題意：有一個字符串（由 0--9 組成 ），兩個人輪流改變字符串的值，誰最後將字符串改成無，就贏。 規則： 1：可以修改任意一個值，可將該值修改成小於它的任意一值。（例：str=“1234”，可將4改成0或1或2或3，也可以將3改成0，或1，或2） 2：每次只能改一個值 3：假如碰到0，可以將0和其右邊的值消掉。（例：str=“1023”，可以變成str=“1”） 思路：博弈題型，所以就求SG值就行了，SG值為0 的必輸，反之必贏。 可將字符串當整數處理，但是，必須記得，這是字符串，不是真正的整數。 先聲明一下將字符串變整數的規則： 1：字符串"1234"可以當成整數1234處理 2：以0開頭的字符串統一當成字符串"0"處理，且其SG值為1（因為這是比勝態）。 根據游戲規則，來講講怎麼求每個字符串的後繼： 例：str=”1023“ 先改3的值，可以變成："1022"，"1021"，"1020"。 改2的值，可以變成："1013"，"1003"。 改0的值，變成："1"。 改1的值，可以變成："0023"。 代碼： [cpp] #include<stdio.h> #include<string.h> #include<stdlib.h> int sg[1000000]; int getint(char *str)//返回字符串的整型值 { int num=0; int length=strlen(str); int j; for(j=0;j<length;j++) { num=num*10+(str[j]-48); } return num; } int mex(char *str) { int a[55]={0};//最多54個後繼 int length = strlen(str); int i,j,keep,num; for(i=length-1;i>=0;i--)//掃描所有後繼 { if( str[i]==48 ) { if( i==0 )//必勝態 { a[1]=1; } else { str[i]=0; num=getint(str); if( sg[ num ]==-1) sg[ num ]=mex(str); a[ sg[ num ] ]=1; str[i]=48; } continue; } for(j=str[i]-1;j>=48;j--) { keep=str[i];//保存一下原值 str[i]=j; if(j==48) { if( i==0 )//這是必勝態 { a[1]=1; } else { num=getint(str); //str[i]=0; if( sg[ num ]==-1) sg[ num ]=mex(str); a[ sg[ num ] ]=1; } } else { num=getint(str); if( sg[ num ] == -1 ) { sg[ num ]=mex(str); } a[ sg[ num ] ]=1; } str[i]=keep;//還原數值 } } for(i=0;i<55;i++) if(a[i]==0) return i; } int main() { int i; char str[7]; memset(sg,-1,sizeof(sg)); sg[0]=1; while( gets(str) ) { if(str[0]==48)//這是必勝態 { printf("Yes\n"); continue; } if( sg[ getint(str) ]==-1 ) { sg[ getint(str) ]=mex(str); } if( sg[ getint(str) ]==0 ) printf("No\n"); else printf("Yes\n"); } return 0; }
