竞赛算法模板

本模板目标是尽量全地收集典型的算法与数据结构，并为所有内容均添加合理的介绍。

算法尽量精简成函数和公开变量，数据结构尽量使用类包装并减少冗余操作。

除存在溢出或特殊需求时，整数使用 int 类型，需要自行修改类型以符合需求。

涉及区间问题使用易于实现的区间定义，一般采用左闭右开实现，特殊情况有标注。

竞赛技巧

代码模板

包含万能头文件，类型别名，随机数生成器和关闭输入输出同步。

随机数生成器可以使用时间戳 chrono::steady_clock::now().time_since_epoch().count() 作为种子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>  
  
using namespace std;  
  
using f80 = long double;  
using u128 = unsigned __int128;  
using i128 = __int128;  
using u64 = unsigned long long;  
using i64 = long long;  
using u32 = unsigned;  
  
constexpr int inf = 1e9;  
constexpr i64 infl = 1e18;  
  
random_device rd;  
mt19937_64 rnd(rd());  
  
void solve() {  
}  
  
int main() {  
    cin.tie(nullptr), ios::sync_with_stdio(false);  
  
    int t = 1;  
    cin >> t;  
    while (t--) {  
        solve();  
    }  
  
    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
cout << fixed // 精确到小数点后指定精度位
     << setprecision(12) // 设置精度 12 位
     << setw(8) // 至少输出 8 个字符
     << setfill('0') // 不满则用 '0' 字符补齐
     << endl // 输出一个换行符并刷新输出流，可用于交互题
     << flush; // 刷新输出流，可用于交互题

format(fmt, args...) // 字符串格式化函数，c++20 可用
{} {0} // 占位符
{0:06d} // 6位整数，多余位填0
{0:.2f} // 浮点数，精确到小数点后2位

if (cin.eof()) // 判断是否读取到文件末尾，即遇到终止符
cin.get(); // 读取一个字符
cin.peek(); // 获取一个字符，但不读取
cin >> ws; // 丢弃流中的空格和换行符

int op;
while (cin >> op) // 循环从输入流读入数据直到文件末尾

string line;
while (getline(cin, line)) // 循环从输入流读入行直到文件末尾
// CLion 中键入终止符快捷键为 ctrl + D，仅在调试模式下生效

快读/快写

输入输出优化，可替换为其它整数类型，关闭同步后不可与 cin / cout 混用。

1
2
3
4
5
6
7
8
9
10
11
12
13
int read() {
    int sum = 0, fl = 1;
    int ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}

void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

作者： 落萱 _Love