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;
}