牛客练习赛59_牛客博客

A.小乔和小灰灰:

直接暴力求解。

代码：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef pair<int,int>P;
const int N=1010;
char ss[N];
int main()
{
    scanf("%s",ss+1);
    int len=strlen(ss+1);
    char s1[10]="XiaoQiao";
    char s2[15]="XiaoHuiHui";
    bool f1=0,f2=0;
    int p=0;
    for(int i=1;i<=len;i++)
    {
        if(ss[i]==s1[p])
            p++;
        if(p==8)
        {
            f1=1;
            break;
        }
    }
    p=0;
    for(int i=1;i<=len;i++)
    {
        if(ss[i]==s2[p])
            p++;
        if(p==10)
        {
            f2=1;
            break;
        }
    }
    if(f1&&f2)
        printf("Happy\n");
    else
        printf("emm\n");
    return 0;
}

B.牛能和小镇:

一看是求最小生成树，直接开始一顿猛敲 $kruscal$ ，交完后显示超出内存限制，我才去看数据范围： $1e5$ ，怎么多边，肯定要超。然后就一直卡住了。
题解是：
先把花费的计算公式化简。

$∣x_i^2y_i−x_j^2y_j+y_i^2(y_i−2x_i)−y_j^2(y_j−2x_j)∣$

$=|x_i^2y_i-2x_iy_i^2+y_i^3-(x_j^2y_j-2x_jy_j^2+y_j^3)|$

令 $A_i=x_i^2y_i-2x_iy_i^2+y_i^3$ ，那么 $dis=|A_i-A_j|$ ；
所以只要把所有的 $A_i$ 从小到大排序，然后求出任意相邻两个之间的差值的绝对值，累加求和即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N];
int main()
{
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        a[i]=1LL*x*x*y-1LL*2*x*y*y+1LL*y*y*y;
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=1;i<n;i++)
        ans+=abs(a[i]-a[i+1]);
    printf("%lld\n",ans);
    return 0;
}

C.装备合成:

假设以第一种方式生成的装备数为 $k_1$ ，以第二种方式生成的装备数为 $k_2$ 。

解法1：线性规划

一开始没有往这边想，看题解的时候看到有人这样写，才想起来高中还学过这个东西。
先写约束条件：

$\begin{cases} 2k_1+4k_2\leq x\\ 3k_1+k_2\leq y \end{cases}$

目标函数为： $z=k_1+k_2$
问题的最优解在交点处取得。
可能的交点有直线与坐标轴的交点，两条直线的交点。但要保证点的坐标为整数。
与坐标轴的交点，直接向下取整即可。
注意的是，如果两条直线的交点不为整数，需要枚举其周围的 $4$ 个点来求最大。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y;
bool check(ll a,ll b)
{
    if(2*a+4*b<=x&&3*a+b<=y)
        return true;
    else
        return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&x,&y);
        ll ax=min(x/2,y/3),ay=0;
        ll by=min(x/4,y),bx=0;
        ll cx=(4*y-x)/10,cy=(3*x-2*y)/10;//交点左下方的点
        ll ans=max(ax,by);
        if(cx>=0&&cy>=0)
        {
            ans=max(ans,cx+cy);
            cx++;
            if(check(cx,cy))
                ans=max(cx+cy,ans);
            cy++;
            if(check(cx,cy))
                ans=max(cx+cy,ans);
            cx--;
            if(check(cx,cy))
                ans=max(cx+cy,ans);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

解法2：三分

首先，暴力的想法，枚举 $k_1$ ，然后求出 $k_2$ ，找到最大值，但是会超时。枚举的过程中发现，最大值其实是有单调性的，所以用三分解决单峰函数最值问题。
证明单调性：
假设 $k_1$ 个一类装备是最优的，减掉一个 $1$ 类装备，最多只可能增加 $1$ 个二类装备；增加一个 $1$ 类装备，可能减少多个 $2$ 类装备，因此在最优答案两边都是递减的。
写三分的时候，最后确定的是 $4$ 个可能点即极值点的取值范围，无法确定具体的点。需要枚举求最大。

代码：

#include <bits/stdc++.h>
using namespace std;
int x,y;
int solve(int a)
{
    return a+max(0,min((x-2****-3*a));
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&x,&y);
        int l=0,r=min(x/2,y/3),ans=0;
        while(l+2<r)
        {
            int mid1=(l+r)>>1;
            int mid2=(mid1+r)>>1;
            if(solve(mid1)>solve(mid2))
                r=mid2-1;
            else
                l=mid1+1;
        }
        for(int i=l;i<=r;i++)
            ans=max(ans,solve(i));
        printf("%d\n",ans);
    }
    return 0;
}

D.取石子游戏：

找必胜态和必输态，推出转移关系。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100;
vector<ll>num;
int sg[N];
void init()
{
    sg[0]=0;
    num.push_back(1);
    ll n=1;
    int cnt=1;
    while(n<=1e18)
    {//cout<<"n="<<n<<endl;
        if(cnt&1)
        {
            n=2*n+1;
            sg[++cnt]=1;
        }
        else
        {
            n=n*2;
            sg[++cnt]=0;
        }
        num.push_back(n);
    }//cout<<"cnt="<<cnt<<endl;
}
int main()
{
    int t;
    ll n;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        int tt=lower_bound(num.begin(),num.end(),n)-num.begin();//cout<<"tt="<<tt+1<<endl;
        if(sg[tt+1]==1)
            printf("XiaoHuiHui\n");
        else
            printf("XiaoQiao\n");
    }
    return 0;
}

E,F都涉及dp,还不会。
题解