abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S5041 【游戏】

发表于 更新于

Description

给你一个有 $n$ 个点的树，初始时有一个硬币在 1 号节点。现在玩家 A 和玩家 B 轮流操作。玩家 A 可以把一个点打叉，使硬币不能到达，B 可以把硬币移动一次，且硬币不能走重复路。游戏时双方都采用最优策略，现在问你：在玩家 A 不知道玩家 B 的操作的情况下是否存在一种打叉的策略使得硬币的移动次数小于 $k$。

Solution

个人比较喜欢这道题，感觉算是近些日子做的比赛中出得比较好的题了。

考虑转换问题，题目即求：在树中选择 $k$ 个深度不同的点（不能为根节点），使得以他们为根的子树包含了所有深度为 $k$ 的点，问你是否可行。

那么考虑在对树进行 DFS 遍历的时候把深度为 $k$ 的点记下来，为了方便表述，下文中称这个记录的顺序为 DFS 序。

再考虑证明只有当 $k^2 < n$ 时才有答案，一个感性的证明：

一个点两个分叉它容易被一石二鸟，不是很优秀。
所以一堆直链看起来最棒。
可以得出根号条直链最棒。

引用部分摘自 @WerKeyTom_FTD 的博客。

那么只有当 $k < 20$ 才可能有解，显然可以设 $f_{i, S} = 0 / 1$ 表示当前覆盖了 DFS 序中 $[1, i]$ 的点，打叉的点的深度集合为 $S$ 的这种局面 不可能 / 可能 出现。

具体的转移见 Code 部分。

Code

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cstdio>
#include <cstring>
#define maxN 410
struct edge{ int x, y, g; } b[maxN << 1];
int len = 0, n = 0, k = 0;
bool f[maxN][1 << 20];
int dfn[maxN], dep[maxN], end[maxN], fa[maxN], h[maxN];
int max (int x, int y)
{
	return x > y ? x : y;
}
void ins (int x, int y)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].g = h[x];
	h[x] = len;
}
void dfs (int x)
{
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(dep[y] < 0)
		{
			fa[y] = x;
			dep[y] = dep[x] + 1;
			if(dep[y] == k)
			{
				end[y] = ++dfn[0];
				dfn[dfn[0]] = y;
			}
			dfs(y);
			end[x] = max(end[x], end[y]);
		}
	}
}
int main ()
{
	scanf("%d %d", &n, &k);
	if(k * k >= n)
	{
		printf("DA");
		return 0;
	}
	for(int i = 1;i < n; i++)
	{
		int x = 0, y = 0;
		scanf("%d %d", &x, &y);
		ins(x, y);
		ins(y, x);
	}
	int root = 1;
	memset(dep, -127 / 3, sizeof(dep));
	dep[root] = 0;
	dfs(root);
	f[0][0] = true;
	int Ma = (1 << k) - 1;
	for(int i = 0;i < dfn[0]; i++)
	{
		for(int S = 0;S <= Ma; S++)
		{
			if(f[i][S])
			{
				int x = dfn[i + 1];
				while(dep[x])
				{
					if(!(S & (1 << (dep[x] - 1))))
					{
						f[end[x]][S | (1 << (dep[x] - 1))] = true;
					}
					x = fa[x];
				}
			}
		}
	}
	printf("%s", f[dfn[0]][Ma] ? "DA" : "NE");
	return 0;
}