題目鏈接：
https://www.luogu.com.cn/problem/CF1215D
題意：
一張票有n位數，如果這張票的前一半數字的和等于后一半數字的和(n一定是偶數)，就稱這張票為快樂票，有些數被擦除了，標記為’?’(’?‘的個數也是偶數)，現在Monocarp 和 Bicarp 進行一個游戲，兩人輪流將’?'變換成0到9的任意一個數，Monocarp先手，如果最后票為快樂票則Bicarp贏，否則Monocarp贏，
分析
我們將左邊右邊的和設為\(s_1,s_2\),左邊右邊的"?"個數設為\(w_1,w_2\);
分情況：
\(if(s_1=s_2)\)
? ①\(w_1=w_2\) 后手在先手另一邊保持與先手出相同的即可，后手勝，
? ②\(w_1!=w_2\) 和上面情況一樣，后手出完他這邊?時，\(s_1\)仍等于\(s_2\).然后只能向一邊放數，該先手出了，先手必勝，
$if(s_1<s_2) \([如果\)s_1>s_2\(就分別把\)s_1和s_2,w_1和w_2$換位置]
? ①\(w_1<=w_2\) 先手往大的\(s_2\)上加數，后手永遠無法補齊\(s_1\),先手勝，
? ②\(w_1>w_2\)
? 先手先盡可能地將\(s_2\)變大，每次加9，后手每次給\(s_1\)加9,縮小差距，最后先手耗盡\(w_2\),接著先手與后手一起加\(s_1\),先手肯定不讓\(s_1\)變大，后手盡可能地讓\(s_1\)變大，加9，即現在每耗2個\(w_1\),\(s_1\)就加上1個9，這也是后手現在唯一能控制定量增長的，即每出兩次加上定值9，若最后后手恰好用完\(w_1\)（也就是當初耗完\(w_2\)時，\(w_1\)是偶數）時，\(s_1=s_2\)了，后手勝；
? 否則（當初耗完\(w_2\)時\(w_1\)是偶數但最后\(s_1!=s_2\) 或者 \(w_1\)是奇數，是奇數的話，最后一次是先手出，他一定可以選一個不讓左右相等的數）先手勝，
代碼
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int s1,s2,w1,w2,n;
char x;
void Swap(int &a,int &b){
int c=a;a=b;b=c;
}
int main(){
// freopen("1.in","r",stdin);
scanf("%d\n",&n);
for(int i=1;i<=n/2;++i){
scanf("%c",&x);
if(x>='0'&&x<='9')s1+=(x-'0');
else w1++;
}
for(int i=(n/2)+1;i<=n;++i){
scanf("%c",&x);
if(x>='0'&&x<='9')s2+=(x-'0');
else w2++;
}
if(w1+w2==0){
if(s1==s2)printf("Bicarp\n");
else printf("Monocarp\n");
return 0;
}
if(s1==s2){
if(w1==w2)printf("Bicarp\n");
else printf("Monocarp\n");
return 0;
}
if(s1>s2){Swap(s1,s2);Swap(w1,w2);}
if(w1<=w2){
printf("Monocarp\n");
return 0;
}
else{
w1-=w2;
if(w1%2==0){
if(s1+(w1/2)*9==s2)printf("Bicarp\n");
else printf("Monocarp\n");
}else{
printf("Monocarp\n");
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/33439.html
標籤：C++
下一篇：博弈--巴什博弈