【博弈论】CF 1215D Ticket Game
2024-10-10 00:56:42
题目大意
洛谷链接
给出一个长度为\(n\)的由数字组成的字符串(\(n\)是偶数)。但可能有偶数个位上的数字为?
。
现在有两个人\(A\)和\(B\),在?
的位置上填\(0\)~\(9\)的数,一直到填完。
让\(A\)先手,若最后该字符串的左半边数字和等于右半边数字和 ,则\(B\)胜利,否则\(A\)胜利。
样例输入
8
?054??0?
样例输出
Bicarp
PS:更多样例和数据范围请打开原题链接吧,实在懒得粘了orz
思路
简单分情况讨论一下就可了。
设左半部分数字和为\(x\),?
的个数为\(a\);右半部分数字和为\(y\),?
的个数为\(b\)。
- 若\(x=y\):
- 若\(a\not= b\),例如
100??919????
,\(A\)总能操作让最后不相等。因此这种情况\(A\)必胜。 - 若\(a=b\),例如
1??919??
,\(A\)填什么\(B\)就填什么就行了,因此这种情况\(B\)必胜。
- 若\(a\not= b\),例如
- 若\(x\not= y\),可设\(x>y\):
- 若\(a\ge 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\)赢。
- 若\(a\ge 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;
}
补充
取石子问题介绍(链接来自网络博客)
最新文章
- iframe跨域+
- ubuntu 创建用户
- Material Design学习
- getFragmentManager()和getSupportFragmentManager()
- linux命令每日一练习-mkdir,rm
- 安装chocolatey
- JS——JavaScript Confirm
- @ExceptionHandler
- JDBC连接MySQL数据库及示例
- Hadoop下各技术应用场景
- bootstrapUI
- ios学习之常见问题记录
- Java解决Hanoi问题
- 【Unity Shaders】Diffuse Shading——漫反射光照改善技巧
- web scraper 抓取网页数据的几个常见问题
- 3d
- 为什么wait()方法要放在同步块
- [c#]_ELVE_Message多功能用法
- js、jquery、jsp的区别
- Linux基础学习(1)--Linux系统简介