杭电 1404
题意：有一个字符串（由 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");
