专栏文章

题解：[ARC209A] Bracket Game

ddongzirui0817
AT_arc209_a题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minawtuf
此快照首次捕获于
2025/12/01 23:25
3 个月前
此快照最后确认于
2025/12/01 23:25
3 个月前
查看原文
好题，要挖的结论挺深的。
来看一堆结论。下面定义一个字符串是好的，当且仅当该字符串是个正确的括号序列。
当然如果大人您注意力惊人，那可以不用看结论了。
结论 11
Taro 发现字符串不好，他就赢了；Jiro 发现字符串是好的，他就赢了。
结论 22
当 Taro 得到的字符串是好的，那么他一定可以通过某种方式，使字符串变不好。
这也说明，Jiro 一直是被动方，因为 Taro 永远可以解除 Jiro 对他的威胁。
所以 Jiro 赢的方式只有一种：扛到最后。那么往这个方向去想即可，于是又有了以下结论。
结论 33
如果 ∣S∣−K|S|-K 为奇数，那么 Jiro 必输。
由结论 22 可推出 Jiro 最多顺利在 ∣S∣−K−12\frac{|S| - K-1}2 轮时把好的字符串扔给 Taro，如果不顺利直接就输了。但 Jiro 还是可以把不好的字符串再还回去，此时游戏刚好结束，Jiro 就输了。
结论 44
当 Taro 拿走了开头的 (，现在开头为 )，那么 Jiro 可以扛过去；当 Taro 拿走了末尾的 )，现在开头为 (，那么 Jiro 也可以扛过去。
比如 ()()()，Taro 拿走了开头，那么 Jiro 可以接着拿开头的 )，就扛过去了。
结论 55
当 Taro 手上的字符串中最短的好的前缀或后缀长度大于 22，且非本身，那么 Jiro 就输了。
比如样例的 Case 2：(())()。Taro 可以把开头的 ( 拿走，此时 Jiro 无言以对。
那么推导完成。
对于 SS，先判 ∣S∣−K|S|-K 是否为偶数，是奇数了话，由结论 33 得 Taro 赢。然后判字符串是不是好的，如果不好，由结论 11 得 Taro 赢。否则由结论 55，Taro 一定会尽可能得消出一个长度最短且好又不为本身的前（后）缀来把 Jiro 创飞。想消成这样，就要以最少轮数达成，即消 () 形式最少。
那么左右两边都消一下，然后选更优方案。如果消成结论 55 了，轮数又没达到 Taro 就赢了。如果发现消不出来，那 Jiro 赢。
否则就有两种情况：
  1. 已经是结论 55 的形式了，但左右两边均没为 () 的前缀和后缀。
  2. 被一对括号包起来的合法序列。
那么我们可以像 O(n)O(n) 求表达式的值一样来求。设 CiC_i 为最大的 jj 满足区间 (i,j)(i,j) 都被 ii 和 jj 包起来了。这可以用 ljl_j 表示最近的深度（括号包起它的对数）为 jj 的最大值辅助解决。
CPP
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][L, R]，如果 CR>LC_R>L 就是情况 11，反之为情况 22。
是情况 11 就结束了，如果是情况 22 就把括号拆了继续做下去，直到轮数达标，也就是 Jiro 扛过来了。
下面上代码。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...