首页 > 代码库 > BZOJ 3895: 取石子[SG函数 搜索]
BZOJ 3895: 取石子[SG函数 搜索]
有N堆石子
·从某堆石子中取走一个
·合并任意两堆石子
不能操作的人输。
100%的数据满足T<=100, N<=50. ai<=1000
容易发现基础操作数$d=\sum a_i +n-1$
没有个数为1的堆还好说，有的话@#$%^&好麻烦啊啊啊啊啊怎么可能找规律
然后看题解，woc记忆化搜索
$f(i,j)$表示i个个数为1的堆，其他操作数为j的胜负态
枚举操作转移就行了，一定要枚举对！注意$j=1$时
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=51,M=50055;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,f[N][M]; int dfs(int a,int b){ int &now=f[a][b]; if(now!=-1) return now; if(a==0) return now=b&1; if(b==1) return now=dfs(a+1,0); if(a && !dfs(a-1,b) ) return now=1; if(b && !dfs(a,b-1) ) return now=1; if(a && b && !dfs(a-1,b+1) ) return now=1; if(a>=2 && !dfs(a-2,b+2+(b!=0)) ) return now=1; return now=0;}int main(){ //freopen("in","r",stdin); int T=read(); memset(f,-1,sizeof(f)); while(T--){ n=read(); int x=0,y=0,a; for(int i=1;i<=n;i++){ a=read(); if(a==1) x++; else y+=a+1; } if(y) y--; puts(dfs(x,y) ? "YES" : "NO"); }}
BZOJ 3895: 取石子[SG函数 搜索]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。