A16879 · A Bit Odd · GESP考级

题目描述

Alice 和 Bob 得到了一个长度为 $n$ 的二进制$^{\text{∗}}$字符串 $s$。他们决定在该字符串上进行一场游戏，轮流进行，Alice 先手。 在每一轮中，当前玩家必须选择一个具有奇数个逆序对$^{\text{‡}}$的子序列$^{\text{†}}$并将其删除。无法进行操作的玩家判负。 假设双方均以最优策略进行游戏，请判断谁将获胜。 $^{\text{∗}}$ 二进制字符串是指仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成的字符串。 $^{\text{†}}$ 序列 $a$ 是字符串 $b$ 的子序列，当且仅当 $a$ 可通过从 $b$ 中删除若干（可能为零个或全部）字符得到。 $^{\text{‡}}$ 二进制字符串 $s$ 中的一个逆序对是指一对下标 $(i, j)$，满足 $i \lt j$，且 $s_i = \texttt{1}$、$s_j = \texttt{0}$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。接下来依次描述每个测试用例。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$）—— 二进制字符串 $s$ 的长度。 每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。保证 $s$ 中每个字符均为 $\texttt{0}$ 或 $\texttt{1}$。 保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。

对于每个测试用例，如果 Alice 获胜则输出 $\texttt{Alice}$，否则输出 $\texttt{Bob}$。

输入 #1

输出 #1

Alice
Alice
Bob