公平组合游戏 （Impartial Combinatorial Games，ICG）#
- 两名玩家轮流对当前游戏状态在一个有限集合中进行一次操作。
- 一个局面的合法操作，只取决于游戏本身固然存在，而与玩家的次序或其他因素无关。
- 对于无法进行任何操作的玩家，即操作集合为空，则另一方获胜。
Nim游戏#
$n$ 堆物品，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取，不能操作的玩家为负。
Nim 游戏的结论是所有的 $\bigoplus _{i = 1} ^ {n} a_i = 0$ 为先手必败。
SG函数#
将游戏状态和所有的合法操作抽象为有向无环图（DAG）。
定义没有后继的状态为必败状态。
一个必胜状态的后继中存在一个必败状态。
一个必败状态的后继中不存在一个必败状态。
这里给出一个不是非常严格的理解，上面所有的必胜状态和必败状态都是对于当前所需进行操作的玩家来说的，没有后继的状态为必败状态是游戏结束的前提，对于一个必胜状态，该玩家一定可以通过一种操作到达一种必败状态使自己胜利；对于一个必败状态，如果存在一个必败状态的后继，那么当前操作的玩家就可以通过一种操作到达一个必败状态使自己胜利，这与当前是必败状态所矛盾，因此一个必败状态的后继一定不存在一个必败状态。
给所有的状态设置一个 $SG$ 值，对于 $SG$ 函数有如下定义：
$$
SG(x) = MEX\lbrace SG(y_1), SG(y_2), SG(y_3), …, SG(y_n)\rbrace, \forall i, x \rightarrow y_i
$$
如果只进行一次博弈的话，求 SG 函数没有任何优势，但是对于一个博弈包含多个子博弈有如下定理：
$$
SG(x_1 + x_2 + … + x_n) = SG(x_1) \bigoplus SG(x_2) \bigoplus … \bigoplus SG(x_n)
$$
这里对该结论不进行详细证明，详见OI-wiki
其中，将 $n$ 个子博弈的并行关系用 $+$ 运算连接，每个子博弈都能求出一个 SG 值。
例如在 Nim 游戏中将每堆物品看成一个子游戏，那么整个游戏的 SG 值为所有子游戏的SG值的异或和。
SG值为 $0$ 为先手必败。
MEX
1
2
3
4
5
6
7
8
9
10
11
12
| // v可以是vector、set等容器
int mex(auto v) {
unordered_set<int> S;
for (auto e : v) {
S.insert(e);
}
for (int i = 0;; ++i) {
if (S.find(i) == S.end()) {
return i;
}
}
}
|
2023 杭电多校 1001#
Alice Game
题目大意：
两人轮流操作，其中 $op1$ 表示消除连续不超过 $k$ 个怪物（且这段连续区间左右均为 $e$ 表示空），op2 表示消除连续 $k$ 个怪物，要求这段连续区间删除完后左右至少各有一个怪物。
对于任意一段长度为 $X ,k + 2 \leq X$ 的连续区间，都可以分成 $X_1, X_2$ 两部分，那么 $SG(X) = SG(X_1) \bigoplus SG(X_2)$
基于此，我们通过可以打表发现此题的结论是存在一个 $4k + 2$ 的循环节。
参考代码：
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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> PII;
const int MAX_N = 2e5 + 10, INF = 1e9 + 7, mod = 998244353;
int mex(auto v) {
unordered_set<int> S;
for (auto e : v) {
S.insert(e);
}
for (int i = 0;; ++i) {
if (S.find(i) == S.end()) {
return i;
}
}
}
void solve() {
int k = 2;
int n = 100;
vector<int> dp(n + 1, -1);
auto sg = [&](auto self, int x) -> int {
if(dp[x] != -1) {
return dp[x];
}
set<int> s;
for(int i = 1;; i ++) {
int l = i, r = x - i - k;
if(r <= 0) break;
s.insert(self(self, l) ^ self(self, r));
}
return dp[x] = mex(s);
};
dp[0] = 0;
for(int i = 1; i <= min(n, k); i ++) {
dp[i] = 1;
}
sg(sg, n);
for(int i = 1; i <= n; i ++) {
cout << dp[i] << ' ';
if(i % (4 * k + 2) == 0) {
cout << '\n';
}
}
}
void ac() {
int k, n;
cin >> k >> n;
if(!n || (n >= k + 1 && !((n - k - 1) % (4 * k + 2)))) {
cout << "Bob\n";
} else {
cout << "Alice\n";
}
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1;
cin >> _;
while(_ --) {
ac();
}
}
|
2023 牛客多校 F#
Link with Chess Game
题目大意：
一个长度为 $n$ 的棋盘上有三颗棋子$r, g, b$，两个玩家轮流操作，每次操作都不能到达之前已经经过的三元组$(r_i, g_i, b_i)$，不能进行操作的玩家为负。
对于每种操作进行搜索，因为不能到达之前已经经过的状态，可以进行记忆化搜索打表求出SG函数。
结果发现打表的结果非常有规律，遂AC。
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
| 1:1 1 1!! 0
2:1 1 1!! 1
2:1 1 2!! 1
2:1 2 1!! 1
2:1 2 2!! 1
2:2 1 1!! 1
2:2 1 2!! 1
2:2 2 1!! 1
2:2 2 2!! 1
3:1 1 1!! 0
3:1 1 2!! 1
3:1 1 3!! 0
3:1 2 1!! 1
3:1 2 2!! 0
3:1 2 3!! 1
3:1 3 1!! 0
3:1 3 2!! 1
3:1 3 3!! 0
3:2 1 1!! 1
3:2 1 2!! 0
3:2 1 3!! 1
3:2 2 1!! 0
3:2 2 2!! 1
3:2 2 3!! 0
3:2 3 1!! 1
3:2 3 2!! 0
3:2 3 3!! 1
3:3 1 1!! 0
3:3 1 2!! 1
3:3 1 3!! 0
3:3 2 1!! 1
3:3 2 2!! 0
3:3 2 3!! 1
3:3 3 1!! 0
3:3 3 2!! 1
3:3 3 3!! 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
57
58
59
60
61
62
63
64
65
66
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> PII;
const int MAX_N = 2e5 + 10, INF = 1e9 + 7, mod = 998244353;
bool dp[100][100][100];
bool vis[100][100][100];
int mex(auto v) {
unordered_set<int> S;
for (auto e : v)
S.insert(e);
for (int i = 0;; ++i)
if (S.find(i) == S.end())
return i;
}
int dx[6] = {-1,1,0,0,0,0}, dy[6] = {0,0,-1,1,0,0}, dz[6] = {0,0,0,0,1,-1};
void solve(int n) {
for(int x = 1; x <= n; x ++) {
for(int y = 1; y <= n; y ++) {
for(int z = 1; z <= n; z ++) {
memset(dp, 0, sizeof dp);
memset(vis,0, sizeof vis);
auto sg = [&](auto self, int r, int g, int b) -> void {
vector<int> s;
vis[r][g][b] = true;
for(int k = 0; k < 6; k ++) {
int X = r + dx[k], Y = g + dy[k], Z = b + dz[k];
if(X >= 1 && X <= n && Y >= 1 && Y <= n && Z >= 1 && Z <= n && !vis[X][Y][Z]) {
self(self, X, Y, Z);
s.push_back(dp[X][Y][Z]);
}
}
dp[r][g][b] = mex(s);
};
sg(sg, x, y, z);
cout << n << ":" << x << " " << y << " " << z << "!! " << dp[x][y][z] << '\n';
}
}
}
cout << '\n';
}
void ac() {
ll n, a, b, c;
cin >> n >> a >> b >> c;
if(n % 2 == 0){
cout << "Alice\n";
} else{
if((a + b + c) % 2 == 1){
cout << "Bob\n";
} else {
cout << "Alice\n";
}
}
}
int main () {
ios::sync_with_stdio(0);
cin.tie();
int _ = 1;
cin >> _;
while(_ --) {
ac();
}
}
|