#PQJ1513x8223. QOJ 1513_8223

    ID: 2627 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2024字符串

QOJ 1513_8223

标题: 字符串游戏 - Problem - QOJ.ac

#8223. 字符串游戏

Statistics

The problem was used in the following contests:

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

  • 有一个包含小写字母的字符串 S,游戏开始时其为 skip 给定的一个字符串 S0。游戏对小 P 和小 B 计算分数,初始他们的分数都为 0。

  • 小 P 和小 B 轮流在这个串上操作,小 P 先手。每次操作方可以进行以下操作:

    • 选择 S 的一个非空前缀(可以是 S 本身),获得等同于这个前缀在 S 中的出现次数的分数,并将这个前缀从 S 中删掉。
  • 如果进行了某次操作后 S 变为空,游戏就结束了。

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

  • 初始时,S0=ababa;
  • 小 P 选择 ababa 的前缀 a,获得 3 分,S 变为 baba;
  • 小 B 选择 baba 的前缀 ba,获得 2 分,S 变为 ba;
  • 小 P 选择 ba,获得 1 分,字符串变为空,游戏结束。最终小 P 获得 4 分,小 B 获得 2 分。

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

输入格式

从标准输入读入数据。

输入仅一行一个小写字母构成的字符串 S0。

输出格式

输出到标准输出。

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

样例1输入

ababa

样例1输出

2

样例1解释

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

子任务

设 n 为字符串 S 的长度。对于所有测试数据,1≤n≤106,且字符串 S 为小写字母构成的字符串。

子任务编号n≤特殊性质分值15×103无102106S 的每个字符在 {a,b} 中独立均匀随机3S 的每个字符均为 a542×105S 的每个字符均为 a 或 b2555×105无6106