B3810

一扶苏一 · 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 即可。

视频题解