luogu-B3769 [语言月赛202305] 制糊串

GESP C++三级练习，字符串截取练习，难度★★☆☆☆。

luogu-B3769 [语言月赛202305] 制糊串

题目要求

题目背景

在这个问题中，我们用 $s[x,y]$ 表示从字符串 $s$ 的第 $x$ 个字符到第 $y$ 个字符连起来构成的字符串。例如，若 $s = \texttt{abcdef}$，则 $s[2,4] = \texttt{bcd}$。

题目描述

给出两个字符串 $s$ 和 $t$，有 $q$ 次询问。

每次给出 $l_1, r_1$ 和 $l_2, r_2$，请判断 $s[l_1, r_1]$ 和 $t[l_2, r_2]$ 谁的字典序更小。

输入格式

第一行是一个字符串 $s$。
第二行是一个字符串 $t$。
第三行是一个整数，表示询问次数 $q$。
接下来 $q$ 行，每行四个整数 $l_1, r_1, l_2, r_2$，表示一次询问。

输出格式

对每次询问，输出一行一个字符串：

• 如果 $s[l_1, r_1]$ 的字典序更小，请输出 >$\texttt{yifusuyi}$。
• 如果 $t[l_2, r_2]$ 的字典序更小，请输出 >$\texttt{erfusuer}$。
• 如果两者的字典序一样大，请输出 $\texttt{ovo}$。

输入输出样例 #1

输入 #1

Yifusuyi
yifusuYi
3
1 2 7 8
1 2 1 2
7 8 7 8

输出 #1

ovo
yifusuyi
erfusuer

说明/提示

数据规模与约定

以下用 $\vert s\vert$ 表示 $s$ 的长度，$\vert t\vert$ 表示 $t$ 的长度。

• 对 $30\%$ 的数据，$\vert s\vert = \vert t\vert = 1$。
• 对 $60\%$ 的数据，$q = 1$。
• 对 $100\%$ 的数据，$1 \leq \vert s\vert, \vert t\vert, q \leq 10^3$，$1 \leq l_1 \leq r_1 \leq \vert s\vert$，$1 \leq l_2 \leq r_2 \leq \vert t\vert$。输入字符串仅含大小写英文字母。

题目分析

解题思路

本题的解题思路如下：

1. 问题分析：

   • 输入两个字符串 $s$ 和 $t$，以及查询次数 $q$
   • 每次查询给出四个整数 $l_1,r_1,l_2,r_2$，表示需要比较的子串范围
   • 需要比较 $s[l_1,r_1]$ 和 $t[l_2,r_2]$ 的字典序大小

2. 解题方法：

   • 核心思路：
     • 使用 string 的 substr 函数截取子串
     • 直接使用字符串比较运算符比较字典序
     • 根据比较结果输出对应字符串
   • 实现方式：
     • 读取两个原始字符串 $s$ 和 $t$
     • 循环处理 $q$ 次查询
     • 每次查询截取并比较子串

3. 实现要点：

   • 字符串长度范围：$1 \leq \vert s\vert,\vert t\vert \leq 10^3$
   • 查询次数范围：$1 \leq q \leq 10^3$
   • 子串范围合法：$1 \leq l_1 \leq r_1 \leq \vert s\vert$，$1 \leq l_2 \leq r_2 \leq \vert t\vert$
   • 字符串只包含大小写英文字母

复杂度分析：

• 时间复杂度：$O(q \times L)$，其中q为查询次数，L为最大子串长度
• 空间复杂度：$O(L)$，需要存储原始字符串和子串

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>
#include <string>

int main() {
    // 声明两个字符串变量s和t用于存储输入的字符串
    std::string s, t;
    // 声明整型变量q用于存储查询次数
    int q;
    // 读取输入的两个字符串和查询次数
    std::cin >> s >> t >> q;
    
    // 循环处理q次查询
    for (int i = 0; i < q; i++) {
        // 声明四个整型变量用于存储查询的起止位置
        int l1, r1, l2, r2;
        // 读取每次查询的四个位置参数
        std::cin >> l1 >> r1 >> l2 >> r2;
        
        // 从字符串s中截取子串，注意下标从0开始，所以要减1
        std::string s_sub = s.substr(l1 - 1, r1 - l1 + 1);
        // 从字符串t中截取子串
        std::string t_sub = t.substr(l2 - 1, r2 - l2 + 1);
        
        // 比较两个子串的字典序
        if (s_sub < t_sub) {
            // s的子串字典序更小
            std::cout << "yifusuyi" << std::endl;
        } else if (s_sub > t_sub) {
            // t的子串字典序更小
            std::cout << "erfusuer" << std::endl;
        } else {
            // 两个子串字典序相等
            std::cout << "ovo" << std::endl;
        }
    }
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号