STL —— 洛谷字符串（string库）入门题（蓝桥杯题目训练）（二）

一、B2121 最长最短单词 - 洛谷

算法代码：

代码分析

变量定义

输入处理

单词长度计算

更新最长和最短单词的长度

输出最长单词

输出最短单词

评测记录：编辑

二、B2122 单词翻转 - 洛谷

算法代码：

代码分析

引入头文件和定义类型

主函数

字符串定义

输入循环

反转输出

换行

返回值

评测记录：编辑

三、B2123 字符串 p 型编码 - 洛谷

算法代码：

代码分析

引入头文件

变量定义

主函数开始

读取输入

初始化第一个字符

遍历字符串

判断字符是否相同

输出最后一组字符

返回值

总结

评测记录：编辑

四、B2124 判断字符串是否为回文 - 洛谷

方法一：算法代码（reverse翻转直接判断）

方法二：算法代码

代码分析

引入头文件

使用命名空间

主函数开始

读取字符串

检查回文

输出结果

总结

评测记录：

五、B2125 最高分数的学生姓名 - 洛谷

算法代码：

代码思路

包含头文件

定义数据结构

全局变量

比较函数

主函数

返回语句

复杂度分析

总结

评测记录：编辑

六、B2126 连续出现的字符 - 洛谷

算法代码：

代码思路

包含头文件

定义变量

读取输入

遍历字符串

无连续字符的情况

复杂度分析

注意事项

改进后的代码示例

评测记录：编辑

七、B3640 T3 句子反转 - 洛谷

算法代码：

代码思路

包含头文件

定义变量

读取输入

处理字符串

输出格式

复杂度分析

总结

评测记录：

八、B3654 [语言月赛202208] 影子字符串 - 洛谷

算法代码：

代码思路

包含头文件

定义变量

读取输入

检查重复

复杂度分析

改进建议

改进后的代码示例

说明

解释

示例

代码示例

总结

评测记录：

九、B3663 [语言月赛202209] Luogu Academic - 洛谷

算法代码：

代码思路

包含头文件

定义变量

读取输入

遍历字符串

输出结果

复杂度分析

总结

评测记录：

十、B3674 [语言月赛202210] 标题修改 - 洛谷

算法代码：

代码解析

包含头文件

主函数

读取输入

处理字符串

输出结果

注意事项

改进后的代码示例

总结

评测记录：

一、B2121 最长最短单词 - 洛谷

算法代码：

#include <iostream>
#include <string>
using namespace std;
string a;
int sum=0,maxx=-100,maxb,minb,minn=1000000;
int main(){getline(cin,a);//带空格输入for(int i=0;i<a.length();i++){if(a[i]==' '||a[i]==','||a[i]=='.'){//如果发现标点符号和空格，代表单词结束if(maxx<sum){//如果单词长度突破目前发现的最长长度maxb=i;//把最长单词的结束点更新，i就是结束点maxx=sum;//把最长单词的长度更新}if(minn>sum){//如果单词长度低于目前发现的最短长度minb=i;//更新最短单词结束点minn=sum;//更新最短长度}sum=0;//sum清空，以便下次操作}else{sum++;//如果是字母，长度加一}}for(int i=maxb-maxx/*从开始位置开始输出*/;i<maxb/*到结束位置结束*/;i++){cout<<a[i];}cout<<endl;for(int i=minb-minn;i<minb;i++){//最短单词同理cout<<a[i];}return 0;
}

代码分析

变量定义
- string a;：用于存储输入的字符串。
- int sum=0;：用于计算当前单词的长度。
- int maxx=-100;：记录发现的最长单词的长度，初始值设置为一个非常小的负数，以确保任何实际单词的长度都会大于这个值。
- int maxb;：记录最长单词的结束位置（索引）。
- int minb;：记录最短单词的结束位置（索引）。
- int minn=1000000;：记录发现的最短单词的长度，初始值设置为一个非常大的数，以确保任何实际单词的长度都会小于这个值。

输入处理

getline(cin, a); // 读取带空格的整行输入

单词长度计算

使用一个循环遍历字符串 a，逐个字符进行处理：

for(int i=0; i<a.length(); i++) {// 检查是否是空格或标点符号if(a[i]==' ' || a[i]==',' || a[i]=='.') {

更新最长和最短单词的长度

当遇到空格或标点符号时，表示一个单词的结束：

更新最长单词：

if(maxx < sum) {maxb = i; // 更新最长单词的结束点maxx = sum; // 更新最长单词的长度
}

更新最短单词：

if(minn > sum) {minb = i; // 更新最短单词的结束点minn = sum; // 更新最短单词的长度
}

更新完成后，将 sum 重置为 0，以便下一次计算新的单词长度：

sum = 0; // 清空当前单词的长度

如果当前字符是字母，则增加 sum：

else {sum++; // 当前单词长度加一
}

输出最长单词

计算并输出第一个最长单词：

for(int i=maxb-maxx; i<maxb; i++) {cout << a[i]; // 输出最长单词
}
cout << endl;

输出最短单词

计算并输出第一个最短单词：

for(int i=minb-minn; i<minb; i++) {cout << a[i]; // 输出最短单词
}

评测记录：

二、B2122 单词翻转 - 洛谷

算法代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){string s;//定义字符串。while(cin>>s){//输入字符串。for(int i=s.size()-1;i>=0;i--){//循环输出。cout<<s[i];}cout<<endl;//换行。}return 0;
}

代码分析

引入头文件和定义类型
```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
```
- #include<bits/stdc++.h>：包含了 C++ 标准库中几乎所有的头文件，方便使用各种功能。尽管这不是最佳实践，但在竞赛或快速测试中很常用。
- #define ll long long：定义了 ll 为 long long 类型，虽然在这段代码中并未使用。
主函数
```
int main() {
```
- int main() 是程序的入口点。
字符串定义
```
string s; // 定义字符串。
```
输入循环
```
while(cin >> s) { // 输入字符串。
```
- 使用 while(cin >> s) 循环读取输入的字符串，直到输入结束（例如，遇到 EOF）。这意味着程序可以处理多行输入，如果每行只包含一个单词。
反转输出
```
for(int i = s.size() - 1; i >= 0; i--) { // 循环输出。cout << s[i];
}
```
- s.size() - 1：获取字符串的最后一个字符的索引。
- for 循环从字符串的最后一个字符开始，向前遍历到第一个字符，逐个输出字符，从而实现反转效果。
换行
```
cout << endl; // 换行。
```
- 在每次反转输出完成后，打印一个换行符，以便于在控制台上的输出格式清晰。
返回值
```
return 0;
```
- 返回 0，表示程序正常结束。

评测记录：

三、B2123 字符串 p 型编码 - 洛谷

算法代码：

#include <iostream>
#include <string>
using namespace std;string a;
char flag;
int ans = 1;//注意，这里要设成1！int main(){cin >> a;flag = a[0];for (int i = 1; i < a.size(); ++ i){if (a[i] == a[i - 1]) {ans += 1;}else {cout << ans << flag;ans = 1;flag = a[i];}}cout << ans << flag << endl;//最后还要再输出return 0;
}

代码分析

引入头文件
```
#include <iostream>
#include <string>
using namespace std;
```
- 引入了 iostream 和 string 头文件，以便使用输入输出流和字符串操作。

变量定义

string a;       // 用于存储输入的字符串
char flag;      // 用于跟踪当前正在计数的字符
int ans = 1;    // 计数器，初始值设为1，因为至少有一个字符

主函数开始
```
int main() {
```
读取输入
```
cin >> a; // 读取输入字符串
```
- cin >> a; 用于读取一个不包含空格的字符串。
初始化第一个字符
```
flag = a[0]; // 将第一个字符存入 flag
```
- flag 用于保存当前正在计数的字符。
遍历字符串
```
for (int i = 1; i < a.size(); ++i) {
```
- 从第二个字符开始遍历字符串（索引从1开始），对每个字符进行处理。

判断字符是否相同

if (a[i] == a[i - 1]) {ans += 1; // 如果当前字符与前一个字符相同，计数器加1
}
else {cout << ans << flag; // 输出当前字符的计数和字符ans = 1;             // 重置计数器flag = a[i];        // 更新 flag 为当前字符
}

如果当前字符与前一个字符相同，增加 ans 的值。
如果不同，输出当前字符的计数及字符，并重置 ans 为1（因为当前字符至少出现了一次），将 flag 更新为当前字符。

输出最后一组字符
```
cout << ans << flag << endl; // 最后一组字符的计数和字符也要输出
```
- 循环结束后，最后一组字符的计数和字符需要单独输出，因为在最后一次的不同字符判断中，这部分不会被输出。
返回值
```
return 0;
```
- 返回0，表示程序正常结束。

总结

功能：该程序将连续相同字符压缩为其字符和出现次数的形式。例如，将输入的字符串 "aaabbc" 转换为 "3a2b1c"。
思路：使用一个循环遍历字符串，利用一个计数器 ans 和一个字符标记 flag 来跟踪当前字符及其连续出现的次数。
最后输出：注意最后一个字符的计数和字符需要在循环结束后单独输出，以确保输出的完整性。

评测记录：

四、B2124 判断字符串是否为回文 - 洛谷

方法一：算法代码（reverse翻转直接判断）

#include<bits/stdc++.h>
using namespace std;
string a,b;int main() {cin >> a;b = a;reverse(a.begin(), a.end());if(a == b) printf("yes\n");else printf("no\n");return 0;
}

方法二：算法代码

#include <bits/stdc++.h> //建议选择万能头文件，避免写程序前打很多头文件
using namespace std;
int main()
{string s;//定义string类（字符串）cin>>s;for(int i=0,j=s.length()-1;i<=s.length()/2;i++,j--){if(s[i]!=s[j]){cout<<"no"<<endl;return 0; }}//判断回文的循环cout<<"yes"<<endl;return 0;
}

代码分析

引入头文件
```
#include <bits/stdc++.h>
```
- 使用了 bits/stdc++.h 这个头文件，它包含了几乎所有的标准 C++ 库，非常便利，适用于快速编程和竞赛，但在实际的项目中可能不是最佳实践，因为它可能造成不必要的编译开销。
使用命名空间
```
using namespace std;
```
- 使用标准命名空间，以便后续使用标准库的功能时无需加上 std:: 前缀。
主函数开始
```
int main() {
```
读取字符串
```
string s; // 定义字符串
cin >> s; // 输入字符串
```
- 使用 cin >> s; 读取输入的字符串，注意这里读取的字符串不能包含空格。
检查回文
```
for(int i = 0, j = s.length() - 1; i <= s.length() / 2; i++, j--) {if(s[i] != s[j]) {cout << "no" << endl; // 如果不相等，输出 "no"return 0; // 提前结束程序}
}
```
- 使用一个 for 循环来检查字符串的前半部分和后半部分的字符是否相等。
  - i 从 0 开始，表示字符串的前半部分。
  - j 从最后一个字符开始，表示字符串的后半部分。
- i <= s.length() / 2 确保只检查到字符串的中间位置。
- 如果发现有任何不相等的字符，立即输出 “no” 并返回 0 结束程序，表示该字符串不是回文。

输出结果

cout << "yes" << endl; // 如果循环结束，说明是回文，输出 "yes"
return 0;

如果循环顺利结束，表示字符串是回文，则输出 "yes"。

总结

功能：该程序用于判断一个字符串是否是回文字符串。
实现方法：通过双指针技术（一个指向字符串的开头，一个指向字符串的末尾）来逐个比较字符，直到中间为止。
时间复杂度：该算法的时间复杂度为 O(n)，其中 n 是字符串的长度，因为需要遍历字符串的一半进行比较。

评测记录：

五、B2125 最高分数的学生姓名 - 洛谷

算法代码：

#include<bits/stdc++.h>
using namespace std;// 定义一个结构体用于存储学生的姓名和分数
struct node
{string name; // 学生姓名int score;   // 学生成绩
} a[105]; // 定义一个结构体数组，最多存储 104 个学生信息int n, i; // 学生数量和循环变量// 比较函数，用于按照分数降序排列
bool cmp(node c, node b)
{return c.score > b.score; // 分数大的靠前
}int main()
{cin >> n; // 输入学生数量for (i = 1; i <= n; i++){cin >> a[i].score >> a[i].name; // 输入每个学生的分数和姓名}sort(a + 1, a + 1 + n, cmp); // 对学生数组进行排序cout << a[1].name; // 输出分数最高的学生姓名return 0; // 程序正常结束
}

代码思路

包含头文件
- #include<bits/stdc++.h>：这是一个常用的包含所有标准库头文件的快捷方式，虽然在实际编程中不推荐使用，但在竞赛中常见。
定义数据结构
- 使用 struct node 定义一个结构体 node，用于存储学生的姓名和分数。该结构体有两个成员：
  - string name：存储学生的姓名。
  - int score：存储学生的分数。
全局变量
- node a[105]：定义了一个结构体数组 a，可以存储最多 104 个学生的信息（因为数组索引从 1 开始）。
- int n, i：定义了学生数量 n 和循环变量 i。
比较函数
- bool cmp(node c, node b)：定义一个比较函数，用于 sort 函数排序。该函数根据分数进行排序，分数高的排在前面（即降序排序）。实现方式是比较两个节点的 score 字段。
主函数
- cin >> n：读取学生的数量。
- 使用 for 循环从 1 到 n，依次读取每个学生的分数和姓名，并存储到数组 a 中。
- sort(a + 1, a + 1 + n, cmp)：使用 sort 函数对数组 a 进行排序。排序范围是从 a[1] 到 a[n]，使用之前定义的比较函数 cmp。
- cout << a[1].name：输出分数最高的学生的姓名，即排序后数组的第一个元素的 name 字段。
返回语句
- return 0：表示程序成功结束。

复杂度分析

时间复杂度：O(n log n)，其中 n 是学生的数量。排序的时间复杂度为 O(n log n)，由于使用了快速排序或其他高效排序算法。
空间复杂度：O(n)，主要用于存储学生的姓名和分数。

总结

这段代码实现了对学生分数的排序，并找到分数最高的学生。通过使用结构体存储学生信息、比较函数进行排序和标准输入输出，代码结构清晰且高效。适合用于基本的排序和查找问题。

评测记录：

六、B2126 连续出现的字符 - 洛谷

算法代码：


#include<bits/stdc++.h>
using namespace std;char a[1001]; // 用char类型存储字符串int main()
{int n, cnt = 1; // 定义计数器cin >> n >> a; // 输入连续出现的次数和字符串for (int i = 1; i <= strlen(a); i++) // 遍历整个数组{cin >> a[i]; // 输入当前字符if (a[i] == a[i - 1]) cnt++; // 如果与前一个字符相同，计数器+1else cnt = 1; // 否则归1if (cnt == n) // 找到了连续出现n次的字符{cout << a[i]; // 输出该字符return 0; // 结束程序}}cout << "No"; // 如果没有找到，输出"No"return 0; // 程序正常结束
}

代码思路

包含头文件
- #include<bits/stdc++.h>：快速包含所有标准库头文件，常用于竞赛编程。
定义变量
- char a[1001]：定义一个字符数组 a，用于存储输入的字符串，最多可以存储 1000 个字符。
- int n, cnt = 1：定义 n（表示连续出现次数）和 cnt（计数器，初始值为 1）。
读取输入
- cin >> n >> a：首先读取一个整数 n，然后读取字符串 a。
遍历字符串
- 使用 for 循环遍历字符串，从 1 到 strlen(a)（字符串的长度）。注意，a[0] 是第一个字符，因此从 1 开始。
- 在循环内部：
  - cin >> a[i]：读取下一个字符并存储在数组 a[i] 中。
  - if(a[i] == a[i-1]) cnt++：如果当前字符等于前一个字符，则计数器 cnt 加 1。
  - else cnt = 1：如果当前字符与前一个字符不相同，则重置 cnt 为 1。
  - if(cnt == n)：如果计数器 cnt 达到 n，说明找到了连续出现的字符。
    - cout << a[i]：输出该字符，并返回 0，结束程序。
无连续字符的情况
- 如果遍历完字符串后仍未发现有字符连续出现 n 次，输出 "No"。

复杂度分析

时间复杂度：O(m)，其中 m 是字符串的长度。遍历字符串的时间复杂度是线性的。
空间复杂度：O(1)，除了输入的字符串外，没有使用额外的空间。

注意事项

输入方式：代码中使用 cin >> a[i] 存储字符，这可能导致输入字符被覆盖，建议使用 cin 一次性读取字符串，而不是在循环中逐个字符读取。
字符串遍历：字符串的索引从 0 开始，初始的遍历条件需要注意，确保不超出数组边界。
字符串长度：使用 strlen 时需要包含 <cstring> 头文件，此外，使用 std::string 可能更安全和灵活。

改进后的代码示例

为了解决上述问题，以下是一个改进的代码示例，正确输入字符串并遍历：

#include <bits/stdc++.h>
using namespace std;int main() {int n, cnt = 1;string a; // 使用 string 类型代替 char 数组cin >> n >> a; // 输入连续出现的次数和字符串// 从第二个字符开始遍历for (int i = 1; i < a.length(); i++) {if (a[i] == a[i - 1]) cnt++; // 如果与前一个字符相同，计数器+1else cnt = 1; // 否则归1if (cnt == n) { // 找到了连续出现n次的字符cout << a[i]; // 输出该字符return 0; // 结束程序}}cout << "No"; // 如果没有找到，输出"No"return 0; // 程序正常结束
}

这个改进版本避免了字符数组的边界问题，并使用了更为安全和灵活的 string 类型。

评测记录：

七、B3640 T3 句子反转 - 洛谷

算法代码：


#include<bits/stdc++.h>
using namespace std;int n; // 记录字符串数量
string s[1007]; // 存储字符串的数组int main() {while(cin >> s[++n]); // 输入字符串，直到 EOF--n; // 调整 n，减去最后一次自增多余的值// 从最后一个字符串开始处理for(int i = n; i >= 1; i--) {// 遍历当前字符串的每个字符for(int j = 0; j < (int)s[i].size(); j++) {// 将小写字母转换为大写if(s[i][j] >= 'a' && s[i][j] <= 'z') s[i][j] -= 'a' - 'A';// 将大写字母转换为小写else if(s[i][j] >= 'A' && s[i][j] <= 'Z') s[i][j] -= 'A' - 'a'; }// 检查字符串是否以数字开头if(s[i][0] >= '0' && s[i][0] <= '9') {// 如果是数字，输出字符串的反向for(int j = (int)s[i].size() - 1; j >= 0; j--) cout << s[i][j];} else {// 否则正常输出字符串cout << s[i];}// 如果不是最后一个字符串，则输出空格if(i != 1) cout << " ";}return 0; // 程序正常结束
}

代码思路

包含头文件
- #include<bits/stdc++.h>：快速包含所有标准库头文件，常用于竞赛编程。
定义变量
- int n：用于计数，记录输入字符串的数量。
- string s[1007]：定义一个字符串数组 s，容量为 1006（因为索引从 1 开始），用于存储输入的字符串。
读取输入
- 使用 while(cin >> s[++n]) 循环读取字符串，直到输入结束。n 从 0 开始自增，最后 --n 是为了将 n 的值调整为实际的字符串数量（因为最后一次循环后 n 增加了一次）。
处理字符串
- 外层循环 for(int i = n; i >= 1; i--)：从最后一个输入的字符串开始处理。
- 内层循环 for(int j = 0; j < (int)s[i].size(); j++)：遍历每个字符串的字符。
  - 如果字符是小写字母（'a' 到 'z'），则将其转换为大写字母。
  - 如果字符是大写字母（'A' 到 'Z'），则将其转换为小写字母。
- 检查字符串的第一个字符：
  - 如果它是数字（'0' 到 '9'），则反向输出这个字符串。
  - 否则，正向输出这个字符串。
输出格式
- 在输出每个字符串之后，如果不是最后一个字符串，则输出一个空格。

复杂度分析

时间复杂度：O(N * M)，其中 N 是字符串的数量，M 是字符串的平均长度。需要遍历所有字符串及其字符。
空间复杂度：O(N * M)，用于存储字符串数组。

总结

这段代码实现了对输入字符串的处理，包括大小写转换和条件反转。通过使用字符串数组、循环和字符操作，代码结构清晰且功能明确。在实际的应用中，这种处理字符串的方法可以广泛用于多种文本处理任务。

评测记录：

八、B3654 [语言月赛202208] 影子字符串 - 洛谷

算法代码：

#include<bits/stdc++.h>
using namespace std;int cnt; // 记录字符串数量
string s[507]; // 存储字符串的数组int main()
{while(true) // 无限循环，直到遇到 "0"{++cnt; // 计数器自增cin >> s[cnt]; // 读取字符串if(s[cnt] == "0") // 如果输入为 "0" 则退出break;bool flag = false; // 用于标记是否有重复// 检查之前输入的字符串是否与当前字符串重复for(int i = 1; i < cnt; i++){if(s[i] == s[cnt]) // 如果发现重复{flag = true; // 设置标记为 truebreak; // 退出循环}}if(flag == false) // 如果没有重复{cout << s[cnt]; // 输出当前字符串}}return 0; // 程序结束
}

代码思路

包含头文件
- #include<bits/stdc++.h>：包含所有标准库头文件，常用于竞赛编程。
定义变量
- int cnt：用于计数，记录输入字符串的数量。
- string s[507]：定义一个字符串数组 s，可以存储最多 506 个字符串（因为索引从 1 开始）。
读取输入
- 使用 while(true) 循环不断读取字符串。
- cin >> s[cnt] 从标准输入中读取字符串并存储到数组 s 中，同时 cnt 自增。
- 当读取到字符串 “0” 时，使用 break 退出循环。
检查重复
- 在每次读取新的字符串后，定义一个布尔变量 flag，初始值为 false。
- 使用嵌套循环 for(int i=1;i<cnt;i++) 遍历之前输入的字符串，检查是否与当前字符串 s[cnt] 重复：
  - 如果找到重复的字符串，将 flag 设置为 true，并跳出循环。
- 如果 flag 仍为 false，则说明当前字符串未重复，输出该字符串。

复杂度分析

时间复杂度：O(N^2)，其中 N 是输入的字符串数量。在最坏情况下，需检查每个字符串与之前所有字符串的重复情况。
空间复杂度：O(N)，用于存储字符串数组。

改进建议

在处理字符串重复问题时，使用集合（如 std::set）可以更高效地判断字符串是否已经存在，从而将时间复杂度降低到 O(N) 的平均情况。以下是改进后的代码示例：

改进后的代码示例

#include<bits/stdc++.h>
using namespace std;int main() {set<string> unique_strings; // 定义一个集合用于存储唯一字符串string input;while(true) {cin >> input; // 读取输入字符串if(input == "0") // 如果输入为 "0" 则退出break;// 使用集合的 insert 方法插入字符串// 如果插入成功，说明是唯一的，输出字符串if(unique_strings.insert(input).second) {cout << input; // 输出当前唯一字符串}}return 0; // 程序结束
}

说明

在改进后的代码中，使用了 std::set 来存储唯一字符串。insert 方法返回一个 pair，其中第二个元素为 true 表示插入成功（即该字符串是新的，之前没有重复）。
这种方法不仅代码更简洁，而且提高了查找和插入的效率。

重点：根据上面的方法，我们下面来回顾一下pair

在 C++ STL（标准模板库）中，std::pair 是一个用于存储一对值的模板结构。它的定义如下：

template <class T1, class T2>
struct pair {T1 first;   // 第一个值T2 second;  // 第二个值
};

解释

first：pair 的第一个元素，通常用于存储某个主要的信息。
second：pair 的第二个元素，通常用于存储与第一个元素相关的信息。

示例

在 C++ 的 STL 中，std::set::insert 方法返回一个 std::pair，该 pair 的第二个值（second）用于表示插入操作的结果：

如果插入成功，即元素是新的且没有重复，则 second 为 true。
如果插入失败，即元素已经存在于集合中，则 second 为 false。

代码示例

以下是一个简单的示例，演示如何使用 std::pair 以及 std::set::insert 的返回值：

#include <iostream>
#include <set>
using namespace std;int main() {set<string> mySet; // 创建一个字符串集合string input;// 输入一些字符串while (true) {cout << "Enter a string (or '0' to stop): ";cin >> input;if (input == "0") break; // 输入 "0" 结束循环// 尝试插入字符串auto result = mySet.insert(input); // result 是一个 std::pair// result.first 是插入的字符串// result.second 表示插入是否成功if (result.second) {cout << "Inserted: " << result.first << endl; // 输出插入的字符串} else {cout << "Duplicate found: " << result.first << endl; // 输出重复的字符串}}return 0;
}

总结

在这个例子中，我们使用 std::set::insert 方法插入字符串，并通过 result.second 判断字符串是否已经存在。result.first 将返回刚刚插入的字符串。通过这种方式，我们可以方便地处理插入操作的结果。

评测记录：

九、B3663 [语言月赛202209] Luogu Academic - 洛谷

算法代码：

#include<bits/stdc++.h>
using namespace std;string S; // 存储输入的字符串
int ans = 0; // 计数器，初始值为 0int main()
{cin >> S; // 读取输入字符串// 遍历字符串，查找 "luogu" 的出现次数for (int i = 0; i + 4 < (int)S.size(); i++) {// 检查当前字符及后面的四个字符if (S[i] == 'l' && S[i + 1] == 'u' && S[i + 2] == 'o' && S[i + 3] == 'g' && S[i + 4] == 'u') {ans++; // 找到一个 "luogu"，计数加一}}cout << ans << endl; // 输出计数结果return 0; // 程序结束
}

代码思路

包含头文件
- #include<bits/stdc++.h>：这是一个在竞赛编程中常用的包含所有标准库头文件的方式。
定义变量
- string S：用于存储输入的字符串。
- int ans：用于记录子串 “luogu” 出现的次数，初始值为 0。
读取输入
- 使用 cin >> S 读取输入的字符串。
遍历字符串
- 使用 for (int i = 0; i + 4 < (int)S.size(); i++) 循环遍历字符串。这里 i + 4 < (int)S.size() 确保我们在检查子串 “luogu” 时不会越界，因为 “luogu” 的长度是 5。
- 在循环内部，检查当前字符及其后四个字符是否组成子串 "luogu"：
  - if (S[i] == 'l' && S[i + 1] == 'u' && S[i + 2] == 'o' && S[i + 3] == 'g' && S[i + 4] == 'u')。
- 如果匹配，则 ans++，计数增加。
输出结果
- 使用 cout << ans << endl 输出 “luogu” 在字符串中出现的次数。

复杂度分析

时间复杂度：O(N)，其中 N 是字符串 S 的长度。代码需要遍历字符串的每个字符一次。
空间复杂度：O(1)，只使用了常数个额外的变量（S 和 ans）。

总结

这段代码有效地找出了字符串中 “luogu” 子串的出现次数。逻辑简单明了，适合用于基本的字符串查找操作。不过，如果要处理更复杂的模式匹配或查找问题，可以考虑使用更高效的算法，如 KMP 算法或 Rabin-Karp 算法。

评测记录：

十、B3674 [语言月赛202210] 标题修改 - 洛谷

算法代码：

#include<bits/stdc++.h>
using namespace std;int main()
{string s;while(cin>>s){int len =s.length();for(int i= 0;i<len;++i){if(i%2==0){s[i]-=32;}     }cout<<s<<' ';}return 0;
}

代码解析

包含头文件
- #include<bits/stdc++.h>：快速包含所有标准库头文件，常用于竞赛编程。
主函数
- int main()：程序的入口。
读取输入
- while(cin >> s)：循环读取输入的字符串 s，直到没有更多的输入（例如遇到文件结束符 EOF）。
处理字符串
- int len = s.length();：获取当前字符串的长度。
- for(int i = 0; i < len; ++i)：遍历字符串的每个字符。
  - if(i % 2 == 0)：检查当前索引 i 是否为偶数。
    - s[i] -= 32;：将偶数位置的字符转换为大写字母。这里用的是 ASCII 码的转换方式，'A' 的 ASCII 值是 65，'a' 的 ASCII 值是 97，因此 s[i] -= 32 实际上是将小写字母转换为对应的大写字母。
输出结果
- cout << s << ' ';：输出处理后的字符串，并在字符串后加一个空格。

注意事项

ASCII 转换：这种方法依赖于 ASCII 字符集，因此只适用于在 ASCII 范围内的字符（例如英文字母）。如果输入包含非 ASCII 字符（如中文），则可能不会按预期工作。
字符串大小写处理：虽然通过 s[i] -= 32 可以将小写字母转换为大写，但更好的做法是使用 C++ 提供的标准库函数 toupper()，可以提高代码的可读性和可维护性。

改进后的代码示例

下面是一个改进后的代码示例，使用 std::toupper() 函数来处理字符大小写：

#include <bits/stdc++.h>
using namespace std;int main()
{string s;while (cin >> s) // 读取输入字符串{int len = s.length(); // 获取字符串长度for (int i = 0; i < len; ++i){if (i % 2 == 0) // 检查索引是否为偶数{s[i] = toupper(s[i]); // 将字符转换为大写}}cout << s << ' '; // 输出处理后的字符串}return 0; // 程序结束
}