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.牛能和小镇:

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

,那么
所以只要把所有的 从小到大排序,然后求出任意相邻两个之间的差值的绝对值,累加求和即可。

代码:

#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.装备合成:

假设以第一种方式生成的装备数为 ,以第二种方式生成的装备数为

解法1:线性规划

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

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

代码:

#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:三分

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

代码:

#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,还不会。
题解