CodeForces585 D Ticket Game tutorial算法日常[29/100]

Linmin.Shan included in 算法学习日常

2019-09-26 708 words 2 minutes

Contents

题目链接

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");
}