第二次CCF-CSP认证
- 第一道（easy）
- 思路及AC代码
- 第二道（easy）
- 基本思路及AC代码
- 第三道（mid）
- 基本思路及AC代码
- solution 1 (模拟)
- solution 2（KMP）
第一道（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 数组的第一个元素为 -1
maxnext[0] = -1;
// 遍历模式字符串
while (j < str.length()) {
if (k == -1 || str[j] == str[k]) {
j++;
k++;
// 当 str[j] 与 str[k] 不相等时，记录 nextval 值为 k
if (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;
}
