扶苏和串 题解

· · 题解

update on 7-20 修改了一些错别字和渲染失败的问题，同时贴上了代码并详细讲解了些细节。

暴力解法

观察题目，我们可以想到一个暴力。我们暴力去枚举翻转区间的左端点 l 和右端点 r 的位置，然后将 l,r 范围内的字符进行翻转。这样计算出每一种翻转后的可能，从翻转完的字符串中取出字典序最小的输出即可。

但是复杂度并不乐观：枚举 l 需要 O(n)，枚举 r 需要 O(n)，翻转还需要 O(n)，合起来一共 O(n^3)，显然会炸。

由于这是入门赛，为了方便新手，这里多讲一下细节（大佬请自动跳过）：

我们令两个字符串为 s1 和 s2

一部分人会说，将两个字符串遍历一遍，然后判断两个字符串同样位置上的字符的大小。

其实并不用那么麻烦，其实只需要一句话。

if(s1<s2)

如果成立，那么 s1 的字典序更小，反之 s2 更小。

如果我们要翻转一个长度为 n 的字符串 s1，显然，我们可以倒序遍历一遍 s1，然后存在一个新的数组里。

这里提供另外一种思路，假设翻转字符串 luogu。

luogu
ugoul

发现，原字符符第 i 位在翻转字符串第 n-i+1 位。所以可以遍历 i，然后进行翻转。

正解

其实正解与暴力之间只有一个优化，那就是：翻转的左端点其实是固定的！！！

有一个结论：翻转的左端点必定是字符串 s 中第一次出现 1。

通过次结论，我们就不需要暴力去枚举 l 的位置，只需要 O(n) 枚举 r，并且 O(n) 进行翻转，最后找到字典序最小的即可。总复杂度 O(n^2)，足以通过此题。

大部分题解都没有证明这个结论，在这里我证明一下这个结论：

我们记字符串 s 中第一次出现 1 的位置为 x。x 后面出现了 0 的位置为 y（如果x 后面没有出现 0，那么 y=-1）。

发现，S_1,S_2,...,S_{x-1} 都为 0。（这里 S_i 代表 S 的第 i 个字符）

现在分类讨论：

- 如果以 $x$ 作为左端点进行翻转，那么我们把旋转的右端点为 $y$，那么 $S_x$ 就会被改成 $0$，$S_1,S_2,...,S_{x-1}$ 依然为 $0$。 - 如果以 $x$ 左侧一点（设为 $a_1$）作为左端点进行翻转，如果右端点为 $1$，那么 $S_{a_1}$ 就会被改成 $1$.而如果以 $x$ 作为左端点进行翻转，因为 $a_1 < x$，所以 $S_{a_1}$ 显然为 $0$，$0<1$，所以这种情况不满足字典序最小。如果右端点为 $0$，类似地，也可以推出同样的结论。 - 如果 $x$ 右侧一点（设为 $a_2$）作为左端点进行翻转。不管右端点为什么， $S_x$ 不会被改变，依旧为 $1$，而如果以 $x$ 作为左端点进行翻转，$S_x=0$，$0<1$，不满足字典序最小。 综上，如果，如果 $x$ 后面有出现 $0$，那么以 $x$ 为左端点进行翻转是最优的。 $(2)$：$y = -1

通过以上所有的证明，可以得出：翻转的左端点是字符串 s 中第一次出现 1 的位置最优。

代码

注释对上面的过程进行讲解：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string s1,s2,ans; //ans 是最后输出的答案 
int l,r; //l 是字符串中第一次出现 1 的位置，即翻转的左端点 
int main()
{
    cin>>s1;
    s2=s1; //进行备份 
    ans=s1;
    for(int i=0;i<s1.length();i++) //遍历整个字符串，寻找第一次出现 1 的位置
    {
        if(s1[i]=='1')
        {
            l=i; //找到了就返回 
            break;
        }
    }
    for(r=l+1;r<s1.length();r++) //枚举旋转的右端点 
    {
        for(int j=l,k=r;j<=r,k>=l;j++,k--)
        {
            s2[j]=s1[k]; //将字符串的 [l,r] 进行翻转 
        }
        if(s2<ans) //如果旋转之后的字符串字典序更小 
        {
            ans=s2; //就将答案更新为字典序更小的字符串 
        }
    }
    cout<<ans;
    return 0; //漂亮的结尾！ 
}

完结撒花！！

程序和思路可以带走，请把赞留下，谢谢辣！（可爱）