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的数量,只有不是回文的地方的个数为10的个数为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;
}  
上一篇:306. Check If Linked List Is Palindrome


下一篇:算法: 验证回文680. Valid Palindrome II