题目
解说
前置
翻译什么的链接里已经说的很清楚了,这里不再赘述,看题吧。
一看见这博弈论模样的题就知道又是思维题了。
设身处地想一想,假如你是游戏里的人你会怎么让自己赢。首先,开局时左右两边数字和肯定有一个大小关系,假如我是\(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\)呢?
幸甚至哉,歌以咏志。