bzoj 3895 取石子

Posted on | Views:

博弈论.

对于若干堆石子来说,能操作的次数为 石子数目 + 堆的数目 - 1.

如果这些石子中不存在单独一个石子一堆的情况,则答案只与操作次数的奇偶性有关.

证明:当操作次数为 $0$ 时,当前的先手就败了.

若先手从数目 $=2$ 的堆中拿了一个石子,后手可以把剩下那个石子与其他的合并.

若先手从数目 $\ge 3$ 的堆中拿了一个石子,后手可以再从那个堆中拿一个石子,或是将这堆与其他的合并.

操作次数的奇偶性不会变化,最后一定会变成只有一堆石子的情况,正确性就显然了.

而总堆数 $n$ 比较小,可以暴力把单独一个石子的数目记在状态里面.

设 $f(i,j)$ 表示当前有 $i$ 个单独的石子,其余石子的操作次数为 $j$ 时的胜负情况, $1$ 表示先手必胜, $0$ 表示先手必败.

边界为 $i=0$ ,此时可以直接判断胜负情况.转移时,可以进行以下几种操作:

  • 拿走一个单独的石子,会使 $i$ 减少 $1$ .
  • 从石子数目 $>1$ 的堆中拿走一个石子,或者合并两个石子数目 $>1$ 的堆,都只会使 $j$ 减少 $1$ .
  • 合并一个单独的石子和一个石子数目 $>1$ 的堆, 会使 $i$ 减少 $1$ ,而 $j$ 增加 $1$ .
  • 合并两个单独的石子,会使 $i$ 减少 $2$ , $j$ 增加 $3​$ .

注意特判全都是单独的石子的情况,此时合并两个单独的石子, $j$ 只会增加 $2$ .

利用记忆化搜索实现,不同组数据也可以共用记录的 $f$ .

时间复杂度 $O(n\cdot \sum a_i)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=51,MAXM=1e3+10;
int f[MAXN][MAXN*MAXM];
int dfs(int i,int j)
{
	if(i==0)
		return j&1;
	if(j==1)
		return dfs(i+1,0);
	if(f[i][j]!=-1)
		return f[i][j];
	int &res=f[i][j];
	if(!dfs(i-1,j))
		res=1;
	else if(j>0 && !dfs(i,j-1))
		res=1;
	else if(j>0 && !dfs(i-1,j+1))
		res=1;
	else if(i>=2 && !dfs(i-2,j+(j?3:2)))
		res=1;
	else
		res=0;
	return res;
}
int main()
{
	memset(f,-1,sizeof f);
	int T=read();
	while(T--)
	{
		int n=read();
		int x=0,y=-1;
		for(int i=1;i<=n;++i)
		{
			int v=read();
			if(v==1)
				++x;
			else
				y+=v+1;
		}
		if(y==-1)
			y=0;
		puts(dfs(x,y)?"YES":"NO");
	}
	return 0;
}