[CTS2024] 字符串游戏

Luogu
IDLGP10215
Time2000ms
Memory512MB
DifficultyP7
2024CTSC/CTS
小 P 和小 B 喜欢玩游戏,他们找到了 skip。skip 告诉了他们这样一个游戏: - 有一个包含小写字母的字符串 $S$,游戏开始时其为 skip 给定的一个字符串 $S_0$。游戏对小 P 和小 B 计算分数,初始他们的分数都为 $0$。 - 小 P 和小 B 轮流在这个串上操作,小 P 先手。每次操作方可以进行以下操作: - 选择 $S$ 的一个非空前缀(可以是 $S$ 本身),获得等同于这个前缀在 $S$ 中的出现次数的分数,并将这个前缀从 $S$ 中删掉。 - 如果进行了某次操作后 $S$ 变为空,游戏就结束了。 为了让你更好的理解游戏规则,考虑如下例子: - 初始时,$S_0 = 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 的得分会是多少。 ## Input 标准输入读入数据。 输入仅一行一个小写字母构成的字符串 $S_0$。 ## Output 输出到标准输出。 一个整数,表示双方绝顶聪明的前提下,游戏结束时小 P 的得分减去小 B 的得分的值。 [samples] ## Note **样例 1 解释** 小 P 和小 B 的最优策略为题目描述中给出的策略。 ### 子任务 设 $n$ 为字符串 $S$ 的长度。对于所有测试数据,$1\le n\le 10^6$,且字符串 $S$ 为小写字母构成的字符串。 | 子任务编号 | $n \le$ | 特殊性质 | 分值 | |-------|-----------------|------------------------------|----| | 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 |
Samples
Input #1
ababa
Output #1
2
API Response (JSON)
{
  "problem": {
    "name": "[CTS2024] 字符串游戏",
    "description": {
      "content": "小 P 和小 B 喜欢玩游戏,他们找到了 skip。skip 告诉了他们这样一个游戏: - 有一个包含小写字母的字符串 $S$,游戏开始时其为 skip 给定的一个字符串 $S_0$。游戏对小 P 和小 B 计算分数,初始他们的分数都为 $0$。 - 小 P 和小 B 轮流在这个串上操作,小 P 先手。每次操作方可以进行以下操作:   - 选择 $S$ 的一个非空前缀(可以是 $S$ 本身),获",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10215"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 P 和小 B 喜欢玩游戏,他们找到了 skip。skip 告诉了他们这样一个游戏:\n\n- 有一个包含小写字母的字符串 $S$,游戏开始时其为 skip 给定的一个字符串 $S_0$。游戏对小 P 和小 B 计算分数,初始他们的分数都为 $0$。\n- 小 P 和小 B 轮流在这个串上操作,小 P 先手。每次操作方可以进行以下操作:\n  - 选择 $S$ 的一个非空前缀(可以是 $S$ 本身),获...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments