BZOJ3051: [wc2013]平面图 扫描线+可持久化平衡树+Kruskal
BZOJ2034: [2009国家集训队]最大收益 && BZOJ4276 拟阵+贪心+二分图匹配

BZOJ3895: 取石子 记忆化搜索+博弈论

shinbokuow posted @ Oct 04, 2015 09:39:19 AM in BZOJ with tags 博弈论 记忆化搜索 , 454 阅读
 
 
大爷真是厉害。。。
 
自己没有想到将总操作次数和大小为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;
}
 
 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter