HDOJ 3980 Paint Chain 博弈 SG函数

[cpp]
//HDOJ 3980 Paint Chain 博弈 SG函数

/*
题意：有n个石子围成一个环，每次从中取走m个连续的石子，无法取的输

思路：第一步将取走之后环就变成了链，之后就可以用SG了
      所以特判第一步之后先手变后手后手变先手就可以了
*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 1005

int n,m;
int sg[N];

int mex(int n){
    int i,res;
    bool vis[N];
    if(sg[n] != -1)
        return sg[n];
    memset(vis,false,sizeof(vis));
    for(i = 0; i+m <= n; ++i){
        if(sg[i] == -1)
            sg[i] = mex(i);
        if(sg[n-m-i] == -1)
            sg[n-m-i] = mex(n-m-i);
        vis[sg[i] ^ sg[n-m-i]] = true;
    }
    for(i = 0; ; ++i)
        if(vis[i]==0)
            return i;
}
int main(){
    int i,j;
    int T,ca = 1;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);
        printf("Case #%d: ",ca++);
        if(m > n){
            puts("abcdxyzk");
            continue;
        } www.zzzyk.com
        else if(m == n){
            puts("aekdycoin");
            continue;
        }
        memset(sg,-1,sizeof(sg));
        n -= m;
        puts(mex(n)?"abcdxyzk":"aekdycoin");
    }
    return 0;
}

补充：软件开发 , C++ ,