D. Letter Picking
Alice and Bob are playing a game. Initially, they are given a non-empty string $s$, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.
Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string $s$, removes it from $s$ and prepends (adds to the beginning) it to their own string.
The game ends when the string $s$ becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.
A string $a$ is lexicographically smaller than a string $b$ if there exists such position $i$ that $a_j = b_j$ for all $j < i$ and $a_i < b_i$.
What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?
Input
The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.
Each testcase consists of a single line — a non-empty string $s$, consisting of lowercase Latin letters. The length of the string $s$ is even.
The total length of the strings over all testcases doesn't exceed $2000$.
Output
For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".
Example
input
2
forces
abbaoutput
Alice
DrawNote
One of the possible games Alice and Bob can play in the first testcase:
- Alice picks the first letter in $s$: $s=$"orces", $a=$"f", $b=$"";
- Bob picks the last letter in $s$: $s=$"orce", $a=$"f", $b=$"s";
- Alice picks the last letter in $s$: $s=$"orc", $a=$"ef", $b=$"s";
- Bob picks the first letter in $s$: $s=$"rc", $a=$"ef", $b=$"os";
- Alice picks the last letter in $s$: $s=$"r", $a=$"cef", $b=$"os";
- Bob picks the remaining letter in $s$: $s=$"", $a=$"cef", $b=$"ros".
Alice wins because "cef" < "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.
解题思路
动态规划还是很好想到的，但状态转移很复杂最后还是没做出来。当然在写这篇博客的时候感觉逻辑还是有点乱的，不过我已尽量去理清思路，如果我讲不明白请看其他大佬的题解吧。
把 Alice 先取走一个字符，Bob 再取走一个字符定义为一轮，那么一局游戏会在 $\frac{n}{2}$ 轮后结束。假设 Alice 和 Bob 各自的字符串为 $sa$ 和 $sb$，那么首个字符 $sa_1$ 和 $sb_1$ 就是第 $\frac{n}{2}$ 轮结束后得到的，第 $2$ 个字符 $sa_2$ 和 $sb_2$ 就是第 $\frac{n}{2}-1$ 轮结束后得到的，以此类推字符串最后一个字符 $sa_{n/2}$ 和 $sb_{n/2}$ 是第 $1$ 轮结束后得到的。
先用最常规的思路来做这道题。定义状态 $f(l,r)$ 表示以字符串 $s_l \sim s_r$ 进行游戏的结果，如果 $f(l,r) = 0$ 则平局，否则 $f(l,r) = 1$ 则 Alice 胜，$f(l,r) = 2$ 则 Bob 胜。以一轮为单位进行状态转移，分以下两种情况：
- 区间 $[l,r]$ 的长度为 $2$。如果 $s_l = s_r$ 则为平局，$f(l,r) = 0$。否则 $s_l \ne s_r$ Alice 必然会取最大的那个字符，有 $f(l,r) = 1$。
- 区间 $[l,r]$ 的长度大于 $2$。$f(l,r)$ 可通过 $f(l+1,r-1)$ （Alice 和 Bob 取两端的字符），$f(l+2,r)$ 和 $f(l, r-2)$（Alice 和 Bob 取同一端的字符）转移过来。
可以知道区间长的状态总是由区间短的状态转移得到，因此状态转移图是一个有向无环图，可以 dp。
在任意一轮中无非就只有以下 $4$ 中情况：
- Alice 取 $s_l$，Bob 取 $s_{l+1}$
- Alice 取 $s_l$，Bob 取 $s_r$
- Alice 取 $s_r$，Bob 取 $s_{r-1}$
- Alice 取 $s_r$，Bob 取 $s_{l}$
考虑 $f(l,r) = 1$ 的情况。由于每个人都选择最优的操作，如果 Alice 会取 $s_l$，当且仅当无论 Bob 取 $s_{l+1}$ 或是 $s_r$ 都是 Alice 胜。分别考虑 Bob 取 $s_{l+1}$ 和 $s_r$ 的情况：
- Bob 取 $s_{l+1}$ 时 Alice 在什么情况下能胜？
-
- $s_l < s_{l+1}$：由于在这个位置上 Alice 的字符已经比 Bob 的小了，因此只要 $f(l+2,r) \ne 2$，$sa$ 的字典序都比 $sb$ 小，即 Alice 胜。
- $s_l \geq s_{l+1}$：由于在这个位置上 Alice 的字符不比 Bob 的小，因此只有 $f(l+2,r) = 1$ 时，$sa$ 的字典序才比 $sb$ 小，Alice 才能胜。
- Bob 取 $s_{r}$ 时 Alice 在什么情况下能胜？
-
- $s_l < s_{r}$：由于在这个位置上 Alice 的字符已经比 Bob 的小了，因此只要 $f(l+1,r-1) \ne 2$，$sa$ 的字典序都比 $sb$ 小，即 Alice 胜。
- $s_l \geq s_{r}$：由于在这个位置上 Alice 的字符不比 Bob 的小，因此只有 $f(l+1,r-1) = 1$ 时，$sa$ 的字典序才比 $sb$ 小，Alice 才能胜。
同理分析如果 Alice 取 $s_r$，当且仅当无论 Bob 取 $s_{r-1}$ 或是 $s_l$ 都是 Alice 胜。
如果 Alice 取 $s_l$ 或是 $s_r$ 都不能保证 Alice 胜，那么接下来 Alice 应该尽可能保证是平局。与上面的分析几乎一样，如果 Alice 会取 $s_l$，当且仅当无论 Bob 取 $s_{l+1}$ 或是 $s_r$ 都是平局。分别考虑 Bob 取 $s_{l+1}$ 和 $s_r$ 的情况：
- 在已知 Alice 不能胜的情况下，Bob 取 $s_{l+1}$ 时在什么情况下能平局？
-
- $s_l \leq s_{l+1}$：由于在这个位置上 Alice 的字符不比 Bob 的大，因此只要 $f(l+2,r) \ne 2$，$sa$ 的字典序不比 $sb$ 大，Bob 不能胜。
- $s_l > s_{l+1}$：由于在这个位置上 Alice 的字符比 Bob 的大，因此只有 $f(l+2,r) = 1$ 时，$sa$ 的字典序才比 $sb$ 小，Bob 不能胜。
- 在已知 Alice 不能胜的情况下，Bob 取 $s_{r}$ 时在什么情况下能平局？
-
- $s_l \leq s_{r}$：由于在这个位置上 Alice 的字符不比 Bob 的大，因此只要 $f(l+1,r-1) \ne 2$，$sa$ 的字典序不比 $sb$ 大，Bob 不能胜。
- $s_l > s_{r}$：由于在这个位置上 Alice 的字符比 Bob 的大，因此只有 $f(l+1,r-1) = 1$ 时，$sa$ 的字典序才比 $sb$ 小，Bob 不能胜。
同理分析如果 Alice 取 $s_r$，当且仅当无论 Bob 取 $s_{r-1}$ 或是 $s_l$ 都是平局。
如果 $f(l,r) = 1$ 和 $f(l,r) = 0$ 都不能满足，那么只有 $f(l,r) = 2$ 了，即 Bob 胜。
AC 代码如下，时间复杂度为 $O(n^2)$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010;
char s[N];
int f[N][N];
int dfs(int l, int r) {
if (f[l][r] != -1) return f[l][r];
if (r - l + 1 == 2) return f[l][r] = s[l] != s[r];
f[l][r] = 2; // 假定Bob胜
// 判断Alice能否胜
if ((s[l] < s[l + 1] && dfs(l + 2, r) != 2 || s[l] >= s[l + 1] && dfs(l + 2, r) == 1) && (s[l] < s[r] && dfs(l + 1, r - 1) != 2 || s[l] >= s[r] && dfs(l + 1, r - 1) == 1)) f[l][r] = 1;
if ((s[r] < s[r - 1] && dfs(l, r - 2) != 2 || s[r] >= s[r - 1] && dfs(l, r - 2) == 1) && (s[r] < s[l] && dfs(l + 1, r - 1) != 2 || s[r] >= s[l] && dfs(l + 1, r - 1) == 1)) f[l][r] = 1;
if (f[l][r] == 1) return f[l][r]; // Alice能胜，直接断定
// 否则Alice不能胜，看能否平局
if ((s[l] <= s[l + 1] && dfs(l + 2, r) != 2 || s[l] > s[l + 1] && dfs(l + 2, r) == 1) && (s[l] < s[r] && dfs(l + 1, r - 1) != 2 || s[l] == s[r] && !dfs(l + 1, r - 1) || s[l] > s[r] && dfs(l + 1, r - 1) == 1)) f[l][r] = 0;
if ((s[r] <= s[r - 1] && dfs(l, r - 2) != 2 || s[r] > s[r - 1] && dfs(l, r - 2) == 1) && (s[r] < s[l] && dfs(l + 1, r - 1) != 2 || s[r] == s[l] && !dfs(l + 1, r - 1) || s[r] > s[l] && dfs(l + 1, r - 1) == 1)) f[l][r] = 0;
return f[l][r];
}
void solve() {
scanf("%s", s);
memset(f, -1, sizeof(f));
int n = strlen(s);
dfs(0, n - 1);
if (f[0][n - 1] == 0) printf("Draw\n");
else if (f[0][n - 1] == 1) printf("Alice\n");
else printf("Bob\n");
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}事实上可以证明游戏的结果只有 Alice 胜或平局这两种结果，这个应该可以通过数学归纳法来证明，不过我想了很久都证不出来，感觉很麻烦。我看其他人的解释是，由于最终状态（长度为 $2$ 的串）只有 Alice 胜和平局两种状态，Bob 不能胜，所以 Bob 无论怎样都不会胜，因为其它状态都是由最终状态转移得到。这里直接用这个结论来定义状态表示。
定义状态 $f(l,r)$ 表示以字符串 $s_l \sim s_r$ 进行游戏的结果，如果 $f(l,r) = 0$ 则平局，否则 $f(l,r) = 1$ 则 Alice 胜。
考虑 $f(l,r) = 1$ 的情况（与上面的完全一样）。由于每个人都选择最优的操作，如果 Alice 会取 $s_l$，当且仅当无论 Bob 取 $s_{l+1}$ 或是 $s_r$ 都是 Alice 胜。分别考虑 Bob 取 $s_{l+1}$ 和 $s_r$ 的情况：
- Bob 取 $s_{l+1}$ 时 Alice 在什么情况下能胜？
-
- $s_l < s_{l+1}$：由于在这个位置上 Alice 的字符已经比 Bob 的小了，因此只要 $f(l+2,r) \ne 2$，$sa$ 的字典序都比 $sb$ 小，即 Alice 胜。
- $s_l \geq s_{l+1}$：由于在这个位置上 Alice 的字符不比 Bob 的小，因此只有 $f(l+2,r) = 1$ 时，$sa$ 的字典序才比 $sb$ 小，Alice 才能胜。
- Bob 取 $s_{r}$ 时 Alice 在什么情况下能胜？
-
- $s_l < s_{r}$：由于在这个位置上 Alice 的字符已经比 Bob 的小了，因此只要 $f(l+1,r-1) \ne 2$，$sa$ 的字典序都比 $sb$ 小，即 Alice 胜。
- $s_l \geq s_{r}$：由于在这个位置上 Alice 的字符不比 Bob 的小，因此只有 $f(l+1,r-1) = 1$ 时，$sa$ 的字典序才比 $sb$ 小，Alice 才能胜。
同理分析如果 Alice 取 $s_r$，当且仅当无论 Bob 取 $s_{r-1}$ 或是 $s_l$ 都是 Alice 胜。如果不能保证 Alice 胜，那么游戏的结果就是平局了，这是因为任意游戏都只有 Alice 胜或平局的结果。
AC 代码如下，时间复杂度为 $O(n^2)$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010;
char s[N];
int f[N][N];
int dfs(int l, int r) {
if (f[l][r] != -1) return f[l][r];
if (r - l + 1 == 2) return f[l][r] = s[l] != s[r];
f[l][r] = 0;
if ((s[l] < s[l + 1] || dfs(l + 2, r)) && (s[l] < s[r] || dfs(l + 1, r - 1))) f[l][r] = 1;
if ((s[r] < s[r - 1] || dfs(l, r - 2)) && (s[r] < s[l] || dfs(l + 1, r - 1))) f[l][r] = 1;
return f[l][r];
}
void solve() {
scanf("%s", s);
memset(f, -1, sizeof(f));
printf("%s\n", dfs(0, strlen(s) - 1) ? "Alice" : "Draw");
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
参考资料
Educational Codeforces Round 135 D(博弈) E(扩展gcd)：https://zhuanlan.zhihu.com/p/562781822
Educational Codeforces Round 135 Editorial：https://codeforces.com/blog/entry/106805
标签：sa,Letter,Alice,dfs,&&,sb,Bob,Picking From： https://www.cnblogs.com/onlyblues/p/17854803.html