首页 > > 程序设计 > C/C++ >

CF1215DTicketGame——（博弈）

2020-04-25 16:00:27来源：博客园阅读 ()

CF1215DTicketGame——（博弈）

题目链接：
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.cnblogs.com/Lour688/p/12767346.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有