转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目:给出一串石头,和一个集合,每次取出若干个连续的石头(数量必须为集合中的),最后取完的获胜,问有没有必胜策略。
http://acm.hdu.edu.cn/showproblem.php?pid=2999
好像不是很理解SG函数的含义, 可还是乱七八糟的搞出了SG,然后水过去。
对于一个连续的串,比如说长度为5,可行只有2,那么取了之后可能分为两段
如后继可能为:(1,3),{(1),(4,5)},{(1,2),(5)},{3,5}这四种情况。两个区间异或之后,取mex操作
虽不明但觉厉,然后就AC了。
局面是确定的,没有存在不确定的情况
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define N 10005 #define LL long long #define inf 1<<29 #define eps 1e-7 using namespace std; int n,a[100],m,k,cnt,sg[1005]; int get_sg(int n){ if(sg[n]!=-1) return sg[n]; int vis[10000]; memset(vis,0,sizeof(vis)); for(int i=0;i<cnt&&a[i]<=n;i++){ for(int j=0;j<=(n-a[i]);j++){ if(sg[j]==-1) sg[j]=get_sg(j); if(sg[n-j-a[i]]==-1) sg[n-j-a[i]]=get_sg(n-j-a[i]); vis[sg[j]^sg[n-j-a[i]]]=1; } } for(int i=0;;i++) if(vis[i]==0) return i; } int main(){ while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); cnt=1; for(int i=1;i<n;i++) if(a[i]!=a[cnt-1]) a[cnt++]=a[i]; int q; scanf("%d",&q); memset(sg,-1,sizeof(sg)); while(q--){ scanf("%d",&k); if(sg[k]==-1) sg[k]=get_sg(k); if(sg[k]) puts("1"); else puts("2"); } } return 0; }