第二次CCF-CSP认证（含C++源码）

第一道（easy）

题目链接

思路及AC代码

#include <bits/stdc++.h>
using namespace std;
//基本思路就是先读一下输入的这堆数字，然后给他排个序，算出每两个相邻数字之间的差值
//然后遍历一下，如果差值为1，用一个外部变量res记录一下啊，否则不做特殊处理
const int N=1010;
int s[N];
int main()
{int n;cin>>n;//读入这堆乱序的数字for(int i=0;i<n;i++){cin>>s[i];}sort(s,s+n);//表示从首地址到末尾排一下序 int res=0;for(int i=0;i<n;i++){//遇到的问题：如果用while就意味这遇到差值为1的时候会陷入死循环导致超时if(s[i+1]-s[i]==1){res++;}}cout <<res<<endl;return 0;
}

第二道（easy）

题目链接

基本思路及AC代码

#include <bits/stdc++.h>
using namespace std;
//前言：
//这题如果使用时间复杂度最优的算法需要使用扫描线的知识，但是这题的数据范围十分有限
//我们可以用暴力的思路来解决 时间复杂度是n*nlogn 扫描线可以做到nlogn；
//基本思路：
//题目的意思是给定几个被染色的矩形，我们需要求出并集，并输出//需要开一个bool数组来标记被染色的矩形
const int N=110;//避免溢出
bool s[N][N];
int main()
{int n;cin>>n;//n表示矩形的个数while(n--){//在读入之前必须要先定义一下int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;//用嵌套for循环先标记一下被染色的数组for(int x=x1;x<x2;x++)//当我们标记到最右上角的矩形的时候，实际上的编号并不是x2//而是x2-1 所以这里边界需要注意控制一下 纵坐标同理for(int y=y1;y<y2;y++)s[x][y]=true;}int res=0;//现在我们只需要遍历整个矩形统计一下被染色的矩形即可for(int i=0;i<N;i++){for(int j=0;j<N;j++){if(s[i][j]==true){res++;}}}cout<<res<<endl;return 0;
}

第三道（mid）

题目链接

基本思路及AC代码

基本思路：KMP算法或者暴力枚举（思路参考y总）
由于本题字符串的长度只有100 可以优先考虑暴力的思路
我们读入一个type0 or1 （注意type是bool类型）表示大小写是否敏感
如果大小写不敏感也就是type=1的时候 我们使用库函数tolower将给定的字符串和目标中所有字母统一变为小写字母 然后再找
如果敏感 我们直接用string里面自带的库函数str.find(s)就能从给出的字符串里找到目标
然后将其输出就好。

solution 1 (模拟)

#include<iostream>
using namespace std;
const int N=110;
string get(string str)
{string res;for(auto c:str)res+=tolower(c);return res;
}
int main()
{string s;cin>>s;int n;bool type;cin>>type>>n;while(n--){string str;cin>>str;if(type && str.find(s)!=-1) cout<<str<<endl;else if(!type&&get(str).find(get(s))!=-1) cout<<str<<endl;//注意两个字符串都要变成小写}return 0;
}

solution 2（KMP）

忘记了的话回顾一下我的文章 BP & KMP算法

#include <iostream>
#include <string>using namespace std;const int N = 110;// 函数功能：将字符串中的所有字母转换为小写形式
// 参数：str - 待转换的字符串
// 返回值：转换为小写后的字符串
string get(string str) {string res;// 遍历字符串中的每个字符for (auto c : str) {// 将字符转换为小写并添加到结果字符串中res += tolower(c);}return res;
}// 函数功能：计算 KMP 算法中的 nextval 数组，用于优化字符串匹配过程
// 参数：str - 模式字符串；maxnext - 存储 nextval 值的数组
void GetNextval(string str, int maxnext[]) {int j = 0, k = -1;// 初始化 nextval 数组的第一个元素为 -1maxnext[0] = -1;// 遍历模式字符串while (j < str.length()) {if (k == -1 || str[j] == str[k]) {j++;k++;// 当 str[j] 与 str[k] 不相等时，记录 nextval 值为 kif (str[j] != str[k]) {maxnext[j] = k;} else {// 当 str[j] 与 str[k] 相等时，nextval 值取 str[k] 的 nextval 值maxnext[j] = maxnext[k];}} else {// 不匹配时，k 回溯到 maxnext[k] 的位置k = maxnext[k];}}
}// 函数功能：使用 KMP 算法在文本串中查找模式串
// 参数：text - 文本串；pattern - 模式串；next - nextval 数组
// 返回值：若找到匹配，返回模式串在文本串中的起始位置；未找到则返回 -1
int kmpSearch(const string& text, const string& pattern, const int next[]) {int i = 0, j = 0;while (i < text.length() && j < pattern.length()) {if (j == -1 || text[i] == pattern[j]) {i++;j++;} else {// 不匹配时，j 回溯到 next[j] 的位置j = next[j];}}// 若 j 等于模式串长度，说明找到了匹配if (j == pattern.length()) {return i - j;}return -1;
}int main() {string t;bool st;int n;// 输入目标字符串cin >> t;// 输入是否区分大小写的标志，true 表示区分，false 表示不区分cin >> st;// 输入待匹配字符串的数量cin >> n;while (n--) {string s;// 输入待匹配的字符串cin >> s;string ss = s;string tt = t;// 如果不区分大小写，将两个字符串都转换为小写if (!st) {ss = get(s);tt = get(t);}int next1[N];// 计算模式串的 nextval 数组GetNextval(tt, next1);// 使用 KMP 算法进行字符串匹配if (kmpSearch(ss, tt, next1) != -1) {// 若找到匹配，输出原始的待匹配字符串cout << s << endl;}}return 0;
}