Codeforces 787C

发表于 |

题目

$N$个星球排成一圈，标号$0$到$N-1$。怪物在除了$0$之外的某个点。$2$个人玩游戏，他们各自有一个集合，集合内是整数。$2$个人轮流从他们自己的集合中取一个数$x$，怪物会顺时针的前进$x$步。如果一个人使得怪物走到了$0$处，就输了。

数据范围

$0\leq N \leq 7000$

做法

必胜态：能够转移到必败态的状态。
必败态：只能转移到必败态的状态。
显然，怪物在$0$处是必败态。
我们可以从必败态开始，倒推出其他状态。推不到的状态就是平局。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 7005;
int N, dp[MAX_N][2], deg[MAX_N][2];
vector<int> S[2];
void dfs(int pos, int people)
{
	int op = people ^ 1;
	for (int step : S[op]) {
		int pre = ((pos - step) % N + N) % N;
		if (dp[pre][op]) continue;
		if (dp[pos][people] == 2) {
			dp[pre][op] = 1;
			dfs(pre, op);
		}
		else {
			--deg[pre][op];
			if (!deg[pre][op]) {
				dp[pre][op] = 2;
				dfs(pre, op);
			}
		}
	}
}
int main()
{
	cin >> N;
	for (int j = 0; j < 2; ++j) {
		int k; cin >> k;
		for (int i = 0; i < k; ++i) {
			int tmp; scanf("%d", &tmp);
			S[j].push_back(tmp);
		}
	}
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < N; ++j) {
			deg[j][i] = (int)S[i].size();
		}
	}
	dp[0][0] = dp[0][1] = 2;
	dfs(0, 0);
	dfs(0, 1);
	for (int i = 1; i < N; ++i) {
		if (dp[i][0] == 1) printf("Win");
		else if (dp[i][0] == 2) printf("Lose");
		else printf("Loop");
		printf("%c", i == N - 1 ? '\n' : ' ');
	}
	for (int i = 1; i < N; ++i) {
		if (dp[i][1] == 1) printf("Win");
		else if (dp[i][1] == 2) printf("Lose");
		else printf("Loop");
		printf("%c", i == N - 1 ? '\n' : ' ');
	}
	return 0;
}

注意

这道题与一般的SG博弈不同的是：状态需要包括当前的游戏者。这是因为游戏者不同，从当前位置能转移到的位置也不同。此题的状态应定义为（怪物的位置，当前的游戏者）。