I - Bob vs ATM(博弈论)-Toy模板网

这篇具有很好参考价值的文章主要介绍了I - Bob vs ATM(博弈论)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

传送门：nefu_10-18 - Virtual Judge (vjudge.net)

思路：

nim游戏的变形。

（（））相当于在一堆n个石子中取任意个，sg（n）=n;

((()))(())(),相当于可以在3堆石子分别为3，2，1个石子中取任意个sg函数值为：

sg(3)^sg(2)^sg(1);

对于（（）（）（（））），这样的，刨除外面一层，sg函数为sg(1)^sg(1)sg(2)=2;

我们可以把他等效成（（））【sg值一致】，整个就可以等效成（（（）））；

将整个序列等效成由（（））这样的括号组成，异或sg函数值即可。

具体操作时：

记录“（”的位置和对应“）”位置，然后solve(1,n)递归处理。

当l==r-1,说明是（）这种情况，返回1;

当p[l]==r,说明最外层是（），返回1+solve(l+1,r-1);

除上述情况返回solve(l, p[l]) ^ solve(p[l] + 1, r);

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e5 + 1000;
char s[N];
unordered_map<int, int> p;
stack<int>q;
int solve(int l,int r)
{
   /*cout << l <<" " << r << endl;*/
   if (r <= l) return 0;
   if (l == r - 1 && s[l] == '(' && s[r] == ')') return 1;
   if (p[l] == r) return 1 + solve(l + 1, r - 1);
   return solve(l, p[l]) ^ solve(p[l] + 1, r);
}
int main() {
   int T;
   cin >> T;
   while (T--)
   {
       cin >> s + 1;
       int len = strlen(s + 1);
       for (int i = 1; i <= len; i++)
       {
           if (s[i] == '(')
               q.push(i);
           else
           {
               p[q.top()] = i;
               q.pop();
           }
       }
       int ans = solve(1,len);
       /*cout << ans << endl;*/
       if (ans)
           printf("ATM\n");
       else
           printf("Bob\n");
       p.clear();
   }
   return 0;
}文章来源地址https://www.toymoban.com/news/detail-722484.html