题目描述
Link
Solution
非常不错的一道博弈论题目，模型有点像Bash博弈。
首先这道题我们可以这么理解：有两堆石头，其中一堆有 $x$ 个石头，只能放 $n$ 次石头，每次能放的石头数量不超过 $9$ 个，另一堆有 $y$ 个石头，能放 $m$次，每次能放的石头数量也不超过 $9$ 个。每次操作可以放 $0$ 个石头 。先手后手轮流操作，两堆石头都可以放，如果两堆石头能放的次数用完了，当且仅当两堆石头个数相等时后手赢，问后手是否有必胜策略。
根据题意我们可以得出这样一个结论：当且仅当 $n=m$ 以及 $x=y$ 时，后手必赢。
所以我们为了达到这个局面，必须要让其中一堆石头的个数小于另一堆石头并且这一堆石头能放的次数大于另一堆石头，或者是两堆石头的石头个数以及能放的次数均相等。
我们再来看题目，题目中说了 $n + m$ 是偶数，所以又可以得出 $|n - m|$ 一定是偶数。
所以如果出现了 $n < m$ 且 $x > y$ 的局面，要想让后手必赢，必须满足 $x - y = 9 * (m - n)$。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 200010
char a[MAXN];
int n, p, q, x, y;
int main() {
scanf("%d", &n);
scanf("%s", a + 1);
for (int i = 1; i <= n / 2; i++) {
if (a[i] != '?') p += a[i] - '0';
else x++;
}
for (int i = n / 2 + 1; i <= n; i++) {
if (a[i] != '?') q += a[i] - '0';
else y++;
}
if (x < y) std::swap(x, y), std::swap(p, q);
if (p > q) {
puts("Monocarp");
return 0;
}
if (p == q && x == y) {
puts("Bicarp");
return 0;
}
x -= y;
q -= p;
if (q == (x / 2) * 9) {
puts("Bicarp");
return 0;
}
else {
puts("Monocarp");
return 0;
}
}
|
