基础模板

以下是我的常用模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include"bits/stdc++.h"
#define ll long long
#define maxn 200005
#define endl '\n'
using namespace std;
void solve() {

}
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

#include"bits/stdc++.h":万能头包含了算法竞赛常用的各种库
#define endl '\n':由于endl换行会强制刷新缓冲区导致输出变慢所以一般换行用\n但是我习惯写endl所以有了这个宏定义（这是个坏习惯）
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);:加快数据的输入和输出（较为关键，可大大提升程序读取和输出数据的速度）
由于很多题目都是有多组测试的，便有了一下模板，在solve()函数里写单组的解

1
2
3
4
5
int t = 1;
cin >> t;
while (t--) {
   solve();
}

输入输出

在算法竞赛中，数据的读写是最基本的操作。虽然我们在模板里已经对 cin 和 cout 进行了加速，但有些特定场景下的读写细节依然需要重点掌握。

基础读写

1
2
3
int a, b;
cin >> a >> b;         // 连续读取两个整数，自动跳过空格和换行
cout << a + b << endl; // 输出结果并换行（这里的 endl 已经被宏定义替换为 '\n'）

格式化输出

1
2
3
4
5
6
7
8
9
10
double ans = 3.14159;
// fixed 表示固定小数位数，setprecision(2) 表示保留两位
cout << fixed << setprecision(2) << ans << endl; // 输出 3.14
int num = 5;
// setw(3) 设置宽度为 3，setfill('0') 表示空缺部分补 0
cout << setw(3) << setfill('0') << num << endl; // 输出 005
double n = 12345.678;
// scientific 表示输出为科学计数法
cout << scientific << setprecision(2) << n << '\n'; 
// 输出类似于 1.23e+04

读取包含空格的字符串

普通的cin >> s遇到空格或者回车就会停止。如果题目给的字符串本身就包含空格（比如 “ H e l l o W o r l d “），你需要用到 getline:

1
2
3
string s;
getline(cin, s); // 读取一整行，直到遇到换行符为止
cout << s << endl;

注：如果在getline之前使用了cin >>读取其他数据（比如数字）cin会把数字后面的回车符留在缓冲区里，导致getline读到一个空串。这时候需要在中间加一句cin.ignore(); 或者手工吃掉那个回车。
如下:

1
2
3
4
5
6
int n;
cin>>n;
cin.ignore();
string s;
getline(cin, s); // 读取一整行，直到遇到换行符为止
cout << s << endl;

循环读取直到文件末尾 (EOF)

有些题目没有告诉你一共有多少组测试数据，只会说“读到文件末尾为止”。此时可以这样写：

1
2
3
4
5
int n;
// 当成功读取到 n 时，cin >> n 返回 true，遇到 EOF 返回 false
while (cin >> n) { 
    solve();
}

结构体 (Struct) 与自定义排序

当你需要将多个相关联的数据打包在一起时（比如二维平面上的坐标 $(x, y)$，或者包含学号、成绩的学生信息），就需要用到结构体。在竞赛中，结构体最常见的应用场景是配合自定义排序。

结构体的定义与基本用法

1
2
3
4
5
6
7
8
9
10
11
struct Node {
    int x, y;
    int val;
} a[100005]; // 直接定义一个结构体数组

int main() {
    a[1].x = 10;
    a[1].y = 20;
    a[1].val = 100;
    // ...
}

结构体排序

详见sort函数的内容

C++ STL 标准模板库入门

STL（Standard Template Library）是 C++ 给大家准备好的“高级数据结构轮子”。熟练掌握它们，能让你省去几百行手写数据结构的代码。在竞赛中，所有的 STL 容器都被包含在了万能头文件 #include <bits/stdc++.h> 中。

超级元组：pair

当结构体里只有两个简单变量时，我们可以直接用 pair，它自带排序规则（优先比较第一个元素，相同再比较第二个），非常适合存坐标或键值对。

1
2
3
4
5
pair<int, int> p1;
p1 = make_pair(1, 2); // 老式写法
pair<int, int> p2 = {3, 4}; // C++11 之后的推荐写法，极其简洁！

cout << p2.first << " " << p2.second << '\n'; // 访问数据用 .first 和 .second

动态数组：vector

不知道数组到底有多长时使用。它在图论中存图（邻接表）时是无可替代的神器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> v; //定义一个vector类型的变量，可以理解为数组
v.push_back(10); // 在末尾插入元素，时间复杂度 O(1)
v.push_back(20);
v.push_back(30);
v.back();//获取v的最后一个元素时间复杂度 O(1)
cout << v.size() << '\n'; // 返回元素个数：3

// 遍历 vector 的经典方式
for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
}
// 或者使用 C++11 的范围 for 循环（更推荐，写起来快）
for (int x : v) {
    cout << x << " ";
}

v.clear(); // 清空 vector

erase的用法

1
2
3
4
5
6
7
8
9
vector<int> v = {10, 20, 30, 40, 50};

// 1. 删除单个元素：删除下标为 1 的元素 (即 20)
v.erase(v.begin() + 1); 
// 现在的 v: {10, 30, 40, 50}

// 2. 删除一个区间：删除下标 1 到下标 2 的元素 (左闭右开)
v.erase(v.begin() + 1, v.begin() + 3); 
// 现在的 v: {10, 50}

注意，erase的时间复杂度是O(n)

set系列

普通set

set内部基于红黑树实现，扔进去的元素会自动按升序排序，并且自动去重。所有增删改查的时间复杂度都是 O(log n)。

1
2
3
4
5
6
7
8
9
10
11
set<int> s;
s.insert(3);
s.insert(1);
s.insert(3); // 重复插入无效

cout << s.size() << '\n'; // 输出 2（因为去重了，只有 1 和 3）

// 查找某个元素是否存在
if (s.count(1)) { // count 返回 1 表示存在，0 表示不存在
    cout << "1 存在于 set 中!\n";
}
1
2
3
4
5
6
7
8
set<int> s = {10, 20, 30, 40};
// 用法 1：直接传值删除（时间复杂度 O(log n)）
s.erase(20); 
// 用法 2：配合 find 传迭代器删除
auto it = s.find(30); // find 返回指向 30 的迭代器，找不到则返回 s.end()
if (it != s.end()) {
    s.erase(it);      // 删除了 30
}

multiset

和set类似，但是可以存重复的元素

1
2
3
4
5
6
7
multiset<int> ms;
ms.insert(10);
ms.insert(10);
ms.insert(20);

cout << ms.size() << '\n';     // 输出 3
cout << ms.count(10) << '\n';  // 输出 2（统计 10 出现的次数）

注意：erase(v)会删除容器内所有值为v的元素，如果只想删除一个的话则可以用以下的方法

1
2
3
4
5
6
7
8
9
multiset<int> ms = {10, 10, 10, 20};
ms.erase(10); // 三个 10 全被删了
cout << ms.size() << '\n'; // 输出 1（只剩下 20）
multiset<int> ms = {10, 10, 10, 20};
auto it = ms.find(10); // 找到第一个 10 的迭代器
if (it != ms.end()) {
    ms.erase(it);      // 只删除了这一个 10
}
cout << ms.size() << '\n'; // 输出 3（还剩两个 10 和一个 20）

字典/映射:map

你可以把 map 看作是一个超级数组，它的下标不再局限于数字，可以是字符串、浮点数，甚至是另一个结构体，它同样基于红黑树，单次操作复杂度为 O(log n)。并且会按key的值排序

1
2
3
4
5
6
7
map<string, int> mp; // 建立 字符串 -> 整数 的映射
mp["apple"] = 10;
mp["banana"] = 20;

mp["apple"]++; // 极其方便的计数操作，现在 apple 的值是 11

cout << mp["banana"] << '\n'; // 输出 20

如果普通的数组下标就能解决问题（比如范围在 1e7 以内），千万不要用 map！map虽然方便，但 O(log n) 的常数非常大

栈

后进先出

1
2
3
4
5
6
7
8
stack<int> st;
st.push(1); // 压栈
st.push(2);
cout << st.top() << '\n'; // 访问栈顶元素，输出 2
st.pop(); // 弹出栈顶元素
if(st.empty()){//empty()判断栈是否为空，若为空则返回true
    cout<<"栈空了"<<endl;
}

队列

普通队列

先进先出

1
2
3
4
5
queue<int> q;
q.push(1); // 入队
q.push(2);
cout << q.front() << '\n'; // 访问队首元素，输出 1
q.pop(); // 弹出队首元素

优先队列

最大/小的数先出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 1. 默认是大根堆（最大的元素在前面）
priority_queue<int> pq_max; 
pq_max.push(3);
pq_max.push(5);
pq_max.push(1);
cout << pq_max.top() << '\n'; // 输出 5

// 2. 怎么定义小根堆？（最小的元素在前面，非常常用！）
priority_queue<int, vector<int>, greater<int>> pq_min; 
pq_min.push(3);
pq_min.push(5);
pq_min.push(1);
cout << pq_min.top() << '\n'; // 输出 1

while(!pq_min.empty()){//判断pq是否为空
    pq_min.pop();//弹出最大/小元素
}

双端队列 (deque)

支持在头部和尾部同时进行快速插入和删除，并且支持像数组一样用下标访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
deque<int> dq;

// 1. 两端插入
dq.push_back(10);  // 在尾部入队：{10}
dq.push_front(20); // 在头部入队：{20, 10}
dq.push_back(30);  // 在尾部入队：{20, 10, 30}

// 2. 访问两端与随机访问
cout << dq.front() << '\n'; // 访问队首元素，输出 20
cout << dq.back() << '\n';  // 访问队尾元素，输出 30
cout << dq[1] << '\n';      // 像数组一样随机访问，输出 10（下标从 0 开始）

// 3. 两端删除
dq.pop_front(); // 弹出队首元素，变成：{10, 30}
dq.pop_back();  // 弹出队尾元素，变成：{10}

// 4. 清空队列
while (!dq.empty()) {
    dq.pop_front(); 
}
// 普通的 queue 和 priority_queue 没有 clear() 方法，只能像上面那样用 while 弹空。
// 但是 deque 和 vector 一样，是有 clear() 方法的，可以直接 dq.clear() 一键清空！

算法竞赛常用的函数

在算法竞赛中，C++ 标准库（STL）和一些内置函数能帮我们省去大量手写基础算法的时间。熟练掌握它们是提速的关键。以下是竞赛中最常碰到的几个核心函数：

排序函数sort

默认是升序排序，时间复杂度是 O(n log n)

1
2
3
4
5
6
7
8
int a[100];
// 对数组前 n 个元素进行升序排序
sort(a, a + n); 
vector<int> v = {4, 1, 3, 2};
// 对 vector 进行升序排序
sort(v.begin(), v.end());
// 如果想降序排序，可以加上 greater<类型>()
sort(a, a + n, greater<int>());

在很多题目中，默认的升序排序并不能满足需求。比如我们要对结构体进行多重条件排序，或者想降序排列，就需要自己定义一个比较函数（一般命名为 cmp），把它作为第三个参数传给 sort。

cmp 函数的核心逻辑是：如果函数返回 true，就表示第一个参数应该排在第二个参数前面。

基础降序排列

1
2
3
4
5
6
7
8
9
10
11
// 自定义比较函数：降序
bool cmp(int a, int b) {
    return a > b; // 如果 a 大于 b，就让 a 排在前面
}

int main() {
    int a[] = {1, 4, 2, 5, 3};
    sort(a, a + 5, cmp); // 传入自定义比较规则
    // 排序后 a 变成：{5, 4, 3, 2, 1}
    return 0;
}

结构体多关键字排序

这就是我们在前面结构体小节提到的核心应用。假设我们有一个学生结构体，要求：先按成绩从高到低排；如果成绩相同，再按学号从低到高排。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Student {
    int id;
    int score;
} stu[100];

// 自定义比较规则
bool cmpStu(Student a, Student b) {
    if (a.score != b.score) {
        return a.score > b.score; // 成绩不同，成绩高的排前面 (降序)
    }
    return a.id < b.id;           // 成绩相同，学号小的排前面 (升序)
}

int main() {
    int n = 3;
    stu[1] = {101, 90};
    stu[2] = {102, 95};
    stu[3] = {103, 90};
    
    // 对结构体数组进行自定义排序
    sort(stu + 1, stu + 1 + n, cmpStu);
    return 0;
}

在编写 cmp 函数时，绝对不能写 <= 或 >= 当比较的两个元素相等时，必须严格返回 false。如果你写了 return a >= b;，当遇到大量相同元素时，sort 内部的指针极易越界，导致程序直接崩溃报错。永远只写 <、>、!= 或 == 的组合逻辑。

二分查找lower_bound和upper_bound

这两个函数必须在有序数组或有序容器中使用，能以 O(log n) 的时间复杂度极快地查找到边界。

  • lower_bound：返回第一个大于等于查找值的元素地址（或迭代器）。
  • upper_bound：返回第一个严格大于查找值的元素地址（或迭代器）。
1
2
3
4
5
6
int a[5] = {1, 2, 2, 4, 5};
// 查找第一个 >= 2 的元素的位置索引（减去首地址 a 得到下标）
int idx1 = lower_bound(a, a + 5, 2) - a; // idx1 = 1

// 查找第一个 > 2 的元素的位置索引
int idx2 = upper_bound(a, a + 5, 2) - a; // idx2 = 3

杂项函数

1
2
3
4
5
6
7
8
9
int x = 10, y = 20;
int m1 = max(x, y); // 返回最大值 20
int m2 = min(x, y); // 返回最小值 10
swap(x, y);         // 交换 x 和 y 的值
    
int z = -5;
int abs_z = abs(z); // 返回绝对值 5
int mx=max({x,y,z});//三个及以上的参数要用大括号括起来
int mn=min({x,y,z});

注意：max和min函数的两个参数类型必须一致

总结与进阶建议

这篇文章整理了算法竞赛中最基础、最高频的语法和 STL 容器工具箱。但请记住，这仅仅是带你走出了“新手村”，C++ 的特性和算法世界的深奥远不止于此（比如 string 的高级处理、位运算的奇技淫巧、更底层的常数优化等）。

在接下来的集训和日常刷题中，给几个核心建议：

  1. 多看大佬的代码： 竞赛圈有一句老话：“读别人的好代码，是提升代码常数和编码思维最快的方式。” 在 Codeforces、洛谷或 Vjudge 上 AC（通过）一道题后，千万不要马上关掉页面！去翻一翻排行榜，看看那些运行时间极短、代码极简的大佬是怎么写的。你会慢慢学到很多神奇的 STL 用法、优雅的宏定义以及极其高效的实现逻辑。
  2. 拒绝死记硬背，靠肌肉记忆： 编程是一门手艺活，语法和模板看十遍不如自己对着题目敲一遍。一开始总是忘记 lower_bound 怎么拼写或者 cmp 怎么写是很正常的，多写几次遇到报错、多调试几次，慢慢就会变成你的本能。
  3. 拥抱 Bug，关注细节： 遇到 WA（答案错误）、TLE（超时）或 RE（运行错误）时不要崩溃。绝大多数新手的坑都在于：数据范围超出 int 忘了开 long long、多组测试数据忘了清空数组或容器。耐心 debug 的过程，就是你硬实力提升的过程。
    算法竞赛是一场厚积薄发的马拉松。前期的基础打得越牢，代码写得越熟练，后期学复杂的图论、动态规划和高级数据结构时就能越专注在“算法思维”上，而不是被“语法”绊倒。