[Multi-SG] POJ 3537 Crosses and Crosses & BZOJ 2940 [Poi2000]条纹

2019-11-06 08:55:52

字体：大中小

来源：转载

供稿：网友

Multi-SG模型是指一个单一游戏又可以分裂成多个游戏实际上并没有改变SG函数的实质单一游戏的SG值是它能分裂成的多个游戏的nim和的mex 记忆化搜索下就好了

POJ 3537

画叉叉：两人在1*N的格子纸上轮流打叉，最先打出连续3个叉者获胜，问必胜者是谁？

#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#define cl(x) memset(x,0,sizeof(x))using namespace std;const int N=2005;int n,sg[N];inline int SG(int x){ if (x<0) return 0; if (sg[x]!=-1) return sg[x]; bool vst[N]; cl(vst); for (int i=1;i<=x;++i) vst[SG(i-3)^SG(x-i-2)]=1; for (int i=0;i<=x && sg[x]==-1;++i) if (!vst[i]) sg[x]=i; return sg[x];}int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); int Sg; memset(sg,-1,sizeof(sg)); while (~scanf("%d",&n)){ Sg=SG(n); PRintf("%s/n",Sg?"1":"2"); } return 0;}

BZOJ 2940

#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>using namespace std;const int N=1005;int a[3];int sg[N];inline int SG(int x){ if (sg[x]!=-1) return sg[x]; bool vst[N]; memset(vst,0,sizeof(vst)); for (int t=0;t<3;t++) if (a[t]<=x) for (int i=1;i<=x-a[t]+1;i++) vst[SG(i-1)^SG(x-i-a[t]+1)]=1; for (int i=0;;i++) if (!vst[i]) return sg[x]=i;}int main(){ int T,n,Sg; freopen("t.in","r",stdin); freopen("t.out","w",stdout); memset(sg,-1,sizeof(sg)); for (int i=0;i<3;i++) scanf("%d",a+i); scanf("%d",&T); while (T--) scanf("%d",&n),printf("%d/n",SG(n)?1:2); return 0;}

上一篇：第一篇博客（我的两年经历）

下一篇：跨境电商：阿根廷本地支付Pago Fácil