自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:15:12，当前版本为作者最后更新于2020-05-24 10:12:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[语言月赛202307] 扶苏和串 题解

Source & Knowledge

2023 年 7 月语言月赛，由洛谷网校入门计划/基础计划提供。

本题考察字符串处理

文字题解

题目大意

给定一个 01 字符串 $s$，你可以任选 $s$ 的一个非空子串，把这个子串在 $s$ 中翻转一次。

问你能得到字典序最小的字符串是什么？

字符串长度不超过 $100$。

解析

枚举 $s$ 子串的左右端点，然后将之翻转找到最小答案即可。

使用 s.substr(pos, len) 可以取出 $s$ 的从第 $pos$ 开始长度为 $len$ 的子串，如果不写 $len$ 则截取到字符串末尾。

for (int l = 0; l < s.length(); ++l) {
  for (int r = l + 1; r < s.length(); ++r) {
    string x = s.substr(0, l);
    string y = s.substr(l, r - l + 1);
    string z = s.substr(r + 1);
  }
}

上面的代码把字符串拆成了 $[0, l - 1], [l, r], [r + 1, |s| - 1]$ 三段。

使用 reverse(t.begin(), t.end()) 可以把 $t$ 翻转。

reverse(y.begin(), y.end());

这个函数需要 algorithm 头文件。

使用字符串的 + 运算符可以进行字符串拼接，拼接后可以用 min 函数直接比较最小值。

string tmp = x + y + z;
ans = min(tmp, ans);

初始时，ans 的值是原串。最后输出 ans 即可。

视频题解