首页 > 代码库 > hdu 3032 Nim or not Nim? （SG，然后找规律）
hdu 3032 Nim or not Nim? （SG，然后找规律）
题意：
n堆石头，每堆石头个数：s[1]...s[n]。
每人每次可以选择在一堆中取若干个（不能不取），或者把一堆石头分成两堆（两堆要都有石头）。
无法操作者负。
数据范围：
(1 ≤ N ≤ 10^6, 1 ≤ S[i] ≤ 2^31 - 1)
思路：
S[i]太大了，直接求SG铁定TLE，所以先把SG打出来看看找一下规律。
分堆也挺好理解，把它抽象成游戏图去想就清晰了。
直接看代码。
代码：
int sg[10005];int s[10005];///打表发现当x=0,4k+1,4k+2时sg[x]=x 当x=4k+3时sg[x]=4k+4; x=4k+4时sg[x]=4k+3/*int dfs(int x){ if(sg[x]!=-1) return sg[x]; bool vis[10005]={0}; rep(i,0,x-1){ vis[dfs(i)]=1; } rep(i,1,x/2){ int t1=0; t1=t1^dfs(i); t1=t1^dfs(x-i); vis[t1]=1; } for(int i=0;;++i) if(!vis[i]) return sg[x]=i;}*/int T,n;int main(){ cin>>T; while(T--){ scanf("%d",&n); rep(i,0,n-1) scanf("%d",&s[i]); int t=0; rep(i,0,n-1){ if((s[i]-1)%4==0 || (s[i]-2)%4==0) t=t^s[i]; if((s[i]-3)%4==0) t=t^(s[i]+1); if((s[i])%4==0) t=t^(s[i]-1); } if(!t) puts("Bob"); else puts("Alice"); }}
hdu 3032 Nim or not Nim? （SG，然后找规律）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。