暴力打表!!
代码如下:
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #define M 1000000 7 #define ll __int64 8 using namespace std; 9 int sg[1000000]; 10 int get_len(int n) 11 { 12 if(n>=100000) return 6; 13 else if(n>=10000) return 5; 14 else if(n>=1000) return 4; 15 else if(n>=100) return 3; 16 else if(n>=10) return 2; 17 else return 1; 18 } 19 void solve(int n) 20 { 21 int len=get_len(n); 22 for(int i=len;i>0;i--){ 23 int m=n,b=1; 24 for(int j=1;j<i;j++) b*=10; 25 int t=m%(10*b)/b; 26 for(int j=t;j<9;j++){ 27 m+=b; 28 sg[m]=1; 29 } 30 } 31 if(len<6){ 32 int m=n,b=1; 33 for(int i=len;i<6;i++){ 34 m*=10; 35 for(int j=0;j<b;j++) 36 sg[m+j]=1; 37 b*=10; 38 } 39 } 40 } 41 void init() 42 { 43 memset(sg,0,sizeof(sg)); 44 sg[0]=1; 45 for(int i=1;i<=999999;i++) 46 if(!sg[i]) solve(i); 47 } 48 int main() 49 { 50 int i,j,k,m,n,ca=0; 51 init(); 52 char a[7]; 53 while(scanf("%s",a)!=EOF){ 54 bool f=1; 55 if(a[0]!='0'){ 56 int t=atoi(a); 57 f=sg[t]; 58 } 59 puts(f?"Yes":"No"); 60 } 61 return 0; 62 }