首页 > 代码库 > HDU 3032 Nim or not Nim?(sg函数)
HDU 3032 Nim or not Nim?(sg函数)
题目链接
暴力出来,竟然眼花了以为sg(i) = i啊....看表要认真啊!!!
#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define LL __int64 int dp[10001]; int sg(int x) { int flag[10001],temp,i; if(dp[x] >= 0) return dp[x]; memset(flag,0,sizeof(flag)); for(i = 1;i <= x;i ++) { temp = sg(x-i); flag[temp] = 1; } for(i = 1;i < x;i ++) { temp = sg(i)^sg(x-i); flag[temp] = 1; } for(i = 0;;i ++) if(!flag[i]) return dp[x] = i; } int main() { int n,m,i,ans,t; scanf("%d",&t); while(t--) { scanf("%d",&n); ans = 0; for(i = 0;i < n;i ++) { scanf("%d",&m); if(m%4 == 0) m --; else if((m+1)%4 == 0) m ++; ans ^= m; } if(ans) printf("Alice\n"); else printf("Bob\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。