202301H 新年快乐 题解

· · 题解

[语言月赛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";
}

视频题解

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