CF1673A Subtle Substring Subtraction

Alice 和 Bob 正在玩一个字符串游戏。游戏共进行 $t$ 轮。在每一轮中，会给出一个只包含小写英文字母的字符串 $s$。 Alice 先手，两人轮流操作。Alice 可以移除任意一个偶数长度（可以为空）的子串，Bob 可以移除任意一个奇数长度的子串。 更正式地说，若当前字符串为 $s = s_1s_2\ldots s_k$，玩家可以选择一个长度为对应奇偶性的子串 $s_ls_{l+1}\ldots s_{r-1}s_r$ 并将其移除。移除后，字符串变为 $s = s_1\ldots s_{l-1}s_{r+1}\ldots s_k$。 当字符串变为空时，本轮结束，每位玩家计算自己在本轮中移除的所有字符的得分。字符 $\texttt{a}$ 的分值为 $1$，$\texttt{b}$ 的分值为 $2$，$\texttt{c}$ 的分值为 $3$，以此类推，$\texttt{z}$ 的分值为 $26$。得分高的玩家赢得本轮。对于每一轮，判断谁获胜，并输出胜者与败者分数的差。假设两人都采取最优策略以最大化自己的得分。可以证明不会出现平局。

输入的第一行为一个整数 $t$（$1\leq t\leq 5\cdot 10^4$），表示游戏轮数。 接下来的 $t$ 行，每行一个字符串 $s$（$1\leq |s|\leq 2\cdot 10^5$），表示本轮使用的字符串。这里 $|s|$ 表示字符串 $s$ 的长度。 保证所有轮中字符串长度之和不超过 $2\cdot 10^5$。

对于每一轮，输出一行，包含一个字符串和一个整数。如果 Alice 获胜，输出 "Alice"；如果 Bob 获胜，输出 "Bob"。整数为胜者与败者分数的差值，假设两人都采取最优策略。

对于第一轮，$\texttt{"aba"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{ab}}}\texttt{a"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}$。Alice 的总得分为 $1+2=3$，Bob 的总得分为 $1$。 对于第二轮，$\texttt{"abc"}\xrightarrow{\texttt{Alice}}\texttt{"a}{\color{red}{\texttt{bc}}}\texttt{"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}$。Alice 的总得分为 $2+3=5$，Bob 的总得分为 $1$。 对于第三轮，$\texttt{"cba"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{cb}}}\texttt{a"}\xrightarrow{} \texttt{"a"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{a}}}\texttt{"}\xrightarrow{}\texttt{""}$。Alice 的总得分为 $3+2=5$，Bob 的总得分为 $1$。 对于第四轮，$\texttt{"n"}\xrightarrow{\texttt{Alice}}\texttt{"n"}\xrightarrow{} \texttt{"n"}\xrightarrow{\texttt{Bob}}\texttt{"}{\color{red}{\texttt{n}}}\texttt{"}\xrightarrow{}\texttt{""}$。Alice 的总得分为 $0$，Bob 的总得分为 $14$。 对于第五轮，$\texttt{"codeforces"}\xrightarrow{\texttt{Alice}}\texttt{"}{\color{red}{\texttt{codeforces}}}\texttt{"}\xrightarrow{} \texttt{""}$。Alice 的总得分为 $3+15+4+5+6+15+18+3+5+19=93$，Bob 的总得分为 $0$。 由 ChatGPT 4.1 翻译