HDOJ 2999 Stone Game, Why are you always there? 博弈 SG函数

[cpp]
//HDOJ 2999 Stone Game, Why are you always there? 博弈 SG函数
/*
题意：有n个石子排成一行，每次只能取走连续的f个石子，f为给定的一个集合。
      问先手胜负态

思路：局面不可能存在无法判断的情况
      假设有4个石子集合中只有一个数2
      则后继状态有｛0，2｝｛1，1｝，｛2，0｝
      因为｛0，2｝和｛2，0｝表示一样的状态因此可以加一个剪枝

*/

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

#define N 105
#define M 1005

int n,cnt;
int op[N],sg[M];

int mex(int n){
    int i,j;
    bool vis[1005];
    if(sg[n] != -1)
        return sg[n];
    memset(vis,false,sizeof(vis));
    for(i = 1; i < cnt && op[i] <= n; ++i){
        for(j = 0; j+op[i] <= n && j < n/2+1 ; ++j){
            if(sg[j] == -1)
                sg[j] = mex(j);
            if(sg[n-j-op[i]] == -1)
                sg[n-j-op[i]] = mex(n-j-op[i]);
            vis[sg[j]^sg[n-j-op[i]]] = true;
        }
    }
    for(i = 0; ; ++i)
        if(vis[i]==false)
            return i;
}

int cmp(const void *a,const void *b){
    return *(int *)a - *(int *)b;
}

int main(){
    int i,k,m;
    while(scanf("%d",&n)!=EOF){
        for(i = 1; i <= n; ++i)
            scanf("%d",&op[i]);
        qsort(op+1,n,sizeof(op[0]),cmp);
        cnt = 2;
        for(i = 2; i <= n; ++i)
            if(op[i] != op[i-1])
                op[cnt++] = op[i];

        memset(sg,-1,sizeof(sg));
        scanf("%d",&k);
        while(k--){
            scanf("%d",&m);
            if(sg[m] == -1)
                sg[m] = mex(m);
            puts(sg[m]?"1":"2");
        }
    }
    return 0;
}

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