CCF csp认证 小白必看
c++支持到C++17(还是更高?)；所以学一些封装好的函数功能是必要的---比如STL里的函数；
因为可携带纸质资料，建议打印带入，需要时可翻阅。
【题目概述:】
0-devc++环境配置
配置好你常用的编译版本：
想要调试记得开启下选项:
0.1小tips:
评测机一般 5*10^8 /s；算复杂度比较一下，同数量级就优化常数；
开辟静态数组的小技巧：开辟静态数组的内存空间时，往往将空间设置比真实大小大一点，来防止访问越界问题。例如，上述代码可以只设计一个空间大小为10000的数组，但是往往喜欢比真是大小多10，变为大小为10010的数组。
cin和scanf的对比：cin相对于scanf来说语法更加简单，但是其效率比scanf更低。一个经验是当输入个数小于100000时两者均可，超过100000时从效率考虑使用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. 202012 -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::find5int 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()`：获取指向数组元素的指针。3.可比较性 ：
- 支持比较操作符（`==`, `!=`, `<`, `<=`, `>`, `>=`），可以比较两个 `std::array` 是否相等或进行排序。
//创建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;
}