C++ 竞赛速查手册¶

常用头文件¶

#include <bits/stdc++.h>  // 万能头文件（竞赛常用，非标准）

若需拆分使用：

头文件	内容
`<iostream>`	cin, cout
`<cstdio>`	scanf, printf
`<algorithm>`	sort, lower_bound, unique 等
`<vector>`	vector
`<queue>`	queue, priority_queue
`<stack>`	stack
`<deque>`	deque
`<set>` / `<unordered_set>`	set, multiset, unordered_set, unordered_multiset
`<map>` / `<unordered_map>`	map, unordered_map
`<string>`	string
`<cmath>`	sqrt, pow, log, sin 等
`<cstring>`	memset, memcpy, strlen 等
`<climits>` / `<limits>`	INT_MAX, LLONG_MAX 等
`<numeric>`	accumulate, gcd (C++17)
`<bitset>`	bitset
`<functional>`	greater, function
`<iomanip>`	setprecision, fixed

STL 容器速查表¶

vector¶

vector<int> a(n);          // 大小为 n，默认初始化
vector<int> a(n, 0);       // 大小为 n，初始值 0
vector<int> a = {1, 2, 3}; // 初始化列表

操作	说明	时间复杂度
`a.push_back(x)`	尾部添加	均摊 O(1)
`a.pop_back()`	尾部删除	O(1)
`a[i]` / `a.at(i)`	随机访问	O(1)
`a.front()` / `a.back()`	首/尾元素	O(1)
`a.size()`	元素个数	O(1)
`a.empty()`	是否为空	O(1)
`a.clear()`	清空	O(n)
`a.resize(n)`	调整大小	O(n)
`a.insert(it, x)`	指定位置插入	O(n)
`a.erase(it)`	指定位置删除	O(n)
`a.begin()` / `a.end()`	迭代器	O(1)

string¶

string s = "hello";

操作	说明	时间复杂度
`s += "abc"` / `s.push_back(c)`	拼接	均摊 O(1)
`s.substr(pos, len)`	子串	O(len)
`s.find("abc")`	查找子串	O(n*m)
`s.length()` / `s.size()`	长度	O(1)
`s[i]`	随机访问	O(1)
`s.erase(pos, len)`	删除子串	O(n)
`s.insert(pos, "abc")`	插入	O(n)
`s.replace(pos, len, "abc")`	替换	O(n)
`s.compare(t)` / `s == t`	比较	O(n)
`s.clear()`	清空	O(1)
`s.empty()`	是否为空	O(1)
`getline(cin, s)`	读入一行	O(n)

stack¶

操作	说明	时间复杂度
`s.push(x)`	入栈	O(1)
`s.pop()`	出栈	O(1)
`s.top()`	栈顶	O(1)
`s.size()`	大小	O(1)
`s.empty()`	是否为空	O(1)

queue¶

操作	说明	时间复杂度
`q.push(x)`	入队	O(1)
`q.pop()`	出队	O(1)
`q.front()`	队首	O(1)
`q.back()`	队尾	O(1)
`q.size()`	大小	O(1)
`q.empty()`	是否为空	O(1)

deque¶

操作	说明	时间复杂度
`dq.push_front(x)` / `dq.push_back(x)`	首/尾插入	O(1)
`dq.pop_front()` / `dq.pop_back()`	首/尾删除	O(1)
`dq[i]`	随机访问	O(1)
`dq.front()` / `dq.back()`	首/尾元素	O(1)

priority_queue¶

priority_queue<int> pq;                        // 大顶堆
priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆

操作	说明	时间复杂度
`pq.push(x)`	插入	O(log n)
`pq.pop()`	弹出堆顶	O(log n)
`pq.top()`	查看堆顶	O(1)
`pq.size()`	大小	O(1)
`pq.empty()`	是否为空	O(1)

set / multiset¶

set<int> s;             // 自动去重排序
multiset<int> ms;       // 允许重复

操作	说明	时间复杂度
`s.insert(x)`	插入	O(log n)
`s.erase(x)`	删除（值）	O(log n)
`s.find(x)`	查找	O(log n)
`s.count(x)`	统计个数	O(log n)（注：set 中结果只有 0/1，恒为 O(log n)；multiset 需数重复元素，为 O(log n + k)）
`s.lower_bound(x)`	>= x 的第一个	O(log n)
`s.upper_bound(x)`	> x 的第一个	O(log n)
`s.size()`	大小	O(1)
`s.begin()` / `s.end()`	迭代器	O(1)

map / unordered_map¶

map<string, int> mp;                // 有序，O(log n)
unordered_map<string, int> ump;     // 无序，均摊 O(1)

操作	说明	map	unordered_map
`mp[key] = val`	插入/修改	O(log n)	O(1)
`mp.insert({key, val})`	插入	O(log n)	O(1)
`mp.erase(key)`	删除	O(log n)	O(1)
`mp.find(key)`	查找	O(log n)	O(1)
`mp.count(key)`	是否存在	O(log n)	O(1)
`mp.size()`	大小	O(1)	O(1)

bitset¶

bitset<1000> bs;         // 1000 位

操作	说明	时间复杂度
`bs[i]`	访问第 i 位	O(1)
`bs.set(i)`	置 1	O(1)
`bs.reset(i)`	置 0	O(1)
`bs.flip(i)`	取反	O(1)
`bs.count()`	统计 1 的个数	O(n/w)
`bs.any()`	是否有 1	O(n/w)
`bs.none()`	是否全 0	O(n/w)
`bs &` / `\\|` / `^`	位运算	O(n/w)

常用算法函数¶

函数	说明	头文件	时间复杂度
`sort(a.begin(), a.end())`	排序	`<algorithm>`	O(n log n)
`stable_sort(...)`	稳定排序	`<algorithm>`	O(n log n)
`lower_bound(begin, end, x)`	>= x 的第一个迭代器	`<algorithm>`	O(log n)
`upper_bound(begin, end, x)`	> x 的第一个迭代器	`<algorithm>`	O(log n)
`unique(begin, end)`	去重（需先排序）	`<algorithm>`	O(n)
`reverse(begin, end)`	翻转	`<algorithm>`	O(n)
`next_permutation(begin, end)`	下一个排列	`<algorithm>`	O(n)
`prev_permutation(begin, end)`	上一个排列	`<algorithm>`	O(n)
`max(a, b)` / `min(a, b)`	最大/最小	`<algorithm>`	O(1)
`max_element(begin, end)`	最大值迭代器	`<algorithm>`	O(n)
`min_element(begin, end)`	最小值迭代器	`<algorithm>`	O(n)
`fill(begin, end, val)`	填充	`<algorithm>`	O(n)
`accumulate(begin, end, init)`	求和	`<numeric>`	O(n)
`__gcd(a, b)`	最大公约数	`<algorithm>`	O(log n)
`swap(a, b)`	交换	`<algorithm>`	O(1)
`count(begin, end, val)`	计数	`<algorithm>`	O(n)
`find(begin, end, val)`	查找	`<algorithm>`	O(n)
`binary_search(begin, end, x)`	二分查找	`<algorithm>`	O(log n)
`memset(a, 0, sizeof(a))`	内存填充	`<cstring>`	O(n)
`memcpy(dst, src, sizeof(src))`	内存拷贝	`<cstring>`	O(n)

字符串操作速查¶

// 数字转字符串
string s = to_string(123);

// 字符串转数字
int x = stoi("123");
long long y = stoll("12345678901");
double d = stod("3.14");

// 字符串与字符数组互转
char buf[100];
string s = "hello";
strcpy(buf, s.c_str());
string t(buf);

// sscanf / sprintf
int a, b;
sscanf("1 2", "%d %d", &a, &b);
char buf[100];
sprintf(buf, "%d+%d=%d", a, b, a + b);

// 排序字符串
sort(s.begin(), s.end());

// 大小写转换
transform(s.begin(), s.end(), s.begin(), ::toupper);
transform(s.begin(), s.end(), s.begin(), ::tolower);

// 字符判断
isalpha(c)  // 字母
isdigit(c)  // 数字
isalnum(c)  // 字母或数字
isspace(c)  // 空白字符

数学函数速查¶

函数	说明	头文件
`__gcd(a, b)`	最大公约数	`<algorithm>`
`abs(x)`	绝对值（整数）	`<cstdlib>`
`fabs(x)`	绝对值（浮点）	`<cmath>`
`sqrt(x)`	平方根	`<cmath>`
`pow(x, y)`	x 的 y 次方	`<cmath>`
`log(x)`	自然对数	`<cmath>`
`log2(x)`	以 2 为底的对数	`<cmath>`
`log10(x)`	以 10 为底的对数	`<cmath>`
`ceil(x)`	向上取整	`<cmath>`
`floor(x)`	向下取整	`<cmath>`
`round(x)`	四舍五入	`<cmath>`
`hypot(x, y)`	sqrt(xx + yy)	`<cmath>`

竞赛常用宏定义¶

// 常用类型别名
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

// 输入输出加速
#define FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

// 循环宏
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define rep0(i, n) for (int i = 0; i < (n); i++)

// 常量
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define PI acos(-1.0)

// 调试宏（提交时注释掉）
#define dbg(x) cerr << #x << " = " << (x) << endl

// 最小公倍数
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))

快速读入模板¶

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

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

常见数据类型范围¶

类型	大小	范围	格式符
`int`	4 字节	-2.1 x 10^9 ~ 2.1 x 10^9	`%d`
`unsigned int`	4 字节	0 ~ 4.3 x 10^9	`%u`
`long long`	8 字节	-9.2 x 10^18 ~ 9.2 x 10^18	`%lld`
`unsigned long long`	8 字节	0 ~ 1.8 x 10^19	`%llu`
`float`	4 字节	约 6-7 位有效数字	`%f`
`double`	8 字节	约 15-16 位有效数字	`%lf`
`char`	1 字节	-128 ~ 127	`%c`
`__int128`	16 字节	约 38 位十进制	需手写读写

竞赛常用常量参考：

常量	值
`INT_MAX`	2,147,483,647 (约 2.1 x 10^9)
`INT_MIN`	-2,147,483,648
`LLONG_MAX`	9,223,372,036,854,775,807 (约 9.2 x 10^18)
`LLONG_MIN`	-9,223,372,036,854,775,808
`1e9 + 7`	常用取模数
`1e9 + 9`	备用取模数

输入输出技巧¶

// scanf / printf（比 cin/cout 快）
scanf("%d", &x);
printf("%d\n", x);
printf("%.10lf\n", x);  // 输出 10 位小数

// 整行读入
getline(cin, s);

// 读入带空格的字符串
getline(cin, s);

// 输出控制
cout << fixed << setprecision(10) << x << endl;

// 常见陷阱：cin >> n 之后用 getline 需要先吃掉换行
cin >> n;
cin.ignore();
getline(cin, s);