注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1404 Digital Deletions  

2013-11-24 23:11:42|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1404
给出一串数字,长度最大为6,每次可以有两种操作:选择一个非0数字,改成比其小的数字;选择数字0,舍弃该0以及后面的数字。两人以最优策略进行,最后操作的人胜。
利用SG函数性质,用博弈搜索树搜过。
如果后继状态值均为1,则该状态值为0;如果后继状态中有一个值为0,则该状态值为1.
*Tips:因为串都是数字,可以理解为状态之间能转换,也就是可以记忆化,所以标记数组f可以在输入前标记。因为这个bug,TLE了好几发。。。

char str[12];
int f[2000010];
struct Node{
char ss[12];
int len,num;
};

int fun(char sp[12])
{
int p=0;
int len=(int)strlen(sp);
for(int i=0;i<len;i++)
p=p*10+sp[i]-'0';
return p;
}

int sg(Node a)
{
int t=a.num+a.len*100000;
if(t == 11)
t=t+1-1;
if(f[t] != -1)
return f[t];
if(a.ss[0] == '0')
return f[t]=1;
if(a.len == 0)
return f[t]=0;
Node b;
for(int i=0;i<a.len;i++)
{
b.len=a.len;b.num=a.num;strcpy(b.ss,a.ss);
if(a.ss[i] == '0')
{
b.ss[i]='\0';b.num=fun(b.ss);b.len=(int)strlen(b.ss);
if(!sg(b))
return f[t]=1;
}
else
{
for(int j=a.ss[i]-1;j>='0';j--)
{
b.ss[i]=j;b.num=fun(b.ss);
if(!sg(b))
return f[t]=1;
}
}
}
return f[t]=0;
}

void solve()
{
Node tmp;
strcpy(tmp.ss,str);
tmp.len=(int)strlen(str);
tmp.num=fun(str);
if(sg(tmp))
printf("Yes\n");
else
printf("No\n");
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
//freopen("textout.txt", "w", stdout);
#endif
memset(f,-1,sizeof(f)); //输入前把标记数组f清空,因为所有状态可以相互转换,所以不用每次输入后清空
while(scanf("%s",str)!=EOF)
solve();
return 0;
}



上面的代码有点冗长,可以优化如下:

char str[12];
int f[2000010];
int q[12]={1,10,100,1000,10000,100000,1000000};

int fun(char sp[12])
{
int p=0;
int len=(int)strlen(sp);
for(int i=0;i<len;i++)
p=p*10+sp[i]-'0';
return p+q[len];
}

int sg(char a[])
{
int len=(int)strlen(a);
int t=fun(a);
if(f[t] != -1)
return f[t];
if(a[0] == '0')
return f[t]=1;
if(len == 0)
return f[t]=0;
for(int i=0;i<len;i++)
{
if(a[i] == '0')
{
a[i]='\0';
if(!sg(a))
return f[t]=1;
a[i]='0';
}
else
{
char c=a[i]--;
for(;a[i]>='0';a[i]--)
if(!sg(a))
return f[t]=1;
a[i]=c;
}
}
return f[t]=0;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
//freopen("textout.txt", "w", stdout);
#endif
memset(f,-1,sizeof(f));
while(scanf("%s",str)!=EOF)
{
if(sg(str))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}


  评论这张
 
阅读(95)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017