「AWOI Round 2 B」树学

Luogu

IDLGP9539

Time1000ms

Memory128MB

DifficultyP2

字符串贪心构造

构造一个长度为 $n$ 的小写字母串，要求和给定的长度为 $n$ 的小写字母串 $s$ 的相似度在 $[l,r]$ 范围内。定义两个长度都为 $n$ 的字符串 $a,b$ 的相似度为 $\sum^{n}_{i=1}[a_i=b_i]$。您需要使构造出的字符串的字典序尽量小。 ## Input 第一行三个正整数 $n,l,r$。接下来一行一个字符串，表示给定的小写字母串 $s$。 ## Output 输出一行一个字符串，表示您构造的字典序最小的可行字符串。 [samples] ## Background HR 刚做完一个简单而又靓丽的题目，它想来试试这道题，可是它太蒻了，不会做，您能帮帮它吗？ ## Note **【数据规模】** **本题使用捆绑测试。** | 子任务编号 | $n\leqslant$ | 特殊性质 | 分值 | | -----------: | -----------: | -----------: | -----------: | | $1$ | $100$ | 无 | $20$ | | $2$ | $10^6$ | A | $10$ | | $3$ | $10^6$ | B | $10$ | | $4$ | $10^6$ | 无 | $60$ | 特殊性质 A：$l=r=n$ 或 $l=0,r=n$。特殊性质 B：$s$ 的每一位都为 `a` 或都不为 `a`。对于 $100\%$ 的数据，$1 \leqslant n \leqslant 10^6$，$0 \leqslant l \leqslant r \leqslant n$，$s$ 的长度为 $n$。 **【工作人员】** | $\text{Idea}$ | $\text{Data}$ | $\text{Check}$ | $\text{Solution}$ | | :----------: | :----------: | :----------: | :----------: | | [玄学OIER荷蒻](/user/671294) | [QwQ666\_666](/user/677609) & [玄学OIER荷蒻](/user/671294) | [QwQ666\_666](/user/677609)| [玄学OIER荷蒻](/user/671294) |

Samples

Input #1

3 1 2
aab

Output #1

aaa

Input #2

4 4 4
awoi

Output #2

awoi

API Response (JSON)

{
  "problem": {
    "name": "「AWOI Round 2 B」树学",
    "description": {
      "content": "构造一个长度为 $n$ 的小写字母串，要求和给定的长度为 $n$ 的小写字母串 $s$ 的相似度在 $[l,r]$ 范围内。 定义两个长度都为 $n$ 的字符串 $a,b$ 的相似度为 $\\sum^{n}_{i=1}[a_i=b_i]$。 您需要使构造出的字符串的字典序尽量小。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9539"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "构造一个长度为 $n$ 的小写字母串，要求和给定的长度为 $n$ 的小写字母串 $s$ 的相似度在 $[l,r]$ 范围内。\n\n定义两个长度都为 $n$ 的字符串 $a,b$ 的相似度为 $\\sum^{n}_{i=1}[a_i=b_i]$。\n\n您需要使构造出的字符串的字典序尽量小。\n\n## Input\n\n第一行三个正整数 $n,l,r$。\n\n接下来一行一个字符串，表示给定的小写字母串 $s$。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments