题目
解说
前置
翻译什么的链接里已经说的很清楚了,这里不再赘述,看题吧。
一看见这博弈论模样的题就知道又是思维题了。
设身处地想一想，假如你是游戏里的人你会怎么让自己赢。首先，开局时左右两边数字和肯定有一个大小关系，假如我是(Monocarp),我先手，我肯定会在大的一边把(?)改成(9)以拉大差距,而接下来的(Bicarp)最好的策略就是先在小的一边把(?)改成(9)补回差距。
基本战略确定了，接下来就能讨论了。
根据上面的推论，我们基本可以确定首先要统计两边开局的数字和以及问号个数。
cin>>n>>s+1;
for(int i=1;i<=n/2;i++){
if(s[i]!='?') suml+=s[i]-'0';
else l+=1;
}
for(int i=n/2+1;i<=n;i++){
if(s[i]!='?') sumr+=s[i]-'0';
else r+=1;
}
P.S. 下面说明情况都是在排除了已经给出的情况之后。
情况一
我能想到的最简单情况就是两边开局就相等，这时只有两边问号也相等(Bicarp)才能胜利。为什么？显然问号不相等的话(Monocarp)在一边加了数(Bicarp)无法在另一边用等量的问号补齐，自然无法平衡。
if(suml==sumr){
if(l==r) cout<<"Bicarp";
else cout<<"Monocarp";
return 0;
}
情况二
既然开局两边不平衡，那么假如这时两边问号相等会怎么样？
(Monocarp)会在大的一边加(9)，(Bicarp)又在小的一边补(9)，由于问号数相等，最后左右的两边问号都用完了两边的数量差还是没变，因此(Monocarp)赢。
if(l==r){
cout<<"Monocarp";
return 0;
}
情况三
现在我们进行到左右大小不等，问号也不等的情况了，那么很容易想到两个分支，第一种是一边数大问号也多，另一种是一边数大但是问号少。情况三我们讨论第一种。
首先两个人左一个(9)右一个(9)把一边的问号消耗完了，但是两边数字差没有丝毫变化，这时只有数字大的一边有问号了，(Bicarp)无法在数小的一边补(9)填坑，无力回天，只可能是(Monocarp)赢。
if((sumr>suml&&r>l)||(suml>sumr&&l>r)){
cout<<"Monocarp";
return 0;
}
情况四
最后的最恶心的情况：一边数大但是问号少，另一边数少问号多。
首先肯定还是两个人一次左一次右把一边的(?)消完了，大的一边没问号了，只有小的有，也就是说我们可以把初始情况看成两边的差还是原来的差，但是只有小的一边有数量为(abs(l-r))个问号。这时两人会怎么做？显然(Monocarp)操作会把问号变为(0)尽力阻止小的一边扩张，而(Bicarp)会在还没有超越界限的前提下尽量补(9)让小的追上大的一边。也就是说每过一轮就消去两个问号，同时，差减九。
int a=abs(suml-sumr),b=abs(l-r);
while(1){
a-=9;
b-=2;
if(a<0||b<0) break;
}
a+=9; b+=2;
这时再分出两个情况：(b==1)和(b==0)。
若是(b)为一，则说明只剩一个问号了。由于前面都是偶数次消除，现在该(Monocarp)了，他可以随意加一个数反正只要不让和相等就行了，肯定赢。（这是我做的时候忽略了问号个数为偶数想到的情况，问号为偶数的话这应该是不成立的，但是反正加上也没事是吧那就加上吧）
若(b)为零，则说明两边都没问号了，谁都无法操作了，那我们就看两边平没平决胜负就行了。
if(!b){
if(a!=0) cout<<"Monocarp";
else cout<<"Bicarp";
}
else cout<<"Monocarp";
代码
把上面那一大堆拼起来就行。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=2000000+5;
char s[maxn];
int n,suml,sumr,l,r;
int main(){
cin>>n>>s+1;
for(int i=1;i<=n/2;i++){
if(s[i]!='?') suml+=s[i]-'0';
else l+=1;
}
for(int i=n/2+1;i<=n;i++){
if(s[i]!='?') sumr+=s[i]-'0';
else r+=1;
}
if(suml==sumr){
if(l==r) cout<<"Bicarp";
else cout<<"Monocarp";
return 0;
}
if(l==r){
cout<<"Monocarp";
return 0;
}
if((sumr>suml&&r>l)||(suml>sumr&&l>r)){
cout<<"Monocarp";
return 0;
}
int a=abs(suml-sumr),b=abs(l-r);
while(1){
a-=9;
b-=2;
if(a<0||b<0) break;
}
a+=9; b+=2;
if(!b){
if(a!=0) cout<<"Monocarp";
else cout<<"Bicarp";
}
else cout<<"Monocarp";
return 0;
}
尾声
大家可能会发现情况二三就是情况四的特殊情况，用情况四的代码稍作修改判断也可以，但是能提前结束谁想用到(while)呢？
幸甚至哉，歌以咏志。