欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CF1215DTicketGame——(博弈)

程序员文章站 2022-07-10 21:18:43
题目链接: https://www.luogu.com.cn/problem/CF1215D 题意: 一张票有n位数,如果这张票的前一半数字的和等于后一半数字的和(n一定是偶数),就称这张票为快乐票。有些数被擦除了,标记为’?’(’?‘的个数也是偶数),现在Monocarp 和 Bicarp 进行一 ......

题目链接:
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;
}