链接:http://acm.hdu.edu.cn/showproblem.php?pid=1536
典型尼姆题,直接sg模板搞
之前mex设为int,怎么都te过不了,看了讨论之后说设为bool就过了,但是我不知道为什么,是bool更快吗???
ac代码:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #define maxn 10001 7 using namespace std; 8 int f[maxn],sg[maxn];bool mex[maxn]; 9 void getsg(int k,int n){ 10 int i,j; 11 memset(sg,0,sizeof(sg)); 12 for(i=1;i<=n;i++){ 13 memset(mex,0,sizeof(mex)); 14 for(j=1;f[j]<=i&&j<=k;j++) 15 mex[sg[i-f[j]]]=true; 16 for(j=0;j<=n;j++){ 17 if(mex[j]==false){ 18 sg[i]=j; 19 break; 20 } 21 } 22 } 23 } 24 int main(){ 25 int n,m,k,q,p,t,ans; 26 while(scanf("%d",&n)&&n){ 27 for(int i=1;i<=n;i++){ 28 scanf("%d",&f[i]); 29 } 30 sort(f+1,f+1+n); 31 getsg(n,10001); 32 scanf("%d",&q); 33 for(int i=1;i<=q;i++){ 34 ans=0; 35 scanf("%d",&p); 36 for(int j=1;j<=p;j++){ 37 scanf("%d",&t); 38 ans^=sg[t]; 39 } 40 if(ans==0)printf("l"); 41 else printf("w"); 42 } 43 printf("n"); 44 } 45 return 0; 46 }
0 条评论