题目大意
洛谷链接
给出一个长度为(n)的由数字组成的字符串((n)是偶数)。但可能有偶数个位上的数字为?
。
现在有两个人(A)和(B),在?
的位置上填(0)~(9)的数,一直到填完。
让(A)先手,若最后该字符串的左半边数字和等于右半边数字和 ,则(B)胜利,否则(A)胜利。
样例输入
8
?054??0?
样例输出
Bicarp
PS:更多样例和数据范围请打开原题链接吧,实在懒得粘了orz
思路
简单分情况讨论一下就可了。
设左半部分数字和为(x),?
的个数为(a);右半部分数字和为(y),?
的个数为(b)。
- 若(x=y):
- 若(a
ot= b),例如
100??919????
,(A)总能操作让最后不相等。因此这种情况(A)必胜。 - 若(a=b),例如
1??919??
,(A)填什么(B)就填什么就行了,因此这种情况(B)必胜。
- 若(a
ot= b),例如
- 若(x
ot= y),可设(x>y):
- 若(age b),例如
??9??111??
,(A)可以直接一直在左半部分放9,这样右半部分永远也不可能和左半部分相等。因此这种情况(A)必胜。 - 若(a<b),例如
?054??0?
,前(a)个回合肯定是(A)一直在左半部分放9,(B)则维持平衡,则变成了90549?0?
。此时两边的差为9,则(A)放任意一个数,(B)放另外一个相加得9的就可以了,例如90549801
。但是比如?053??0?
或者?055??0?
,此时的(x-y)并不是9的倍数,分别可以改为9053990?
和9055900?
,(B)就GG了。这就类似一个取石子问题,如果(x-y)是9的先手的步数倍(刚好可以补齐足够的9,当然(x-y)太大也不行),并且(b-a)是偶数(保证前(a)个回合后(B)先开始),那么就(B)赢,否则就是(A)赢。
- 若(age b),例如
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const char PlayerA[10]={"Monocarp"};
const char PlayerB[10]={"Bicarp"};
int n;
char s[maxn];
int x,y,a,b;
int main(){
scanf("%d",&n);
scanf("%s",s+1);//个人习惯从1开始,当然也可以从0开始(的异世界生活)
for(int i=1; i<=n/2; i++){
if(s[i]=='?')a++;
else x+=s[i]-'0';
}
for(int i=n/2+1; i<=n; i++){
if(s[i]=='?')b++;
else y+=s[i]-'0';
}
if(x<y){//如果是小于直接调换一下左右就行了
swap(x,y);
swap(a,b);
}
if(x==y)
puts(a==b ? PlayerB : PlayerA);
else{
if(a>=b)puts(PlayerA);
else puts(((b-a)%2==0&&x-y==(b-a)/2*9) ? PlayerB : PlayerA);
}
return 0;
}
补充
取石子问题介绍(链接来自网络博客)