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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 2999 Stone Game, Why are you always there?  

2014-05-08 19:49:15|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=2999
题意:
给出一个集合,一个长K的石子串,每次只能取a连续的石子,a在集合里,谁不能取算输。
题解:
SG,算每种子状态的SG值时,因为一个石子串被取后可能分成两个串,所以子状态的SG异或结果就是当前状态的SG值。
另外,这题数据很强,能加的优化都需要加上,否则TLE到哭。。。

int n,m,k,tot,a[110],f[1010];
set<int>s;
set<int>::iterator it;

int sg(int p)
{
if(f[p] != -1)
return f[p];
bool mex[1010];
MEM(mex);
for(int i=0;i<tot && a[i]<=p;i++)
for(int j=0;p-a[i]-j >= 0;j++)
mex[sg(j)^sg(p-a[i]-j)]=1;
int i=0;
while(mex[i]) i++;
return f[p]=i;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
int t;
while(sf(n)!=EOF)
{
//去重
s.clear();
fr(n){
sf(t);
s.insert(t);
}
tot=0;
for(it=s.begin();it!=s.end();it++)
a[tot++]=*it;

sf(m);
memset(f,-1,sizeof(f));
while(m--)
{
sf(k);
if(sg(k)) pf(1);
else pf(2);
}
}
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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