自动搬运

查看原文

来自洛谷，原作者为

	I_am_AKed_by_NOI 数学里有一个虐心的事实：两条平行线永不相交。两条相交的线，先是不停相近，但在经历唯一的相交后，越离越远。

搬运于2025-08-24 22:48:33，当前版本为作者最后更新于2023-07-19 10:10:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$ 个字符）

现在分类讨论：

$(1)$：$y \ne -1$。

• 如果以 $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$

• 如果以 $x$ 作为左端点进行翻转，右端点一定是 $1$，因为 $x$ 后面没有 $0$ 的出现，所以旋转区间内的所有数都为 $1$，翻转后与原字符串相同。

• 如果以 $x$ 右侧一点（设为 $a_3$）作为左端点进行翻转，类似地，翻转后与原字符串相同。

• 如果以 $x$ 右侧一点（设为 $a_4$）作为左端点进行翻转，如果右端点（设为 $a_5$） 在 $x$ 左侧，显然的 $S_{a_4},S_{a_4+1},...S_{a_5}$ 之间所有的数都为 $0$，翻转后与原字符串相同。如果右端点（设为 $a_5$） 在 $x$ 右侧，那么 $S_{a_5}$ 一定为 $1$，翻转后 $S_{a_4}$ 就会由 $0$ 变成 $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; //漂亮的结尾！ 
}

完结撒花！！

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