QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 8224. Caught in the Middle

统计

给定一个长度为 $n$ 的仅包含 '$\texttt{L}$','$\texttt{R}$' 的字符串 $s$. Alice, Bob 打算使用字符串进行一次游戏。

Alice 和 Bob 会轮流对字符串 $s$ 进行操作,Alice 先手。

每次操作时,假定当前剩余字符串为 $s$。如果 $s$ 为空串,则此时操作者输掉游戏。否则操作者可以从 $\{1,2,\cdots,|s|\}$ 中选择整数 $i$。 如果 $s_i = \texttt{'L'}$,则操作后剩余字符串为 $s_{1}s_{2}\cdots s_{i-1}$;如果 $s_i = \texttt{'R'}$,则操作后剩余字符串为 $s_{i+1}s_{i+2}\cdots s_{|s|}$。

两个人都绝顶聪明,因此他们都总会采用最优的策略。而你,一个参加 PKUWC 的普通吃瓜群众,想要知道这场游戏的胜者。

输入格式

第一行一个正整数 $T$, 表示数据组数。

对于每一组测试数据:

第一行一个正整数 $n$。

第二行一个长度为 $n$ 的仅包含 '$\texttt{L}$','$\texttt{R}$' 的字符串 $s$,表示游戏初始字符串。

输出格式

对于每组测试数据,输出一行 AliceBob, 表示游戏胜者。

样例数据

样例输入

3
5
LRLLR
6
RLRLRL
1
L

样例输出

Alice
Bob
Alice

子任务

Subtask 1 (23 pts): $n\le 10, T\le 20$

Subtask 2 (22 pts): $\sum n\le 500$

Subtask 3 (28 pts): $\sum n\le 5000$

Subtask 4 (27 pts): $\sum n\le 10^6$