自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:30，当前版本为作者最后更新于2023-01-05 22:04:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[语言月赛202301] 新年快乐 题解

Source & Knowledge

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

文字题解

题目大意

给定一个只含小写字母的字符串 $s$。

给出 $q$ 组询问，每次截取 $s$ 的第 $l$ 个字符到第 $r$ 个字符构成新的字符串 $t$。询问 $t$ 的「上一个字符串」是否存在于 $s$ 中。

解析

C++ 的 string 类提供了很多很有用的功能。这里我们会用到其提供的 substr() 与 find() 两个函数。

对于一个 string 类型变量 $s$，s.substr(l, r) 返回值可被转换为 string 类，返回内容为以 $s$ 的第 $l + 1$ 个字符为起点，截取其及其之后共计 $r$ 个字符构成的新的字符串。

对于两个 string 类型变量 $s, t$，s.find(t) 代表查找 $t$ 在 $s$ 中的位置。如果可以找到，则返回 $t$ 第一次在 $s$ 中出现的位置的起始下标。如果无法找到，则返回 npos。大多数情况下 npos 的值为 -1。

需要注意的是，find() 函数近似于暴力匹配，时间复杂度为平方级别。但是本题数据规模相对较小，这种方式可以通过。

下面将这两个函数运用到题目中。

对于每次询问，我们调用 s.substr(l - 1, r - l + 1) 得到子字符串 $t$。这里截取了以 $s$ 的第 $(l - 1) + 1$ 个字符为起点，长度为 $r - l + 1$ 的字符串，不难发现为 $s$ 的第 $l$ 个字符到第 $r$ 个字符。

我们注意到，$t$ 的「上一个字符串」是不存在的，当且仅当 $t$ 全部由小写字母 $\texttt{a}$ 构成。

详细说明：假设 $t$ 中有一个位置的字母不是小写字母 $\texttt{a}$，那么在取 $t$ 的「上一个字符串」时，我们一定可以找到一个位置使其变为其的上一个字母，在这个位置之后进行一定的修改便可找到 $t$ 的上一个字符串。如果 $t$ 全部由小写字母 $\texttt{a}$ 构成，那么我们找不到任何一个位置可以变为上一个字母。由此，我们便无法找到「上一个字符串」。

因此，我们首先需要判断 $t$ 中是否全部为小写字母 $\texttt{a}$。如果是，则输出 NULL\nHappy Chinese New Year!\n。

核心代码如下：

int flag = 1;
for (int i = 0; i < t.length(); ++i) {
    if (t[i] != 'a') {
        flag = 0;
        break;
    }
}
if (flag) {
    cout << "NULL\nHappy Chinese New Year!\n";
}

确认 $t$ 中不全为小写字母 $\texttt{a}$ 后，我们从后向前进行寻找直到找到第一个不为 $\texttt{a}$ 的位置。此时，该位置之后全部为 $\texttt{a}$。因此，我们将其自身修改为上一个字符，其之后全部赋值为小写字母 $\texttt{z}$ 即可。

核心代码如下：

for (int i = t.length() - 1; i >= 0; --i)
    if (t[i] == 'a') {
        t[i] = 'z';
    } else {
        --t[i];
        break;
    }

最后，我们调用 s.find(t)，判断返回值是否为 npos 即 -1，进行对应的输出即可。

核心代码如下：

cout << t << endl;
if (s.find(t) != -1) {
    cout << "Happy New Year!\n";
} else {
    cout << "Happy Chinese New Year!\n";
}

视频题解

完整代码请在视频中查看。