题目链接:
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("%dn",&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("bicarpn"); else printf("monocarpn"); return 0; } if(s1==s2){ if(w1==w2)printf("bicarpn"); else printf("monocarpn"); return 0; } if(s1>s2){swap(s1,s2);swap(w1,w2);} if(w1<=w2){ printf("monocarpn"); return 0; } else{ w1-=w2; if(w1%2==0){ if(s1+(w1/2)*9==s2)printf("bicarpn"); else printf("monocarpn"); }else{ printf("monocarpn"); } } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599709.html