Codeforces Round #721 (Div. 2) B. Palindrome Game (easy and hard version) （思维 + 简单博弈）

本文主要是介绍Codeforces Round #721 (Div. 2) B. Palindrome Game (easy and hard version) （思维 + 简单博弈），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

easy version 传送门
hard version 传送门

题意：

给定一个由0和1组成的字符串，进行如下两种操作；

• 将0变为1，花费1代价；
• 如果字符串不是回文串，则选手可以进行一次翻转，花费0代价（简单问题版本中字符串为回文串）；

Alice先手；

思路：

首先是简单版本，统计0的个数

• 0的个数为偶数，Alice先手破坏回文串，Bob修补成为回文串······当剩下两个0的时候，Alice破坏回文串，Bob进行翻转，剩下的一个0，Alice修补，这样Alice比Bob多花了2代价，Bob必胜；
• 0的个数为奇数，Alice只要将字符串变为回文串，接下来和偶数情形一样，只不过先手变成Bob，所以Alice必胜 注意当0的个数为1时Alice花费1代价，Bob花费0，则Bob胜；

接下来是困难版本

• 如果是回文串，则按简单版本处理
• 如果不是，只需要统计字符串中不是回文的地方的个数和0的数量，只有不是回文的地方的个数为1且0的个数为2时，例：10011，这种情况是会打成平局的，其余情况，Alice胜；

Code：

简单版本

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <map>
#include <vector>
#include <set>
#include <iomanip>
#define hz020 return
#define mes memset
#define mec memcpy

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>pii;

const int N = 200010;
const int null = 0x3f3f3f3f,INF = 1e9;
const ll mod = 998244353;

int T;
int n;

ll gcd(ll a,ll b)
{
	return b ? gcd(b,a % b) : a;
}

int main()
{
	cin >> T;
	while(T --)
	{
		cin >> n;
		string s;
		cin >> s;
		int cnt = 0;
		for(int i = 0;i < s.size();i ++)
		{
			if(s[i] == '0') cnt ++;
		}
	
		if(!(cnt % 2) || cnt == 1) puts("BOB");
		else puts("ALICE");
	
	} 
	
	hz020 0;
}  

困难版本

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <map>
#include <vector>
#include <set>
#include <iomanip>
#define hz020 return
#define mes memset
#define mec memcpy

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>pii;

const int N = 200010;
const int null = 0x3f3f3f3f,INF = 1e9;
const ll mod = 998244353;

int T;
int n;

ll gcd(ll a,ll b)
{
	return b ? gcd(b,a % b) : a;
}

int main()
{
	cin >> T;
	while(T --)
	{
		cin >> n;
		string s;
		cin >> s;
		int cnt = 0;
		int flag = 0;
		
		int i = 0,j = n - 1;
		
		while(i < j)
		{
			if(s[i] != s[j]) flag ++;
			
			if(s[i] == '0') cnt ++;
			if(s[j] == '0') cnt ++;
			
			i ++,j --;
		}

		if(s[n / 2] == '0' && (n % 2)) cnt ++;
	
		
		if(!flag)
		{
			if(!(cnt % 2) || cnt == 1) puts("BOB");
			else puts("ALICE");
		}
		else
		{
			if(flag == 1 && cnt == 2) puts("DRAW");
			else puts("ALICE");
		}
	} 
	
	hz020 0;
}  

这篇关于Codeforces Round #721 (Div. 2) B. Palindrome Game (easy and hard version) （思维 + 简单博弈）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！