P14688 [ICPC 2025 Yokohama R] Game of Names

Alice 和 Bob 正在一个单行、有一定数量格子的棋盘上玩游戏。一些格子（可能为零）中写有玩家的名字，要么是 "Alice"，要么是 "Bob"。其他格子最初是空白的。 游戏从 Alice 开始，两位玩家轮流操作。在一次操作中，轮到行动的玩家选择一个空白格子，该格子不能与写有该玩家自己名字的格子相邻，然后在该选定的空白格子中写下自己的名字。请注意，相邻格子中对手的名字没有影响。 无法进行操作的玩家输掉游戏。给定棋盘的初始状态，确定当 Alice 和 Bob 都采取最优策略时，谁会获胜。

输入包含一个或多个测试用例。输入的第一行包含一个整数 $t$ ($1 \le t \le 2 \times 10^5$)，表示测试用例的数量。接下来是 $t$ 个测试用例的描述，每个用例的格式如下。 $$ n $$ $$ s $$ 整数 $n$ 表示棋盘上的格子数量 ($1 \le n \le 2 \times 10^5$)。棋盘的初始状态由一个长度为 $n$ 的字符串 $s$ 给出。 对于每个 $i$ ($1 \le i \le n$)，$s$ 的第 $i$ 个字符 $s_i$ 是 'a'、'b' 或 '.' 之一，表示从左数第 $i$ 个格子的初始状态。其中，如果第 $i$ 个格子包含名字 Alice，则 $s_i$ 为 'a'；如果包含名字 Bob，则为 'b'；如果是空白，则为 '.'。 保证初始棋盘不会包含两个相邻且名字相同的格子。 所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一行：如果 Alice 获胜则输出 alice，如果 Bob 获胜则输出 bob。

翻译由 DeepSeek V3 完成