[ABC278G] Generalized Subtraction Game

Aigony · 2024-01-04 21:15:49 · 题解

我们有时候要把正经做法和人类智慧结合起来。—— KH

试试直接 dp？设 sg(i) 表示一个长度为 i 的区间的 \text{SG} 值，总复杂度是 \mathcal{O}(n^3) 的，且看起来不可优化。

找性质，如果在第一步能把区间划分成恰好相等的两段，此后不论后手做什么，我们都在另一段做对称的操作，就赢了。

而做不到这种情况时，必然有 l=r 且 l\bmod 2\neq n\bmod 2。
进一步地，重新考虑上面的 dp，因为这时候有 l=r 的保证，转移复杂度就变成了 \mathcal{O}(n^2)。可以写出方程：

求出先后手必胜后，选择对应的一方即可。

至于构造方案，类比 Nim 游戏的证明，对每个 i 开一个桶存放哪些位置能被谁异或到，每次枚举连续段，找到任意一个使 \text{SG} 值变为 0 的方案并操作。 因为这里可以接受平方的复杂度，每次重新统计所有连续段情况是完全可行的。

#include<bits/stdc++.h>
#define il inline
using namespace std;
int n,l,r;
il void Solve()
{
    cout<<"First"<<endl;
    int len=((n-l)&1)?l+1:l,st=((n-len)>>1)+1;
    cout<<st<<" "<<len<<endl;
    while("qwq")
    {
        int a,b; cin>>a>>b; 
        if(a<=0) return;
        int l=a,r=a+b-1; l=n-l+1,r=n-r+1;
        cout<<r<<" "<<l-r+1<<endl;
    }
}
const int N=2005;
int sg[N],t[N][N];
int nw[N];
il bool dopt()
{
    int a,b; cin>>a>>b;
    if(a<=0) return 0;
    for(int i=a;i<=a+b-1;i++) nw[i]=1;
    return 1;
}
struct node{int l,r;};
vector<node> v;
il void wopt()
{
    int st=-1;
    v.clear(); nw[n+1]=1;
    for(int i=1;i<=n+1;i++)
    {
        if(!nw[i]&&st==-1) st=i;
        else if(nw[i]&&st!=-1) v.push_back({st,i-1}),st=-1;
    }
    int now=0;
    for(auto x:v) now^=sg[x.r-x.l+1];
    for(auto x:v)
    {
        int len=x.r-x.l+1,qwq=now^sg[len];
        if(t[len][qwq]!=-1) 
        {
            int st=t[len][qwq]+x.l;
            cout<<st<<" "<<l<<endl;
            for(int i=st;i<=st+l-1;i++) nw[i]=1;
            break;
        }
    }
}
int main()
{
    cin>>n>>l>>r;
    if(l!=r||(n-l)%2==0) {Solve();return 0;}
    memset(t,-1,sizeof(t));
    for(int i=l;i<=n;i++)
    {
        for(int j=0;i-l-j>=0;j++) t[i][sg[j]^sg[i-l-j]]=j;
        while(t[i][sg[i]]!=-1) sg[i]++;
    }
    if(sg[n]) printf("First\n");
    else 
    {
        printf("Second\n");
        dopt();
    }
    while("qwq") 
    {
        wopt();
        if(!dopt()) return 0;
    }
}