题解：[ARC209A] Bracket Game

dongzirui0817 · 2025-11-09 22:04:41 · 题解

好题，要挖的结论挺深的。

来看一堆结论。下面定义一个字符串是好的，当且仅当该字符串是个正确的括号序列。

当然如果大人您注意力惊人，那可以不用看结论了。

::::info[结论 1]{open} Taro 发现字符串不好，他就赢了；Jiro 发现字符串是好的，他就赢了。 ::::

::::info[结论 2]{open} 当 Taro 得到的字符串是好的，那么他一定可以通过某种方式，使字符串变不好。
这也说明，Jiro 一直是被动方，因为 Taro 永远可以解除 Jiro 对他的威胁。 ::::

所以 Jiro 赢的方式只有一种：扛到最后。那么往这个方向去想即可，于是又有了以下结论。

::::info[结论 3]{open} 如果 $	S	-K 为奇数，那么 Jiro 必输。由结论 2 可推出 Jiro 最多顺利在 \frac{	S	- K-1}2$ 轮时把好的字符串扔给 Taro，如果不顺利直接就输了。但 Jiro 还是可以把不好的字符串再还回去，此时游戏刚好结束，Jiro 就输了。

::::info[结论 4]{open} 当 Taro 拿走了开头的 (，现在开头为 )，那么 Jiro 可以扛过去；当 Taro 拿走了末尾的 )，现在开头为 (，那么 Jiro 也可以扛过去。
比如 ()()()，Taro 拿走了开头，那么 Jiro 可以接着拿开头的 )，就扛过去了。 ::::

::::info[结论 5]{open} 当 Taro 手上的字符串中最短的好的前缀或后缀长度大于 2，且非本身，那么 Jiro 就输了。
比如样例的 Case 2：(())()。Taro 可以把开头的 ( 拿走，此时 Jiro 无言以对。 ::::

那么推导完成。

对于 S，先判 |S|-K 是否为偶数，是奇数了话，由结论 3 得 Taro 赢。然后判字符串是不是好的，如果不好，由结论 1 得 Taro 赢。否则由结论 5，Taro 一定会尽可能得消出一个长度最短且好又不为本身的前（后）缀来把 Jiro 创飞。想消成这样，就要以最少轮数达成，即消 () 形式最少。

那么左右两边都消一下，然后选更优方案。如果消成结论 5 了，轮数又没达到 Taro 就赢了。如果发现消不出来，那 Jiro 赢。

否则就有两种情况：

已经是结论 5 的形式了，但左右两边均没为 () 的前缀和后缀。
被一对括号包起来的合法序列。

那么我们可以像 O(n) 求表达式的值一样来求。设 C_i 为最大的 j 满足区间 (i,j) 都被 i 和 j 包起来了。这可以用 l_j 表示最近的深度（括号包起它的对数）为 j 的最大值辅助解决。

int cnt = 0;
for (int i = 1 ; i <= n ; i++) l[i] = -1;
l[0] = 0;
for (int i = 1 ; i <= n ; i++) {
    if (s[i] == '(') ++cnt;
    else {
        --cnt;
        if (cnt < 0) break;
    }
    c[i] = l[cnt] + 1, l[cnt] = i;
}

那么对于上述的两种情况对应的区间 [L, R]，如果 C_R>L 就是情况 1，反之为情况 2。

是情况 1 就结束了，如果是情况 2 就把括号拆了继续做下去，直到轮数达标，也就是 Jiro 扛过来了。

下面上代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int T, k;
string s;
int l[1000010], c[1000010];

int main() {
    cin >> T;
    for ( ; T-- ; ) {
        cin >> s >> k;
        s = " " + s;
        int n = s.size() - 1;
        if ((n - k) % 2 || n % 2) puts("First");
        // 如果 (n - k) % 2 == 1，那么 Taro 胜。n % 2 == 1 纯粹是让代码跑更快。
        else {
            int cnt = 0;
            for (int i = 1 ; i <= n ; i++) l[i] = -1;
            l[0] = 0;
            for (int i = 1 ; i <= n ; i++) {
                if (s[i] == '(') ++cnt;
                else {
                    --cnt;
                    if (cnt < 0) break;
                }
                c[i] = l[cnt] + 1, l[cnt] = i;
            }

            if (cnt) puts("First"); // 非合法括号序列
            else {
                int front = 1, rear = n;
                int i = 0;
                for ( ; i < (n - k) / 2 ; ) {
                    int L = front, R = rear;
                    int u = 0, v = 0;
                    while (L + 1 <= R && s[L] == '(' && s[L + 1] == ')')
                        L += 2, ++u;    // 把左边的 () 全拆下来
                    if (L >= R) {   // 如果全是 ()
                        i = (n - k) / 2;
                        break;
                    }
                    while (s[R - 1] == '(' && s[R] == ')')
                        R -= 2, ++v;    // 把右边的 () 全拆下来
                    if (u < v) front = L, i += u;   // 取最小值
                    else rear = R, i += v;
                    if (i >= (n - k) / 2) break;
                    if (u || v) break;  // 如果左右至少有一个 ()
                    if (c[rear] != front) break;    // 情况 1
                    while (i < (n - k) / 2 && front < rear && c[rear] == front)
                        ++i, ++front, --rear;   // 拆包着的括号
                }
                if (i >= (n - k) / 2) puts("Second");
                else puts("First");
            }
        }
    }
    return 0;
}