easy version 传送门
hard version 传送门
题意:
给定一个由0和1组成的字符串,进行如下两种操作;
(简单问题版本中字符串为回文串)
;Alice先手;
思路:
首先是简单版本,统计0的个数
Alice先手破坏回文串,Bob修补成为回文串······当剩下两个0的时候,Alice破坏回文串,Bob进行翻转,剩下的一个0,Alice修补,
这样Alice比Bob多花了2代价,Bob必胜;注意当0的个数为1时Alice花费1代价,Bob花费0,则Bob胜
;接下来是困难版本
不是回文的地方的个数为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; }