[蓝桥杯 2020 国 B] 游园安排

Luogu
IDLGP8736
Time1000ms
Memory128MB
DifficultyP3
动态规划 DP2020字典树 Trie蓝桥杯国赛
$\mathrm{L}$ 星球游乐园非常有趣,吸引着各个星球的游客前来游玩。小蓝是 $\mathrm{L}$ 星球 游乐园的管理员。 为了更好的管理游乐园,游乐园要求所有的游客提前预约,小蓝能看到系统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始,后面跟 $0$ 个或多个小写英文字母。游客可能重名。 小蓝特别喜欢递增的事物。今天,他决定在所有预约的游客中,选择一部分游客在上午游玩,其他的游客都在下午游玩,在上午游玩的游客要求按照预约的顺序排列后,名字是单调递增的,即排在前面的名字严格小于排在后面的名字。 一个名字 $A$ 小于另一个名字 $B$ 是指:存在一个整数 $i$,使得 $A$ 的前 $i$ 个字母与 $B$ 的前 $i$ 个字母相同,且 $A$ 的第 $i+1$ 个字母小于 $B$ 的第 $i+1$ 个字母。(如果 $A$ 不存在第 $i+1$ 个字母且 $B$ 存在第 $i+1$ 个字母, 也视为 $A$ 的第 $i+1$ 个字母小于 $B$ 的第 $i+1$ 个字母) 作为小蓝的助手,你要按照小蓝的想法安排游客,同时你又希望上午有尽量多的游客游玩,请告诉小蓝让哪些游客上午游玩。如果方案有多种,请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案,请输出第一个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种,依此类推选择第三个、第四个……游客名字最小的方案。 ## Input 输入包含一个字符串,按预约的顺序给出所有游客的名字,相邻的游客名字之间没有字符分隔。 ## Output 按预约顺序输出上午游玩的游客名单,中间不加任何分隔字符。 [samples] ## Note 对于 $20 \%$ 的评测数据, 输入的总长度不超过 $20$ 个字母。 对于 $50 \%$ 的评测数据, 输入的总长度不超过 $300$ 个字母。 对于 $70 \%$ 的评测数据, 输入的总长度不超过 $10000$ 个字母。 对于所有评测数据, 每个名字的长度不超过 $10$ 个字母, 输入的总长度不超过 $10^6$ 个字母。 蓝桥杯 2020 年国赛 B 组 G 题。
Samples
Input #1
WoAiLanQiaobei
Output #1
AiLanQiaobei
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2020 国 B] 游园安排",
    "description": {
      "content": "$\\mathrm{L}$ 星球游乐园非常有趣,吸引着各个星球的游客前来游玩。小蓝是 $\\mathrm{L}$ 星球 游乐园的管理员。 为了更好的管理游乐园,游乐园要求所有的游客提前预约,小蓝能看到系统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始,后面跟 $0$ 个或多个小写英文字母。游客可能重名。 小蓝特别喜欢递增的事物。今天,他决定在所有预约的游客中,选择一部分游客在上午游玩,",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8736"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$\\mathrm{L}$ 星球游乐园非常有趣,吸引着各个星球的游客前来游玩。小蓝是 $\\mathrm{L}$ 星球 游乐园的管理员。\n\n为了更好的管理游乐园,游乐园要求所有的游客提前预约,小蓝能看到系统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始,后面跟 $0$ 个或多个小写英文字母。游客可能重名。\n\n小蓝特别喜欢递增的事物。今天,他决定在所有预约的游客中,选择一部分游客在上午游玩,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments