首页 > 代码库 > poj 3537 Crosses and Crosses （SG）
poj 3537 Crosses and Crosses （SG）
题意：
1 × n 个格子，每人每次选一个格子打上叉（不得重复），如果一个人画完叉后出现了连续的三个叉，则此人胜。
给n，判断先手胜还是先手败。
思路：
假设选择画叉的位置是i，则对方只能在前[1,i-3]中或[i+3,n]中选择画叉。子问题出现。
根据SG的定义，即可求出SG(N)。看代码。
代码：
int sg[2005];int n;int dfs(int n){ if(n<0) return 0; if(sg[n]!=-1) return sg[n]; bool g[2005] = {0}; rep(i,1,n){ int t=dfs(i-3)^dfs(n-i-2); g[t]=true; } for(int i=0;;++i){ if(!g[i]) return sg[n]=i; }}int main(){ mem(sg,-1); while(scanf("%d",&n)!=EOF){ dfs(n); rep(i,0,n) printf("sg[%d]=%d\n",i,sg[i]); if(sg[n]==0) puts("2"); else puts("1"); }}
poj 3537 Crosses and Crosses （SG）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。