CodeFoeces 1215 D Ticket Game

题目大意

M和B轮流玩游戏（每一轮M先手

现在给出一个长度为偶数的串，包含字符'?'和数字

现在两人依次在'?'上填数字\(0\)~\(9\)

若M先手，最后串的左右两部分数字之和相等，则B赢，反之M赢

solution

难得教练给一道稍稍简单的题QwQ

最好想的状态就是：

若一开始左边的和等于右边的和
- 若左边的'?'数量等于右边的，那么每次M放一个数字，B放一个同样的，显然B赢
- 反之，两边的'?'数量不相等，那么先手赢
若一开始两边的和不相等
- 如果大的一边'?'较多，那么先手必胜，因为后手不可缩小差距
- 反之，则就需要讨论一下了，前“小”次按照保持差距去放，然后剩下的次数，也就是两边个数之差，下面后手的任务就是缩小差距那么每次补齐9即可，也就是说，相差的数字除了B放的数字要求能被9整除，那么后手赢。反之，先手赢。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=2e5+5;

int n;

char s[maxn];

int ls, rs, x, y;

int main(){

    scanf("%d", &n);

    scanf("%s", s + 1);

    for(int i = 1; i <= n / 2; i++){

        if(s[i] == '?') x++;

        else ls += s[i] - '0';

    }

    for(int i = n / 2 + 1; i <= n; i++){

        if(s[i] == '?') y++;

        else rs += s[i] - '0';

    }

    if(ls<rs){

        swap(ls, rs);

        swap(x, y);

    }

    if(ls == rs){

        printf("%s\n", x == y? "Bicarp":"Monocarp");

    }

    else{

        if(x >= y) printf("Monocarp\n");

        else printf("%s\n", (y - x) % 2 == 0 && ls - rs == (y - x)/2*9? "Bicarp":"Monocarp");

    }

    return 0;

}

巴特西

CodeFoeces 1215 D Ticket Game（数学，思维）

CodeFoeces 1215 D Ticket Game

题目大意

solution

最新文章

热门文章