[语言月赛 202307] 扶苏和串

Luogu
IDLGB3810
Time1000ms
Memory512MB
DifficultyP2
2023O2优化字符串(入门)语言月赛
给定一个 01 字符串 $s$,你可以任选 $s$ 的一个非空子串,把这个子串在 $s$ 中**翻转**一次。 问你能得到字典序最小的字符串是什么? 形式化的,你可以选择一个区间 $[l, r]$ 满足 $1 \leq l \leq r \leq |s|$,构造一个串 $t$ 满足: $$t_i = \begin{cases}s_i, &i < l \text{ 或 } i > r \\ s_{r - (i - l)}, & l \leq i \leq r\end{cases}$$ 这里字符串的下标从 $1$ 开始。 最小化字符串 $t$ 的字典序。 ## Input 输入只有一行一个字符串,表示 $s$。 ## Output 输出一行一个字符串,表示得到的字典序最小的字符串。 [samples] ## Background 众所周知,每个月入门赛的字符串题都是扶苏来枚举 idea 出出来的。 ## Note ### 样例 1 解释 $s = \texttt{\underline{10}1}$,翻转下划线标出的子串,得到 $t = \texttt{011}$ ### 样例 2 解释 $s = \texttt{00\underline{10100}}$,翻转下划线标出的子串,得到 $\texttt{0000101}$。 ### 数据规模与约定 下面用 $|s|$ 表示输入字符串的长度。 - 对 $20\%$ 的数据,$|s| \leq 2$。 - 对 $40\%$ 的数据,$|s| \leq 8$。 - 另有 $10\%$ 的数据,$s$ 只含字符 $\texttt 1$。 - 另有 $10\%$ 的数据,$s$ 只含字符 $\texttt 0$。 - 对 $100\%$ 的数据,$1 \leq |s| \leq 100$。$s$ 只含字符 $\texttt{0,1}$。
Samples
Input #1
101
Output #1
011
Input #2
0010100
Output #2
0000101
API Response (JSON)
{
  "problem": {
    "name": "[语言月赛 202307] 扶苏和串",
    "description": {
      "content": "给定一个 01 字符串 $s$,你可以任选 $s$ 的一个非空子串,把这个子串在 $s$ 中**翻转**一次。 问你能得到字典序最小的字符串是什么? 形式化的,你可以选择一个区间 $[l, r]$ 满足 $1 \\leq l \\leq r \\leq |s|$,构造一个串 $t$ 满足: $$t_i = \\begin{cases}s_i, &i < l \\text{ 或 } i > r \\\\ s",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3810"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 01 字符串 $s$,你可以任选 $s$ 的一个非空子串,把这个子串在 $s$ 中**翻转**一次。\n\n问你能得到字典序最小的字符串是什么?\n\n形式化的,你可以选择一个区间 $[l, r]$ 满足 $1 \\leq l \\leq r \\leq |s|$,构造一个串 $t$ 满足:\n\n$$t_i = \\begin{cases}s_i, &i < l \\text{ 或 } i > r \\\\ s...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments