BZOJ3895: 取石子 记忆化搜索+博弈论
大爷真是厉害。。。
自己没有想到将总操作次数和大小为1的堆数分开。
很容易想到定义状态的总操作次数为总石子数+总堆数-1。
这样的话无论什么操作都只会花费1的操作次数。
但是大小为1的堆是个毒瘤。。。你会发现如果从这里面取走一个石子会花费2的操作次数。
我们将大小为1的堆分开考虑。
考虑一个状态里面只含有$\geq{2}$的石子堆。
那我们发现，先手必胜当且仅当总操作次数为奇数。
下面证明这个结论：
如果先手操作次数为奇数，若此时堆数为1，先手显然必胜；否则先手可以进行一次任意的合并操作使得操作次数为偶数（且此时依然只含有$\geq{2}$的石子堆）。
现在只需证明操作次数为偶数先手必败。
现在先手操作次数为偶数，如果此时堆数为1的话，先手显然必败；否则：
（1）若先手取走一个$>2$的石子堆中的石子，依然只含有$\geq{2}$的石子堆，而且后手操作次数为奇数；
（2）若先手取走一个大小恰为$2$的石子堆，会产生一个大小为$1$的石子堆，但由于此时堆数$\geq{2}$，后手可以将这个大小为1的石子堆与另外任意一堆进行合并，此时依然只会存在$\geq{2}$的石子堆，又回到了先手操作次数为偶数的情况。
这样就完成了证明。
现在只需再考虑大小为$1$的石子堆就行了。
令$f_{i,j}$表示有$i$个大小为$1$的石子堆，剩下的石子堆操作次数为$j$的先手胜负情况，记忆化搜索即可。
请注意这题有很多细节。。。
我算是不胜其扰。。。只能怪自己弱吧。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int f[51][50050];
int solve(int x,int y){
if(x==0)
return y&1;
if(y==1)
return solve(x+1,0);
if(f[x][y]!=-1)
return f[x][y];
if(!solve(x-1,y))
return f[x][y]=1;
if(x>=2&&!solve(x-2,y==0?2:y+3))
return f[x][y]=1;
if(y>0&&!solve(x-1,y+1))
return f[x][y]=1;
if(y>0&&!solve(x,y-1))
return f[x][y]=1;
return f[x][y]=0;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("tt.in","r",stdin);
#endif
int T;
cin>>T;
int n,i,j,a,b,x;
memset(f,-1,sizeof f);
while(T--){
scanf("%d",&n);
for(a=b=0,i=1;i<=n;++i){
scanf("%d",&x);
if(x==1)
++a;
else
b+=x+1;
}
if(solve(a,b==0?0:b-1))
puts("YES");
else
puts("NO");
}
return 0;
}
评论 (0)