• 欢迎光临~

# 博弈论练习2 Digital Deletions(sg函数)

``` 1 #include "bits/stdc++.h"
2 using namespace std;
3 const int MAX=1e6+5;
4 int t,ls;
5 int sg[MAX];
6 char s[15];
7 void sgf(int x){
8     if (sg[x]!=-1) return;
9     int i,j;
10     for (i=1;i<=x;i*=10){
11         j=x;
12         while (j/i%10!=0 && j-i>=i){
13             if (sg[j-i]==0){
14                 sg[x]=1;
15                 goto away;
16             }
17             j-=i;
18         }
19         if (x/i%10==0 && sg[x/i/10]==0){
20             sg[x]=1;
21             goto away;
22         }
23     }
24     sg[x]=0;
25     away: return;
26 }
27
28 int main(){
29     int i,j;
30     scanf("%d",&t);
31     memset(sg,-1,sizeof(sg));
32     sg[0]=1;
33     for (i=1;i<MAX;i++)
34         sgf(i);
35     while (t--){
36         scanf("%s",s+1);
37         ls=strlen(s+1);
38         if (s[1]=='0'){
39             printf("Yesn");
40             continue;
41         }
42         j=0;
43         for (i=1;i<=ls;i++)
44             j=j*10+s[i]-'0';
45         if (sg[j]==0) printf("Non");
46         else printf("Yesn");
47     }
48     return 0;
49 }```