首页 > 代码库 > 【poj3537】 Crosses ans Crosses

【poj3537】 Crosses ans Crosses

poj.org/problem?id=3537 (题目链接)

题意:给出一个1*n的棋盘,每次可以选择一个没被标记过的点打标记,若经过某一步操作使得出现3个连续的标记,则最后操作的人获胜。问是否存在先手必胜策略。

Solution 
  我们可以很快发现,若给x位置打上标记,那么棋盘就被分成了2份,分别是x-3以及n-x-2,于是sg[n]=mex{sg[x-3]^sg[n-x-2]},1<=x<=n。因为n<=2000,直接暴力求解sg函数即可。

代码:

// poj3537#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=2010;int n,sg[maxn];int cal(int x) {    if (x<0) return 0;    if (sg[x]!=-1) return sg[x];    bool vis[maxn];    memset(vis,0,sizeof(vis));    for (int i=1;i<=x;i++)        vis[cal(i-3)^cal(x-i-2)]=1;    for (int i=0;;i++) if (!vis[i]) return sg[x]=i;}int main() {    int n;    scanf("%d",&n);    memset(sg,-1,sizeof(sg));    if (cal(n)) printf("1");    else printf("2");    return 0;}

  

【poj3537】 Crosses ans Crosses