字符串翻转 - 扶苏和串 - 代码详解

#\ 扶苏和串\n\n##\ 题目背景\n\n众所周知，每个月入门赛的字符串题都是扶苏来枚举 idea 出出来的。\n\n##\ 题目描述\n\n给定一个 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_{r - (i - l)}, & l \leq i \leq r\end{cases}$$\n\n这里字符串的下标从 $1$ 开始。\n\n最小化字符串 $t$ 的字典序。\n\n##\ 输入格式\n\n输入只有一行一个字符串，表示 $s$。\n\n##\ 输出格式\n\n输出一行一个字符串，表示得到的字典序最小的字符串。\n\n##\ 样例 #1\n\n###\ 样例输入 #1\n\n\n101\n\n\n###\ 样例输出 #1\n\n\n011\n\n\n##\ 样例 #2\n\n###\ 样例输入 #2\n\n\n0010100\n\n\n###\ 样例输出 #2\n\n\n0000101\n\n\n##\ 提示\n\n###\ 样例 1 解释\n\n$s = \texttt{\underline{10}1}$，翻转下划线标出的子串，得到 $t = \texttt{011}$\n\n###\ 样例 2 解释\n\n$s = \texttt{00\underline{10100}}$，翻转下划线标出的子串，得到 $\texttt{0000101}$。\n\n###\ 数据规模与约定\n\n下面用 $|s|$ 表示输入字符串的长度。\n\n- 对 $20%$ 的数据，$|s| \leq 2$。\n- 对 $40%$ 的数据，$|s| \leq 8$。\n- 另有 $10%$ 的数据，$s$ 只含字符 $\texttt 1$。\n- 另有 $10%$ 的数据，$s$ 只含字符 $\texttt 0$。\n- 对 $100%$ 的数据，$1 \leq |s| \leq 100$。$s$ 只含字符 $\texttt{0,1}$。cpp code内容：cpp\n#include <iostream>\n#include <string>\nusing namespace std; \n\nstring getSmallestString(string s) {\n int n = s.size();\n string t = s; \n for (int i = 0; i < n; i++) {\n if (s[i] == '1') {\n int j = i + 1;\n while (j < n && s[j] == '1') {\n j++;\n }\n reverse(t.begin() + i, t.begin() + j);\n i = j - 1;\n }\n }\n return t; \n}\n\nint main() {\n string s;\n cin >> s;\n string ans = getSmallestString(s);\n cout << ans << endl; \n return 0; \n}\n