[ARC209A] Bracket Game

Genius_Star · 2026-08-08 16:56:29 · 题解

简单手玩题。

思路：

显然，如果刚开始 S 都不是合法括号串，先手可以直接宣布结束获得胜利；同理，如果最后 k 是奇数，后手永远收到的是奇数位，不可能胜利。

对于一般的情况，初始是合法的，k 是偶数，因为任意一方有宣告比赛结束的权力，所以游戏一定是：

• 合法，不合法，合法，不合法……

这样交替下去的，看起来先手特别牛逼，每次删一个后后手都需要存在一个删的方法使得合法，手玩一下：

• 如果 S 是 (S')：先手怎么删，后面删另外一边依旧合法。

• 如果 S 是 ()\cdots()(S')：先手删最右边那个，后手不可能合法。

• 如果 S 是 ()\cdots()(S')()\cdots()：先手肯定是找一个策略，从一边开始一直往里删，直到撞到了 (S')；所以显然是找一边 () 最少的删过去。

那么这题就解决了，先手策略一定是先把第一种情况删完，变成第三种情况，选择一边一直删进去成为第二种情况后字符串不合法直接宣告胜利。

那么输的情况，显然就是在第一和第三种情况删的途中长度变为 k 了，求出具体删的数量，和 k 比大小即可。

时间复杂度为 O(n)。

完整代码：

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define add(x, y) ((x + y >= mod) ? (x + y - mod) : (x + y))
#define dec(x, y) ((x - y < 0) ? (x - y + mod) : (x - y))
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e6 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}   
int T, n, k;
int pre[N];
char s[N];
inline void solve(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    k = read();
    if(n & 1){
        puts("First");
        return ;
    }
    stack<int> stk;
    int sum = 0;
    for(int i = 1; i <= n; ++i){
        if(s[i] == '(')
          ++sum, stk.push(i);
        else{
            if(stk.empty()){
                puts("First");
                return ;
            }
            --sum, pre[i] = stk.top(), stk.pop();
        }
        if(sum < 0){
            puts("First");
            return ;
        }
    }
    if(sum != 0){
        puts("First");
        return ;
    }
    if(k & 1){
        puts("First");
        return ;
    }
    int l = 1, r = n, t =0 ;
    for(int i = n; i >= 1 && l <= r; --i){
        if(s[i] == ')' && pre[i] == n - i + 1)
          ++l, -- r, t += 2;
        else
          break;
    }
    if(l > r){
        puts("Second");
        return ;
    }
    int mn = 1e9;
    for(int i = l; i <= r; i += 2){
        if(s[i] == s[i + 1]){
            mn = min(mn, (i - l));
            break;
        }
    }
    for(int i = r; i >= l; i -= 2){
        if(s[i] == s[i - 1]){
            mn = min(r - i, mn);
            break;
        }
    }
    if(n - t - mn <= k)
      puts("Second");
    else
      puts("First");
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}