CF1215D Ticket Game（思维，博弈）

题目

传送门：https://www.luogu.com.cn/problem/CF1215D

Idea

一列数，保证能分成左右两部分，其中有若干个数字被抹掉，两个人轮流填数，如果在把这些空缺的数字填好后左右两部分的数之和相同，则B（后手）赢，否则A（先手）赢。

我们来简单思考一下：

首先如果初始时左右两部分的已有值就是相同的，那只有左右两边空缺的个数相同，B才能赢

如果初始值不同的话，由于两人所能做出的操作都是可以抵消掉的，最后肯定会把左右两边空缺个数较少的那一位先消耗完（肯定是A破坏，B还原，最后某一方消耗完后左右差值依然是初始时的左右差值），然后所有的空缺都集中到左或右其中一方里。

接下来的情况就是在剩下的一方里（假设此时还剩n个空缺），还是A先手，两方每次选择一个0~9之间的数，如果最后选择数的和等于初始左右差值，B赢，否则A赢

这就转换为一个经典博弈问题了，只要(n÷2)×9==差值，B赢，否则A赢。

想想为什么，因为先手的A可以选择0~9的任意一个数，后手的B只可以控制他和A选择的数的总和是9，故如果轮数（两人各填一次算一轮）乘9（B能控制每轮增长的数字和为9）和差值相等，B就赢，否则A就赢。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ll long long

using namespace std;

const int maxn=2000000;

char s[maxn];

ll lsum=0,rsum=0,lcnt,rcnt;

bool Check(int a,int b,int l,int r){

    int res=a-b;

    int sum=(l-r)/2;

    if(sum*9==res) return 1;

    return 0;

}

int main(){

    ios::sync_with_stdio(0);

    int len;

    cin>>len;

    cin>>s;

    for(int i=0;i<len/2;i++){

        if(s[i]!='?') lsum+=s[i]-'0';

        else lcnt++;

    }

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

        if(s[i]!='?') rsum+=s[i]-'0';

        else rcnt++;

    }

    if(lsum==rsum){

        if(lcnt==rcnt) cout<<"Bicarp"<<endl;

        else cout<<"Monocarp"<<endl;

    }

    else if(lsum<rsum){

        if(Check(rsum,lsum,lcnt,rcnt)) cout<<"Bicarp"<<endl;

        else cout<<"Monocarp"<<endl;

    }

    else{

        if(Check(lsum,rsum,rcnt,lcnt)) cout<<"Bicarp"<<endl;

        else cout<<"Monocarp"<<endl;

    }

    return 0;

}

巴特西

CF1215D Ticket Game（思维，博弈）

题目

Idea

最新文章

热门文章