D. 智胜对手

• 每次测试时间限制：1 秒
• 内存限制：256 MB

题目描述

爱丽丝和鲍勃在玩一个与字符串有关的游戏。

每场游戏开始时，爱丽丝先选择一个长度为 $n$、仅由字符 H 和 T 组成的字符串 $A$，并将其展示给鲍勃。

接下来的游戏按以下顺序进行：

1. 鲍勃选择一个长度为 $n$、仅由字符 H 和 T 组成的字符串 $B$，且满足 $A \neq B$，并将其展示给爱丽丝。
2. 然后爱丽丝和鲍勃共同构造一个同样仅由 H 和 T 组成的新字符串 $S$。鲍勃先选择 $S$ 的第一个字符。
3. 之后，爱丽丝不断在 $S$ 的末尾追加一个新字符（H 或 T），直到游戏结束。

游戏会在以下情况之一发生时立即结束：

• 如果 $A$ 作为 $S$ 的子串出现，则爱丽丝获胜。
• 如果 $B$ 作为 $S$ 的子串出现，则鲍勃获胜。
• 如果 $S$ 的长度达到 $10^{100}$，则鲍勃获胜。

双方都知道游戏规则，并且每一步行动都会立即被对方看到。

现在，爱丽丝已经选择并公开了字符串 $A$。给定 $n$ 和 $A$，请判断在双方都采取最优策略的情况下，从此时开始谁会获胜。

---

子串定义

字符串 $a$ 是字符串 $b$ 的子串，如果 $a$ 可以通过删除 $b$ 开头若干（可能为零）个字符和结尾若干（可能为零）个字符得到。

---

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 游戏数量。

接下来每组数据格式如下：

• 第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）—— 字符串长度。
• 第二行包含一个长度为 $n$、仅由 H 和 T 组成的字符串 $A$—— 爱丽丝选择的字符串。

保证所有游戏 $n$ 的总和不超过 $3 \cdot 10^5$。

---

输出格式

对于每组数据，输出一行：如果爱丽丝获胜，输出 Alice；否则输出 Bob。

---

样例

输入

5
2
HT
3
THT
4
TTHT
3
HHH
1
T

输出

Bob
Alice
Alice
Bob
Bob

---

样例解释

第一组数据中，$A = \text{HT}$。鲍勃可以选择 $B = \text{TH}$，并将 $S$ 的第一个字符设为 T。之后无论爱丽丝如何追加剩余字符，鲍勃都保证获胜。

---

解题思路

注意到，Bob 操作一次（选择 $B$ 和设置 $S$ 的首字符），而 Alice 可以操作无数次（不断追加字符）。因此，只要前 $n-1$ 个字符模仿 Bob 设置的首字符，最后一个字符与 Bob 不同，Alice 就能赢。
什么情况下 Bob 能赢呢？只要前 $n-1$ 个字符彼此相同，即整个字符串 $A$ 的所有字符都相同，Bob 就能赢。

---

参考代码

//Sunshine sunshine ladybugs awake,
//Clap your hooves and do a little shack.

#include<bits/stdc++.h>

#define int long long
#define endl "\n"

using namespace std;

using PII=pair<int,int>;
const int MAXN=300005;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;

void solve(){
    int n; cin >> n;
    string s; cin >> s;

    for(int i = 1; i < n - 1; i++){
        if(s[i] != s[0]){
            cout << "Alice" << endl;
            return;
        }
    }

    cout << "Bob" << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}