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;
}