POJ-3537-Crosses and Crosses

点击打开题目链接

 

/*
题意：在1*n的格子里画X，当有连续的三个，就获胜；那么当第一个人在i位置画时，
就能够得到子问题，即在1*i-3 和 1 * （n-i-2）的两个游戏;套用sg模板就能够了；
*/ 

# include <stdio.h>
# include <cstdlib>
# include <cstring>
# include <iostream>
using namespace std;

int sg[2100];

inline int dfs(int x)
{
    if(x < 0)   return 0;
    if(sg[x] >= 0)  return sg[x];
    int mex[2100] = {0};    //值得注意的是这个不要写在函数if推断的前面;会超时;
    for(int i = 1;i <= x;i++){
        int t = dfs(i-3) ^ dfs(x-i-2);
        mex[t] = 1;
    }
    for(int i = 0;;i++) if(!mex[i]) return sg[x] = i;
}

int main()
{
    int n;
    memset(sg,-1,sizeof(sg));
    while(~scanf("%d",&n)){
        if(dfs(n))   puts("1");
        else    puts("2");
    }
    return 0;
}