CF1839E 题解

honglan0301 · 2023-06-05 19:57:59 · 题解

题目分析

实质上是让你找必胜策略的简单博弈题。题意转化一下是让你每次选两个数换成它们的差，问最后会不会剩下一个数，根据样例和手玩从 n=2 开始向大推广，容易得出以下结论：

• 若能分成两组和相等的数则后手必胜，策略是每次选与先手选的数不同组的数；若不能则先手必胜，策略是随便选。

猜到之后很好证明：

• 前者：显然每次后手按照策略选完后都不会改变“能分成两组相等的数”这一性质（操作前后分组方法是不变的），所以若先手能选则后手一定也能选，后手必胜。

• 后者：事实上不管怎么选都不改变“不能分成两组相等的数”这一性质（因为一次操作仅会把 a,b 变成 |a-b|，若操作后能分，则操作前把 \min (a,b) 放到另一组也就能分），所以数的个数每次减少一或二，最终一定会 只剩下一个数 或者 剩下两个不等的数（此时在操作一轮就只剩一个数了），那么先手必胜。

所以做完了，随便写个背包判胜负即可。

代码

int n,a[305],sum,dp[305][90005],zt[305];

signed main()
{
    cin>>n; for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    dp[0][0]=1;
    for(int i=1;i<=n;i++) {for(int j=a[i];j<=sum;j++) dp[i][j]|=dp[i-1][j-a[i]]; for(int j=0;j<=sum;j++) dp[i][j]|=dp[i-1][j];}
    if(sum&1||!dp[n][sum/2])
    {
        cout<<"First"<<endl; int na=0,nb=0;
        while(1)
        {
            for(int i=1;i<=n;i++) if(a[i]) {na=i; break;}
            cout<<na<<endl; cin>>nb; if(nb==0) return 0; 
            int kk=min(a[na],a[nb]); a[na]-=kk; a[nb]-=kk;
        }
    }
    cout<<"Second"<<endl;
    int na=n,nb=sum/2;
    while(na)
    {
        if(nb>=a[na]&&dp[na-1][nb-a[na]]) zt[na]=1,nb-=a[na]; na--;
    }
    while(1)
    {
        cin>>na; if(na==0) return 0;
        for(int i=1;i<=n;i++) if(a[i]&&zt[i]!=zt[na]) {nb=i; break;}
        cout<<nb<<endl; int kk=min(a[na],a[nb]); a[na]-=kk; a[nb]-=kk;
    }
}