A16879. A Bit Odd
编程题
入门
知识点
题目描述
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}$。
在每一轮中，当前玩家必须选择一个具有奇数个逆序对$^{\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$。
每个测试用例的第一行包含一个整数 $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
3 5 10101 4 0100 6 011001
输出 #1
Alice Alice Bob
说明/提示
对于第一个测试用例，Alice 可以选择整个字符串，因为该字符串具有奇数个逆序对。此时 Bob 面对的是一个空字符串，无法进行任何操作。因此 Alice 获胜。
对于第二个测试用例，Alice 可以选择由下标 $1$、$2$ 和 $4$ 处的字符构成的子序列，即 $\texttt{010}$。此时 Bob 剩余的字符为下标 $3$ 处的 $\texttt{0}$，其逆序对数量为 $0$（偶数）。因此 Bob 无法选出一个具有奇数个逆序对的子序列，故 Alice 获胜。
对于第三个测试用例，可以证明：无论 Alice 的第一步如何操作，Bob 均能确保获胜。
对于第二个测试用例，Alice 可以选择由下标 $1$、$2$ 和 $4$ 处的字符构成的子序列，即 $\texttt{010}$。此时 Bob 剩余的字符为下标 $3$ 处的 $\texttt{0}$，其逆序对数量为 $0$（偶数）。因此 Bob 无法选出一个具有奇数个逆序对的子序列，故 Alice 获胜。
对于第三个测试用例，可以证明：无论 Alice 的第一步如何操作，Bob 均能确保获胜。