CF2241F A Bit Odd

Alice 和 Bob 获得了一个长度为 $n$ 的二进制字符串 $s$。他们决定以此字符串玩一个游戏，轮流操作，Alice 先手。 每一步中，玩家必须选择一个逆序对数为奇数的子序列，并将其删除。无法进行操作的玩家判负。 请你判断，设双方都采取最优策略，谁将赢得比赛。 $^*$ 二进制字符串是指只由字符 $0$ 和 $1$ 组成的字符串。 $^\dagger$ 如果序列 $a$ 可以通过从字符串 $b$ 中删除若干（可能是零个或全部）字符得到，则称 $a$ 是 $b$ 的一个子序列。 $^\ddagger$ 在二进制字符串 $s$ 中，逆序对指的是满足 $i < j$ 且 $s_i = 1$ 且 $s_j = 0$ 的一对下标 $(i, j)$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。每组测试用例的描述如下。 每组第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），为二进制字符串 $s$ 的长度。 每组第二行包含一个长度为 $n$ 的二进制字符串 $s$。保证 $s$ 的每个字符都是 $0$ 或 $1$。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每组测试用例，如果 Alice 能赢输出 $\texttt{Alice}$，否则输出 $\texttt{Bob}$。

对于第一个测试用例，Alice 可以选择整个字符串，因为其逆序对数为奇数。此时 Bob 面对空串，无法进行操作。因此 Alice 胜。 对于第二个测试用例，Alice 可以选择下标为 $1$、$2$ 和 $4$ 的字符组成的子序列 $010$。Bob 只剩下下标 $3$ 的字符 $0$，逆序对数为 $0$（偶数）。因此 Bob 不能再选出逆序奇数的子序列，Alice 获胜。 对于第三个测试用例，可以证明无论 Alice 如何操作，Bob 都能保证获胜。 由 ChatGPT 5 翻译