题目链接
CodeForces585 D Ticket Game
题意
- n个数字的车牌,n是偶数(n $\in$ [2,2*$10^5$])
- 一些车牌偶数个数字被搽除了
- 定义美丽车牌的是
前n/2个数字的数字和 == 后n/2个数字的数字和
- M讨厌美丽车牌,而B喜欢
- 玩一个游戏, M先手改被搽除的数字成为0-9中的一个(直到数字被填完)
- 数字填完是美丽的则 B win,否则 M win
题解
借鉴了大佬LIf0703
设先手为 M ，后手为 B 。并把数列左右两边剩下的空格个数记为 a,b 。
当左右两边都有的时候，B 就可以复制 M 的操作。
剩下的操作中可以控制每回合(所以a-b后是要除以2的)的和为 9，如果刚好补完那么后手就能获得胜利，否则先手就可以阻碍后手获胜。
发现大佬的想法总是高屋建瓴!!!
只有我个傻逼想歪了,想着傻逼模拟,然后情况还出错了…
但是还是感觉题解错了,不一定全是0,9的操作啊,可能最后一步是非0,9的操作啊!
当我尝试求出tutorial的反例,然后我失败了
???01?
右边的两个数之和必须是9才有可能B赢! 否则[1-8][10-18]都不行! 因为[1-8]别人取9,[10-18]别人取0!所以delta只有为9的倍数才行!
nb! 所以tutorial没错,只是隐藏了很多信息没有说…还是因为我太菜…
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
39
40
41
42
| #include <bits/stdc++.h>
using namespace std;
inline int read() {
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
int n;
char s[200005];
signed main() {
n = read();
scanf("%s", s + 1);
int a = 0, b = 0, delta = 0;
for (int i = 1; i <= n; i++) {
if ((i << 1) <= n) {
if (s[i] != '?')
delta += s[i] - '0';
else
a++;
} else {
if (s[i] != '?')
delta -= s[i] - '0';
else
b++;
}
}
int cur = ((a - b) >> 1) * 9 + delta;
if (cur) return 0 & puts("Monocarp");
return 0 & puts("Bicarp");
}
|