# 扶苏和串 ## 题目背景 众所周知，每个月入门赛的字符串题都是扶苏来枚举 idea 出出来的。 ## 题目描述 给定一个 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$ 的字典序。 ## 输入格式 输入只有一行一个字符串，表示 $s$。 ## 输出格式 输出一行一个字符串，表示得到的字典序最小的字符串。 ## 样例 #1 ### 样例输入 #1 ``` 101 ``` ### 样例输出 #1 ``` 011 ``` ## 样例 #2 ### 样例输入 #2 ``` 0010100 ``` ### 样例输出 #2 ``` 0000101 ``` ## 提示 ### 样例 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}$。c++

题目描述的是给定一个01字符串，可以选择其中的一个子串并翻转一次，问如何得到字典序最小的字符串。

我们可以观察到，如果我们选择的子串中包含了1，那么在翻转之后，原先是1的位置上就会变成0，原先是0的位置上会变成1。因此，我们希望选择一个不包含1的最长子串进行翻转。

具体的做法如下：
1. 遍历字符串s，找到第一个出现的1的位置i。如果找不到1，则直接输出s。
2. 从位置i开始向后遍历，直到遇到0为止，记录下最后一个0的位置j。
3. 将子串s[0:j]翻转，即将其中的0变成1，1变成0。
4. 输出翻转后的字符串。

以下是C++代码实现：

#include <iostream>
#include <string>
using namespace std;

string getMinString(string s) {
    int n = s.length();
    int i = 0;
    while (i < n && s[i] != '1') {
        i++;
    }
    if (i == n) {
        return s;
    }
    int j = i;
    while (j < n && s[j] != '0') {
        j++;
    }
    for (int k = 0; k <= j; k++) {
        if (k < j - k) {
            swap(s[k], s[j - k]);
        }
    }
    return s;
}

int main() {
    string s;
    cin >> s;
    cout << getMinString(s) << endl;
    return 0;
}

时间复杂度分析：遍历一次字符串s，时间复杂度为O(|s|)。