题目详情题解（0）讨论（0）提交记录（0）

AT_arc209_a.[ARC209A] Bracket Game

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个只由 ( 和 ) 组成的字符串 SS。

太郎和次郎将用这个字符串玩如下的游戏。

太郎先手，次郎后手，他们轮流选择并进行以下三种操作之一：

  • 删除 SS 的第一个字符。
  • 删除 SS 的最后一个字符。
  • 宣告终止。

当 SS 的长度恰好变为 KK，或有任意一方宣告终止时，游戏结束。游戏结束时，若 SS 是一个合法括号序列，则次郎获胜；否则，太郎获胜。

在游戏开始前，你会得到 SS。请你判断当双方都采取最优策略时，谁会获胜。

你需要完成 TT 组测试，每组分别求解。

什么是一个合法括号序列？只要把字符串中连续的 () 作为一个子串删去，反复多次能将整个字符串删成空串，就认为它是一个合法括号序列。

输入格式

从标准输入读入，输入格式如下：

TT
case1case_1
case2case_2
⋮\vdots
caseTcase_T

每组测试数据格式如下：

SS KK

输出格式

对于每组测试数据，如果太郎获胜则输出 First，如果次郎获胜则输出 Second。

输入输出样例

  • 输入#1

    4
(()())
2
(())()
2
(()
2
(()()())((()()(())()))
12

    输出#1

    Second
First
First
First

说明/提示

样例解释 1

对于第一组测试数据，游戏可能的过程如下：

  • 游戏开始前，SS 为 (()())。
  • 太郎删除 SS 的第一个字符，变为 ()())。
  • 接下来，次郎删除 SS 的最后一个字符，变为 ()()。
  • 然后，太郎删除 SS 的最后一个字符，变为 ()(。
  • 接下来，次郎删除 SS 的最后一个字符，变为 ()，此时 SS 的长度变为 K=2K=2，游戏结束。
  • 最终 SS 是一个合法括号序列，所以次郎获胜。

再比如，对于第三组测试数据，太郎可以在第一轮直接宣告终止获胜。

数据范围

  • 1≤T≤1051 \le T \le 10^5
  • 1≤K<∣S∣≤1061 \le K < |S| \le 10^6
  • SS 是只包含 ( 和 ) 的字符串。
  • TT 和 KK 是整数。
  • 所有测试数据的 ∣S∣|S| 之和不超过 10610^6。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页