组合游戏概念
$1$.两个玩家
$2$.一个状态集合
$3$.游戏规则是指明玩家在一个状态下可以移动到哪些其他状态
$4$.玩家轮流进行移动
$5$.若当前处于某个状态，玩家根据规则无法移动，则游戏结束
$6$.游戏会在有限步以内结束(有向无环$DAG$)
$P$态和$N$态
$P$态：走到这个状态的玩家赢的状态
$N$态：从这个状态走的玩家赢的状态
至少能走到一个$P$态的状态是$N$态
只能走到$N$态的状态是$P$态
正常规则：终态是$P$态(无法走的人输)
反常规则：终态是$N$态(无法走的人赢)
$P$态和$N$态应用
由$P$态和$N$态的性质可以做出大部分简单的博弈题
对小数据题可以记忆化搜索所有状态
对大数据题可以先打表小数据，看看有无规律
例题：$Digital\ Deletions$
题目大意
有一个只含数字$0$到$9$的串$s$，两个人玩游戏，每次当前玩家可以把某一位改为比当前位更小的数字，或者删除一个$0$以及它的右边全部的数字。删除最后一个数字的人赢。求最优策略下，先手必胜还是后手必胜
串$s$的长度不超过$6$位
解题思路
当一个串的开头是$0$的时候，先手一步获胜，将串变成空串
已知游戏终止状态，即递归终点
那么根据至少能走到一个$P$态的状态是$N$态，只能走到$N$态的状态是$P$态
通过递归遍历所有决策去记忆化搜索即可
具体代码
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
| #include <bits/stdc++.h>
const int N = 1e6 + 1;
int dp[N];
int real_num(std::string t)
{
int res = 0;
for (int i = 0; i < t.size(); ++i)
res = res * 10 + t[i] - '0';
return res;
}
int dfs(std::string u)
{
if (u[0] == '0')
return 1;
int num = real_num(u);
if (dp[num] != -1)
return dp[num];
for (int i = 0; i < u.size(); ++i)
{
char backup = u[i];
for (char j = backup - 1; j >= '0'; --j)
{
u[i] = j;
if (dfs(u) == 0)
return dp[num] = 1;
}
u[i] = backup;
}
for (int i = 0; i < u.size(); ++i)
{
if (u[i] == '0')
{
std::string t = std::string(u.begin(), u.begin() + i);
if(dfs(t) == 0)
return dp[num] = 1;
}
}
return dp[num] = 0;
}
void solve()
{
std::string str;
std::cin >> str;
if (dfs(str) == 1)
std::cout << "Yes\n";
else
std::cout << "No\n";
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
memset(dp, -1, sizeof dp);
while (T--)
solve();
return 0;
}
|
例题：$Bash$游戏
题目大意
一堆石子共$n$个，$A$和$B$两人轮流拿，每次最少拿一颗，最多拿$k$颗，最后无法行动的人输
$A$先手，问谁必胜
解题思路
游戏终止状态是$0$颗石子，此时先手必输，即$P$态
由此打表$/$手玩找规律，非常容易发现规律
具体代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
void solve()
{
int n, k;
std::cin >> n >> k;
if (n % (k + 1))
std::cout << 'A' << '\n';
else
std::cout << 'B' << '\n';
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
solve();
return 0;
}
|
例题：$CF1537D$
题目大意
$Alice$和$Bob$玩游戏，开始时有一个整数，两者轮流行动
每次行动可以在当前的$n$上减去其一个非$1$也非$n$的因子
无法行动者输，$Alice$先手，问谁必胜
解题思路
注释内容为打表
通过打表能很快发现结论为
若$n$为奇数，$Bob$必胜
若$n$为偶数，当$n$为$2$的奇数次幂时，$Bob$必胜，否则$Alice$必胜
具体代码
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
| #include <bits/stdc++.h>
void solve()
{
std::set<int> two_pow;
int t = 2;
while (t <= 1e9)
{
two_pow.insert(t);
t *= 2;
}
int n;
std::cin >> n;
if (n & 1)
std::cout << "Bob" << '\n';
else
{
if (two_pow.count(n))
{
if ((int)std::log2(n) & 1)
std::cout << "Bob" << '\n';
else
std::cout << "Alice" << '\n';
}
else
std::cout << "Alice" << '\n';
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
solve();
return 0;
}
|
例题：$CF1527B2$
题目大意
$Alice$和$Bob$对一个$01$串做游戏
$Alice$先手，每轮可以做两种操作中的一种
$1.$任选一个位置的$0$，将其变为$1$，花费代价$1$
$2.$若当前串不为回文串，且上一个操作不为操作$2$，那么可以$std::reverse$这个$01$串
$01$串变为全$1$时游戏结束，此时花费代价少的人获胜，否则平局
问谁必胜
解题思路
串中对称的两个$1$不再有用
所以考虑对称的$00$，对称的$01$，长度为奇数的串中间是否为$0$，上一次操作是不是$reverse$这四个维度
做记忆化搜索即可
具体代码
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
| #include <bits/stdc++.h>
const int N = 510;
const int M = 2;
const int INF = 0x7f7f7f7f;
int dp[N][N][M][M];
int n;
std::string s;
int dfs(int cnt00, int cnt01, int mz, int rev)
{
if (cnt00 == 0 && cnt01 == 0 && mz == 0)
return dp[cnt00][cnt01][mz][rev] = 0;
if (dp[cnt00][cnt01][mz][rev] != INF)
return dp[cnt00][cnt01][mz][rev];
int res = INF;
if (cnt00 > 0)
res = std::min(res, -dfs(cnt00 - 1, cnt01 + 1, mz, 0) + 1);
if (cnt01 > 0)
res = std::min(res, -dfs(cnt00, cnt01 - 1, mz, 0) + 1);
if (mz == 1)
res = std::min(res, -dfs(cnt00, cnt01, 0, 0) + 1);
if (rev == 0 && cnt01 > 0)
res = std::min(res, -dfs(cnt00, cnt01, mz, 1));
return dp[cnt00][cnt01][mz][rev] = res;
}
void solve()
{
std::cin >> n;
std::cin >> s;
s = "?" + s;
int cnt00 = 0, cnt01 = 0, mz = 0;
for (int i = 1; i <= n / 2; ++i)
{
if (s[i] == '0' && s[n - i + 1] == '0')
++cnt00;
if (s[i] != s[n - i + 1])
++cnt01;
}
if ((n & 1) && s[(n + 1) / 2] == '0')
mz = 1;
int ans = dfs(cnt00, cnt01, mz, 0);
if (ans > 0)
std::cout << "BOB" << '\n';
else if (ans < 0)
std::cout << "ALICE" << '\n';
else
std::cout << "DRAW" << '\n';
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
memset(dp, 0x7f, sizeof dp);
while (T--)
solve();
return 0;
}
|