[CF1215D] Ticket Game

题目

原题链接

解说

前置

翻译什么的链接里已经说的很清楚了,这里不再赘述,看题吧。

一看见这博弈论模样的题就知道又是思维题了。

设身处地想一想,假如你是游戏里的人你会怎么让自己赢。首先,开局时左右两边数字和肯定有一个大小关系,假如我是\(Monocarp\),我先手,我肯定会在大的一边把\(?\)改成\(9\)以拉大差距,而接下来的\(Bicarp\)最好的策略就是先在小的一边把\(?\)改成\(9\)补回差距。

基本战略确定了,接下来就能讨论了。

根据上面的推论,我们基本可以确定首先要统计两边开局的数字和以及问号个数。

	cin>>n>>s+1;
	for(int i=1;i<=n/2;i++){
		if(s[i]!='?') suml+=s[i]-'0';
		else l+=1;
	}
	for(int i=n/2+1;i<=n;i++){
		if(s[i]!='?') sumr+=s[i]-'0';
		else r+=1;
	}

P.S. 下面说明情况都是在排除了已经给出的情况之后。

情况一

我能想到的最简单情况就是两边开局就相等,这时只有两边问号也相等\(Bicarp\)才能胜利。为什么?显然问号不相等的话\(Monocarp\)在一边加了数\(Bicarp\)无法在另一边用等量的问号补齐,自然无法平衡。

	if(suml==sumr){
		if(l==r) cout<<"Bicarp";
		else cout<<"Monocarp";
		return 0;
	}

情况二

既然开局两边不平衡,那么假如这时两边问号相等会怎么样?

\(Monocarp\)会在大的一边加\(9\),\(Bicarp\)又在小的一边补\(9\),由于问号数相等,最后左右的两边问号都用完了两边的数量差还是没变,因此\(Monocarp\)赢。

	if(l==r){
		cout<<"Monocarp";
		return 0;
	}

情况三

现在我们进行到左右大小不等,问号也不等的情况了,那么很容易想到两个分支,第一种是一边数大问号也多,另一种是一边数大但是问号少。情况三我们讨论第一种。

首先两个人左一个\(9\)右一个\(9\)把一边的问号消耗完了,但是两边数字差没有丝毫变化,这时只有数字大的一边有问号了,\(Bicarp\)无法在数小的一边补\(9\)填坑,无力回天,只可能是\(Monocarp\)赢。

	if((sumr>suml&&r>l)||(suml>sumr&&l>r)){
		cout<<"Monocarp";
		return 0;
	}

情况四

最后的最恶心的情况:一边数大但是问号少,另一边数少问号多。

首先肯定还是两个人一次左一次右把一边的\(?\)消完了,大的一边没问号了,只有小的有,也就是说我们可以把初始情况看成两边的差还是原来的差,但是只有小的一边有数量为\(abs(l-r)\)个问号。这时两人会怎么做?显然\(Monocarp\)操作会把问号变为\(0\)尽力阻止小的一边扩张,而\(Bicarp\)会在还没有超越界限的前提下尽量补\(9\)让小的追上大的一边。也就是说每过一轮就消去两个问号,同时,差减九。

	int a=abs(suml-sumr),b=abs(l-r);
	while(1){
		a-=9;
		b-=2;
		if(a<0||b<0) break;
	}
	a+=9; b+=2;

这时再分出两个情况:\(b==1\)和\(b==0\)。

若是\(b\)为一,则说明只剩一个问号了。由于前面都是偶数次消除,现在该\(Monocarp\)了,他可以随意加一个数反正只要不让和相等就行了,肯定赢。(这是我做的时候忽略了问号个数为偶数想到的情况,问号为偶数的话这应该是不成立的,但是反正加上也没事是吧那就加上吧)

若\(b\)为零,则说明两边都没问号了,谁都无法操作了,那我们就看两边平没平决胜负就行了。

	if(!b){
		if(a!=0) cout<<"Monocarp";
		else cout<<"Bicarp";
	}
	else cout<<"Monocarp";

代码

把上面那一大堆拼起来就行。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=2000000+5;
char s[maxn];
int n,suml,sumr,l,r;
int main(){
	cin>>n>>s+1;
	for(int i=1;i<=n/2;i++){
		if(s[i]!='?') suml+=s[i]-'0';
		else l+=1;
	}
	for(int i=n/2+1;i<=n;i++){
		if(s[i]!='?') sumr+=s[i]-'0';
		else r+=1;
	}
	if(suml==sumr){
		if(l==r) cout<<"Bicarp";
		else cout<<"Monocarp";
		return 0;
	}
	if(l==r){
		cout<<"Monocarp";
		return 0;
	}
	if((sumr>suml&&r>l)||(suml>sumr&&l>r)){
		cout<<"Monocarp";
		return 0;
	}
	int a=abs(suml-sumr),b=abs(l-r);
	while(1){
		a-=9;
		b-=2;
		if(a<0||b<0) break;
	}
	a+=9; b+=2;
	if(!b){
		if(a!=0) cout<<"Monocarp";
		else cout<<"Bicarp";
	}
	else cout<<"Monocarp";
	return 0;
}

尾声

大家可能会发现情况二三就是情况四的特殊情况,用情况四的代码稍作修改判断也可以,但是能提前结束谁想用到\(while\)呢?

幸甚至哉,歌以咏志。

上一篇:luogu P7619 [COCI2011-2012#2] RASPORED


下一篇:动态规划——NC19. 子数组的最大累加和问题