hdu3980 Paint Chain SG函数+SG定理+记忆化搜索-526互联

liyishui今天学习博弈，因为liyishui今天写树链剖分写得有点理智--

题意：

有一个圆，上面有n个豆子，每次要挑出连续m个没染色的豆子进行染色，不能移动时输掉游戏

问先手必胜还是后手必胜，其中n、m<=1000

题解：

会很朴素地想到如果第一个人拿走了m个，那么剩下的就是一条链的问题。

所以可以先n-m，然后交换一下前后手。(当然如果n<m是要讨论一下的)

然后再继续想，如果此时的先手选了一段走，剩下的是什么情况？

就变成左边一段(可能为空)，右边一段(可能也为空)

接下来轮到的人可以操作左边，也可以操作右边

你发现这样等价于有两个游戏——这让我们想到了sg定理：

多线程游戏SG值为子游戏SG值的异或和

所以我们可以枚举当前先手选取了哪段进行切分(有一点区间dp的感觉)

显然不同的分段点对应不同的状态，dfs求出左、右边部分的sg值，异或一下就得到该后继状态的sg值

int vis[N]={0};
    for(int i=1;i<=l-m+1;i++){
        vis[dfs(i-1)^dfs(l-(i+m-1))]=1;
    }

然后再根据sg函数的定义，扫一遍求出哪个是mex，返回即可

for(int i=0;i<N;i++){
        if(!vis[i]){
            //sg[l]=i;
            //cout<<l<<" "<<sg[l]<<endl;
            return sg[l]=i;
        }
    }

感觉思路还是很清晰的，主要考察了sg函数的基本应用

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,sg[N];
int dfs(int l){
    if(!l) return sg[l]=0;
    if(l<m) return sg[l]=0;
    if(sg[l]!=-1) return sg[l];
    int vis[N]={0};
    for(int i=1;i<=l-m+1;i++){
        vis[dfs(i-1)^dfs(l-(i+m-1))]=1;
    }
    for(int i=0;i<N;i++){
        if(!vis[i]){
            //sg[l]=i;
            //cout<<l<<" "<<sg[l]<<endl;
            return sg[l]=i;
        }
    }
    return 0; 
}
int main(){
    //freopen("lys.in","r",stdin);
    int t,cas=0;
    cin>>t;
    while(t--){
        cin>>n>>m;
        memset(sg,-1,sizeof(sg));
        cas++;
        if(n<m){
            cout<<"Case #"<<cas<<": abcdxyzk"<<endl;
            continue;
        }
        n-=m;
        int tmp=dfs(n);
        if(sg[n]) cout<<"Case #"<<cas<<": abcdxyzk"<<endl;
        else cout<<"Case #"<<cas<<": aekdycoin"<<endl;
    }
}