打表找SG函数规律。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } int sg[200],f[200]; int main() { sg[0]=0; for(int i=1;i<=100;i++) { memset(f,0,sizeof f); for(int j=0;j<i;j++) f[sg[j]]=1; for(int j=1;j<=i;j++) { for(int k=1;k<=i;k++) { for(int s=1;s<=i;s++) { if(j+k+s!=i) continue; f[sg[j]^sg[k]^sg[s]]=1; } } } for(int j=0;j<200;j++) if(f[j]==0) {sg[i]=j;break;} } for(int i=0;i<=100;i++) printf("i:%d sg[i]:%d ",i,sg[i]); return 0; }
然后就可以轻松AC了...
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn=1000000+10; int T,n; LL ans,x; LL SG(LL x) { if(x==0)return 0; if(x==1) return 1; if(x%8==0) return x-1; if((x+1)%8==0) return x+1; return x; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); ans=0; for(int i=1;i<=n;i++) scanf("%lld",&x), ans=ans^SG(x); if(ans) printf("First player wins. "); else printf("Second player wins. "); } return 0; }