【CTS2024】字符串游戏 - 题目 - Universal Online Judge

小 P 和小 B 喜欢玩游戏，他们找到了 skip。skip 告诉了他们这样一个游戏：

有一个包含小写字母的字符串 $S$ ，游戏开始时其为 skip 给定的一个字符串 $S_{0}$ 。游戏对小 P 和小 B 计算分数，初始他们的分数都为 $0$ 。
小 P 和小 B 轮流在这个串上操作，小 P 先手。每次操作方可以进行以下操作：
- 选择 $S$ 的一个非空前缀（可以是 $S$ 本身），获得等同于这个前缀在 $S$ 中的出现次数的分数，并将这个前缀从 $S$ 中删掉。
如果进行了某次操作后 $S$ 变为空，游戏就结束了。

为了让你更好的理解游戏规则，考虑如下例子：

小 P 希望最大化小 P 的得分减去小 B 的得分，而小 B 希望最小化这个值。他们想知道在双方都绝顶聪明的情况下，最终小 P 的得分减去小 B 的得分会是多少。

标准输入读入数据。

输入仅一行一个小写字母构成的字符串 $S_{0}$ 。

输出到标准输出。

一个整数，表示双方绝顶聪明的前提下，游戏结束时小 P 的得分减去小 B 的得分的值。

ababa

样例 1 解释

小 P 和小 B 的最优策略为题目描述中给出的策略。

设 $n$ 为字符串 $S$ 的长度。对于所有测试数据， $1 \leq n \leq 10^{6}$ ，且字符串 $S$ 为小写字母构成的字符串。

子任务编号	$n \leq$	特殊性质	分值
1	$5 \times 10^{3}$	无	10
2	$10^{6}$	$S$ 的每个字符在 ${a, b}$ 中独立均匀随机	10
3	$10^{6}$	$S$ 的每个字符均为 $a$	5
4	$2 \times 10^{5}$	$S$ 的每个字符均为 $a$ 或 $b$	25
5	$5 \times 10^{5}$	无	25
6	$10^{6}$	无	25

时间限制：2s $3.5s$

空间限制：~~512MB~~ $1G$

Universal Online Judge