首页 > 代码库 > hdu 2999 Stone Game, Why are you always there? （简单SG，有个优化）
hdu 2999 Stone Game, Why are you always there? （简单SG，有个优化）
题意：
一排石头，个数是K。
有n个数，a1...an。
每人每次取石子只能取连续的x个。x属于a1...an的一个。
没法取者负。
思路：
简单的SG。但是TLE！后面加了一个优化~这个优化不好想到吧，看了别人的代码才发现的。就是把a1...an中重复的去掉！。。。
直接看代码。
代码：
int sg[1005];int n,m,k;int a[105];int dfs(int x){ if(sg[x]!=-1) return sg[x]; bool vis[1005]={0}; rep(i,1,n){ if(x<a[i]) break; for(int j=1;j+a[i]-1<=x;++j){ int t1=0; t1=t1^dfs(j-1); t1=t1^dfs(x-j-a[i]+1); vis[t1]=true; } } for(int i=0;;++i){ if(!vis[i]){ return sg[x]=i; } }}int main(){ while(scanf("%d",&n)!=EOF){ rep(i,1,n) scanf("%d",&a[i]); sort(a+1,a+1+n); ///去重，时间一下缩短一半，这数据.... int t1=0; int b[105]; b[0]=-1; rep(i,1,n) if(a[i]!=b[t1]) b[++t1]=a[i]; n=t1; rep(i,1,n) a[i]=b[i]; scanf("%d",&m); mem(sg,-1); while(m--){ scanf("%d",&k); if(!dfs(k)) puts("2"); else puts("1"); } }}
hdu 2999 Stone Game, Why are you always there? （简单SG，有个优化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。