首页 > 代码库 > POJ 2960

POJ 2960

也算是一道模板题吧,只需按照SG函数的定义求出每个值的SG,然后异或就可以了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 const int N=10005;
 7 int sg[N];
 8 bool vis[N];
 9 int k,s[105];
10 int p[105],top;
11 int work(int w){
12     int mi=0,i;
13     for(i=1;i<=k;i++){
14         if(w-s[i]>=0)
15         p[++top]=sg[w-s[i]];
16     }
17 //    if(w==2)
18 //    printf("%d\n",p[0]);
19     sort(p,p+top+1);
20     for(i=0;i<=top;i++){
21         if(p[i]==mi)
22         mi++;
23         else if(p[i]>mi)
24         break;
25     }
26     return mi;
27 }
28 char ans[105],tot;
29 int main(){
30     int i;
31     while(scanf("%d",&k)!=EOF){
32         if(!k) break;
33     //    memset(sg,-1,sizeof(sg));
34     //    memset(vis,false,sizeof(vis));
35         sg[0]=0;
36         for(i=1;i<=k;i++){
37             scanf("%d",&s[i]);
38         }
39         for(i=1;i<=10000;i++){
40             top=-1;
41             sg[i]=work(i);
42         //    if(i<=12)
43         //    printf("%d ",sg[i]);
44         }
45     //    printf("\n");
46         int n,tmp; tot=-1;
47         scanf("%d",&k);
48         for(i=1;i<=k;i++){
49             scanf("%d",&n);
50             int anst=0;
51             for(int j=1;j<=n;j++){
52                 scanf("%d",&tmp);
53                 anst=(anst^sg[tmp]);    
54             }
55             if(!anst)
56             ans[++tot]=L;
57             else ans[++tot]=W;
58         }
59         for(i=0;i<=tot;i++)
60         printf("%c",ans[i]);
61         printf("\n");
62     }
63     return 0;
64 }
View Code