题目地址:不放了,网页加载不出来。
题目:
Bicarp和Monocarp玩游戏,长度为n(n为偶数)的字符串,其中有偶数个?,每次选择0-9中的一个数替换?,Monocarp先开始,若最终前n/2位上数字和与后n/2位上的数字和相同,Bicarp赢,否则Monocarp赢。
解题思路:
num1,sum1记录前n/2位上的?数目和初始数字和,num2,sum2记录后n/2位上的?数目和初始数字和。
考虑何时Bicarp可以赢。
(1)sum1=sum2,那么必定num1=num2方可。
(2)sum1>sum2,为了让前后数字和相同,定有num2>num1,其中num2中的num1位上所填的数字对结果无影响,因为每次Monocarp填一个数之后Bicarp可以和他填相同的数,剩下的num2-num1个数(偶数),Bicarp可填的位数为(num2-num1)/2,且当sum1-sum2=(num2-num1)/2*9时Bicarp才会赢。(因为当sum1-sum2=(num2-num1)/2*9时,无论Monocarp填什么,Bicarp总能随后再填一个数,使得这两个数之和=9,否则Monocarp总能有办法赢)
(3)sum2>sum1和(2)同理
ac代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
char s[maxn];
int main()
{
int n, num1 = 0, num2 = 0, sum1 = 0, sum2 = 0;
scanf("%d", &n);
scanf("%s",s+1);
for(int i = 1; i <= n; i++)
{
if(i <= n/2)
{
if(s[i] == '?') num1++;
else sum1 += s[i]-'0';
}
else
{
if(s[i] == '?') num2++;
else sum2 += s[i]-'0';
}
}
bool flag = false;
if(num1 == num2 && sum1 == sum2) flag = true;
else if(sum1 > sum2 && sum1 - sum2 == (num2-num1)/2*9) flag = true;
else if(sum2 > sum1 && sum2 - sum1 == (num1-num2)/2*9) flag = true;
if(flag) printf("Bicarp");
else printf("Monocarp");
return 0;
}