CCF csp认证 小白必看

大家好，欢迎来到IT知识分享网。

c++支持到C++17(还是更高?)；所以学一些封装好的函数功能是必要的—比如STL里的函数；

因为可携带纸质资料，建议打印带入，需要时可翻阅。

【题目概述:】

0-devc++环境配置

配置好你常用的编译版本：

想要调试记得开启下选项:

0.1小tips:

评测机一般 5*10^8 /s；算复杂度比较一下，同数量级就优化常数；

开辟静态数组的小技巧：开辟静态数组的内存空间时，往往将空间设置比真实大小大一点，来防止访问越界问题。例如，上述代码可以只设计一个空间大小为10000的数组，但是往往喜欢比真是大小多10，变为大小为10010的数组。

cin和scanf的对比：cin相对于scanf来说语法更加简单，但是其效率比scanf更低。一个经验是当输入个数小于时两者均可，超过时从效率考虑使用scanf更加合理。

基本上都会包含的头文件：基本上所有的竞赛代码都会包含<iostream>以及<cstring>和<algorithm>三个头文件，因此可以提前写上。

0.1.1 对于统计字符个数【尤其是字母个数】：

不用开结构体，可以直接根据字母对应的ASCII码（一个整数），作为数组的下标去存储。即 用cnt[int(A)]这种直接进行计数；

比如，A-Z，26个，我统计出Z有3个。而int( ‘Z’ ) =120； 我直接arr[ int ( ‘z’ )]++;  即统计了个数；

示例代码:

0.1.2  对于子串重复查找：

类似KMP的思想，不需要重复回溯。比如string  str1=”abc…..zabcd”;(大小为26+4 = 30)；

比如我找‘d’；第一次找到是在下标=3;那么下一次从3的下一位置4开始找，而不需从第2位；

【这里如果是一个字串”abc”，就很明显，比如首次找到匹配是在小标  = 10；也就同时说明了0-9的位置是不匹配的，下一次要从10+1开始,所以下面是pos  = found +1 】

0.1.3 除法涉及浮点数，为避免误差，判断时，挪为另一边，变成乘法；

0.1.4 第二题一般后30%涉及优化: 基本都是 前缀和；

预处理前i项和：

一维前缀和: 求sum( A[i]~A[j] )  ，用pre_sum(j)- pre_sum(i);

        前缀和矩阵本身的计算？  –类似dp;  如下

        学会用递归【即 sum _i = sum_i-1 + a这种，避免每一项都要重新计算；如下】

e.g. -2 安全阈值：

等效变形—0/1的情况与个数的关系；

前i项里0 的个数    =   i- （1的计数—而1的计数就是求和结果；）

从i项起到最后1的个数 = 01总个数 – 0的个数[0的个数用相减就行]；

从第i+n项到第i项之间1的个数 == n- (这之间0的个数)

1-输入输出

#include <iostream> #include <vector> #include <string> #include <sstream> #include <algorithm> #include <iterator> #include <boost/tokenizer.hpp> // 如果使用 Boost 库 using namespace std; int main() { 12 // 读取一个整数 13 int a; 14 cin >> a; 15 cout << "a: " << a << endl; 16 17 // 读取一个字符串 18 string s; 19 cin >> s; 20 cout << "s: " << s << endl; 21 22 // 读取一行文本（包括空格） 23 string line; 24 getline(cin, line); 25 cout << "Line: " << line << endl; 26 27 // 读取多个整数到 vector 中 28 int n; 29 cin >> n; 30 vector<int> nums(n); 31 for (int i = 0; i < n; ++i) { 32 cin >> nums[i]; 33 } 34 cout << "Numbers: "; 35 copy(nums.begin(), nums.end(), ostream_iterator<int>(cout, " ")); 36 cout << endl; 37 38 // 读取多行文本到 vector<string> 中 39 int numLines; 40 cin >> numLines; 41 vector<string> lines(numLines); 42 for (int i = 0; i < numLines; ++i) { 43 getline(cin, lines[i]); 44 } 45 cout << "Lines: "; 46 for (const auto& line : lines) { 47 cout << line << endl; 48 } 49 说明 1. 读取一个整数： o 使用 cin >> a 读取一个整数 a。 2. 读取一个字符串： o 使用 cin >> s 读取一个字符串 s。 3. 读取一行文本（包括空格）： o 使用 getline(cin, line) 读取一行文本，包括空格。 4. 读取多个整数到 vector 中： o 使用 for 循环和 cin 读取多个整数到 vector<int> 中。 5. 读取多行文本到 vector<string> 中： o 使用 for 循环和 getline 读取多行文本到 vector<string> 中。 2. getline() //getline() 是 C++ 标准库中的一个函数，用于从流中读取一行文本，直到遇到换行符。它可以安全地读取一行文本，并且不会导致缓冲区溢出。【分隔符本身不会被存储在 str 中】 std::istream& getline(std::istream& is, std::string& str, char delimiter = '\n'); 参数 •    is：输入流对象，通常是 std::cin。 •    str：用于存储输入字符串的 std::string 对象。 •    delimiter：分隔符，默认为换行符 ('\n')。 返回值 •    成功读取字符串时返回 is 的引用。 •    读取失败时，std::cin 的状态将变为 std::ios_base::failbit。 注意事项 •    安全性：getline() 是安全的，因为它会自动管理缓冲区的大小。 •    方便性：getline() 可以读取包含空格的字符串，并且可以自定义分隔符。 •    int main() { •    5    std::string line; •    6 •    7    std::cout << "Enter a line: "; •    8    if (std::getline(std::cin, line)) { •    9        std::cout << "You entered: " << line << std::endl; •    10    } else { •    11        std::cout << "Failed to read input." << std::endl; •    12    } •       while (std::getline(std::cin, line, ',')) { •          fields.push_back(line); •       } 

2-STL： C++ 中一个强大的库

Standard Template Library，标准模板库

2.1 set #include <set>

1.    有序性：
        o    std::set 中的元素是有序的，默认按照元素的自然排序进行排序（例如，数字从小到大，字符串按字典序排列）。
        o    可以指定自定义比较器来改变排序规则。
2.    唯一性：
        o    std::set 中不允许有重复的元素。如果尝试插入重复的元素，插入操作将失败。
3.    插入与删除：
        o    插入操作通常是 O(log n) 的时间复杂度，因为 std::set 内部使用红黑树实现。
        o    删除操作也是 O(log n) 的时间复杂度。

std::set 的常用操作

 创建 std::set 4int main() { 5 std::set<int> mySet; // 创建一个空的 set 6 std::set<std::string> stringSet; // 创建一个空的 string set 插入元素 1mySet.insert(10); // 插入一个元素 2mySet.insert({20, 30}); // 插入多个元素 删除元素 1mySet.erase(mySet.find(10)); // 删除一个元素 2mySet.erase(mySet.begin(), mySet.end()); // 删除指定范围内的元素 查找元素 1auto it = mySet.find(10); // 查找元素 2if (it != mySet.end()) { 3 std::cout << "Element found: " << *it << std::endl; 4} else { 5 std::cout << "Element not found." << std::endl; 6} 判断元素是否存在 1bool contains = mySet.count(10); // 判断元素是否存在 获取元素数量 1size_t size = mySet.size(); // 获取元素数量 清空容器 1mySet.clear(); // 清空容器 迭代器遍历 1for (const auto& elem : mySet) { 2 std::cout << elem << " "; 3} 4std::cout << std::endl; 5 6for (auto it = mySet.begin(); it != mySet.end(); ++it) { 7 std::cout << *it << " "; 8} 9std::cout << std::endl; 自定义比较器 你还可以使用自定义比较器来改变 std::set 的排序规则。 4struct CustomComparator { 5 bool operator()(const std::string& lhs, const std::string& rhs) const { 6 return lhs.size() < rhs.size(); // 按字符串长度排序 7 } 8}; 9 10int main() { 11 std::set<std::string, CustomComparator> stringSet; 12 stringSet.insert("world"); 13 stringSet.insert("hello"); 14 stringSet.insert("hi"); 15 16 for (const auto& elem : stringSet) { 17 std::cout << elem << " "; 18 } 19 std::cout << std::endl; 20 21 return 0; 22} 性能分析 1. 时间复杂度： o 插入：O(log n) o 删除：O(log n) o 查找：O(log n) 2. 空间复杂度： o O(n)，其中 n 是容器中的元素数量。 int main() { 5 std::set<int> mySet = {10, 20, 30, 40, 50}; 6 7 // 使用迭代器访问元素 8 for (auto it = mySet.begin(); it != mySet.end(); ++it) { 9 std::cout << *it << " "; 10 } 11 std::cout << std::endl; 13 // 使用 range-based for 循环访问元素 14 for (const auto& elem : mySet) { 15 std::cout << elem << " "; 16 } 17 std::cout << std::endl; 19 // 查找元素 20 auto it = mySet.find(30); 21 if (it != mySet.end()) { 22 std::cout << "Found element: " << *it << std::endl; 23 } /* set（集合），是一个内部自动有序且不含重复元素的容器 set只能通过迭代器(iterator)访问 原本无序的元素，被插入set集合后，set内部的元素自动递增排序，并且自动去除了重复元素。 注意：除了vector和string之外的STL容器都不支持*(it+i)的访问方式，因此只能按照如下方式枚举： */ #include <iostream> #include <set> using namespace std; int main() { set<int> st; st.insert(5); st.insert(2); st.insert(6); for (set<int>::iterator it = st.begin(); it != st.end(); it++) { cout << *it << endl; } return 0; } insert(item)：插入元素 find(value)：返回的是set中value所对应的迭代器，也就是value的指针（地址） erase()：删除单个元素、删除一个区间内的所有元素 erase(it)：其中it为所需要删除元素的迭代器。时间复杂度为O(1)。可以结合find()函数来使用 erase(value)：value为所需要删除元素的值 erase(iteratorBegin , iteratorEnd)：删除一个区间内的所有元素 size()：获得set内元素的个数 #include<set> using namespace std; set<类型名> 变量名; set<int> name; set<double> name; set<char> name; set<struct node> name; set<set<int> > name;//注意：> >之间要加空格 set<类型名> array[SIZE]; 

2.2 Vector#include <vector>

std::vector 是一种动态数组,非常适合需要频繁添加或删除元素的场景。
o    std::vector 支持随机访问，可以通过下标（索引）快速访问元素。

 示例代码 下面是一个完整的示例代码，演示了 std::vector 的常见操作。 1#include <iostream> 2#include <vector> 3#include <algorithm> // 用于 std::find 5int main() { // 创 建 vector 5    std::vector<int> myVector; // 创建一个空的 vector 6    std::vector<std::string> stringVector(5, "hello"); // 创建一个包含 5 个 "hello" 的 vector 7    std::vector<double> doubleVector{1.1, 2.2, 3.3}; // 创建一个包含 3 个 double 的 vector 6 std::vector<int> myVector; 7 myVector.push_back(10); 8 myVector.push_back(20); 9 myVector.push_back(30); 10 11 // 插入元素 12 myVector.insert(myVector.begin(), 5); 13 myVector.insert(myVector.begin() + 2, {3, 4, 5}); 14 15 // 删除元素 16 myVector.pop_back(); 17 myVector.erase(myVector.begin() + 2); 18 19 // 访问元素 20 int first = myVector.front(); 21 int last = myVector.back(); 22 int middle = myVector.at(2); 23 24 // 查找元素 25 auto it = std::find(myVector.begin(), myVector.end(), 10); 26 if (it != myVector.end()) { 27 std::cout << "Element found: " << *it << std::endl; 28 } else { 29 std::cout << "Element not found." << std::endl; 30 } 31 32 // 判断元素是否存在 33 bool contains = std::find(myVector.begin(), myVector.end(), 10) != myVector.end(); 34 35 // 获取元素数量 36 size_t size = myVector.size(); 37 38 // 清空容器 39 myVector.clear(); 40 41 // 迭代器遍历 42 for (const auto& elem : myVector) { 43 std::cout << elem << " "; 44 } 45 std::cout << std::endl; 46 47 return 0; 48} // 遍历： for (const auto& field : fields) { 16 std::cout << field << " "; 17 } push_back(item)：vector后面添加一个元素item pop_back()：尾端删除数据 size()：返回vector中所含元素的个数 clear()：一键清空vector中的所有元素 insert(position, item)：根据指定位置在vector中插入元素，v.insert(v.begin()+2,-1) erase() erase(position)：删除指定位置的元素 erase(positionBegin, positionEnd)：删除一个区间的元素 #include<vector> using namespace std; vector<类型名> 变量名; vector<int> name; vector<double> name; vector<char> name; vector<struct node> name; vector<vector<int> > name;//注意：> >之间要加空格 // vector数组就是一个一维数组,如果定义成vector数组的数组，那就是二维数组。 vector<int> array[SZIE]; //二维变长数组 // 在此，我送你一句话非常受用的话：低维是高维的地址。 //访问 vecntor[i]; //修改 vector[i] = value;   

2.3 map #include<map>

 map<string, string> mp; map<string, int> mp; mao<int, node> find(key)：返回键为key的映射的迭代器，用find函数来定位数据出现位置，数据不存在时，返回mp.end() erase： erase(it)：删除迭代器对应的键和值 erase(key)：根据映射的键删除键和值 erase(first, last)：删除左闭右开区间迭代器对应的键和值 size()：返回映射的对数 clear()：返回映射的对数 insert()：插入元素，插入时要构造键值对 empty()：如果map为空，返回true，否则返回false begin()：返回指向map第一个元素的迭代器（地址） end()：返回指向map尾部的迭代器（最后一个元素的下一个地址） rbegin()：返回指向map最后一个元素的迭代器（地址） rend()：返回指向map第一个元素前面(上一个）的逆向迭代器（地址） count()：查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0 lower_bound()：返回一个迭代器，指向键值>= key的第一个元素 upper_bound()：返回一个迭代器，指向键值> key的第一个元素 //注意： //找元素是否存在时，可以使用 ①mp.find() ② mp.count() ③ mp[key] 但是第三种情况，如果不存在对应的key时，会自动创建一个键值对（产生一个额外的键值对空间） 所以为了不增加额外的空间负担，最好使用前两种方法 //添加元素： mp["学习"] = "看书"; mp.insert(make_pair("vegetable", "蔬菜")); mp.insert(pair<string, string>("fruit", "水果")); //访问元素： //迭代器访问 map<string, string>::iterator it; for(it=mp.begin(); it!=mp.end(); it++) { cout << it->first << it->second << endl; } //对指定单个元素访问 map<char, int>::iterator it = mp.find('a'); cout << it->first << " " << it->second << endl; 

2.4 pair #include<utility>

 //pair只含有两个元素，可以看作是只有两个元素的结构体 //初始化定义 pair<string, int> p("111", 1); //带初始值 pair<string, int> p; //不带初始值 //赋值 p = {"wang", 18}; p = make_pair("wang", 18); p = pair<string, int>("wang", 18); pair<int, int> p[20]; //访问 for(int i=0; i<20; i++) { cout << p[i].first << " " << p[i].second << endl; } 

2.5 array

C++ 标准库中的容器类型：std::array — C++11 引入的静态数组容器 ;

1. 固定大小 ;下标访问；
   – 支持 `begin()` 和 `end()` 方法来获取迭代器，用于遍历元素。
   – 支持 `empty()` 方法来判断数组是否为空。
   – 支持 `size()` 方法来获取数组的大小。

2.成员函数：
   – `fill(value)`：填充数组中的所有元素。 【所有赋相同值】  e.g.:  arr.fill(0);
   – `operator[]`：通过索引访问元素。
   – `front()`：获取第一个元素。
   – `back()`：获取最后一个元素。
   – `data()`：获取指向数组元素的指针。

 //创建array ： std::array<int, 5> arr; // 创建一个大小为5的数组，所有元素初始化为默认值（0） std::array<int, 5> arr = {1, 2, 3, 4, 5}; // 使用初始值列表初始化 std::array<int, 5> arr(5, 0); // 使用填充构造函数初始化所有元素为0 //示例完整代码： #include <iostream> #include <array> int main() { // 创建一个大小为5的数组 std::array<int, 5> arr = {1, 2, 3, 4, 5}; // 访问元素 std::cout << << arr.front()<< arr.back() << std::endl; // 输出 : 1 5 // 遍历数组 std::cout << "Elements: "; for (const auto &value : arr) { std::cout << value << " "; } std::cout << std::endl; 

3-字符(串)常见处理:string/cctype

String /cctype 库： 【字符串处理 / 字符分类】

3.1 #include <string>

 【注意：不要定义string a =’1’//应该是”1”】

 #include <string> string 可以动态调整大小，不需要预先确定字符串的长度。 字符串操作(1)查找(2)替换(3)拼接(4)删除子串(5)比较 e.g.: #include <iostream> #include <string> int main() { // 创建 std::string str = "Hello, World!"; //访问by下标/at() : char a= str[0]; char last = str.at(str.size() - 1); //拼接 string str3 = str1 + str2; //长度: size_t len = str.size(); int a=str.length(); // 查找子字符串 size_t pos = str.find("World");// 默认从0下标开始找：返回其W的下标6； //【size_t是无符号整型 32位】 int a = str.find("serach",6);//从指定位置开始找； // 使用 std::replace 替换 'a' 为 'c' replace(str.begin(), str.end(), 'a', 'c'); // 替换子字符串 str.replace(pos, 5, "1234a");//从pos下标的位置开始，替换5位的长度； // 删除字符 str.erase(pos, 8); //从pos开始，删8位 //string::substr() 或者自定义函数来分割字符串。 string part = str.substr(7, 5); // 从7开始，算5位长度："World" // 比较字符串 string str3 = "Hello, Universe!"; bool isEqual = str.compare(str3) ; return 0; // 查找 "World" 的前3个字符 std::string str = "Hello, World!"; const char* cStr = "World"; size_t pos = str.find(cStr, 0, 3); // 查找 "Wor" /* (6)string 类提供了成员函数来获取字符串的长度（如 size() 或 length()）， 因此不需要使用空字符来标记字符串的结束。【char数组末尾是如'\0'】 */ } /* 1. 返回值 npos：如果找不到子字符串或字符，find() 会返回 string::npos【不是-1，一般是size_t的最大，32位除去符号位全为1】。 你需要检查返回值是否等于 npos 【一个已经在库里声明过的全局变量】来确定是否找到了匹配项。 2. 性能考虑：find() 的时间复杂度通常为 O(n)，其中 n 是主字符串的长度。在大型字符串中查找时，性能可能成为一个考虑因素。 3. 多处查找：如果你需要查找所有出现的位置，可以结合循环使用 find()。每次查找后，从上次找到的位置之后开始下一次查找。 */ 

3.2  #include <cctype>

功能:字符分类和转换。【判断 字母/数字/空白字符 / 大小写转换】；

 //下面是一个使用 <cctype> 的示例： #include <iostream> #include <cctype> int main() { char ch = 'A'; // 检查字符是否为字母 bool isLetter = std::isalpha(ch); // 检查字符是否为数字 bool isDigit = std::isdigit(ch); // 检查字符是否为空白字符 bool isSpace = std::isspace(ch); // 检查字符是否为大写字母 bool isUpper = std::isupper(ch); // 转换字符为小写 char lowerCase = std::tolower(ch); // 转换字符为大写 char upperCase = std::toupper(ch) return 0; }