算法竞赛速查手册

头文件

#include <bits/stdc++.h>   // 万能头，包含所有标准库，竞赛首选
using namespace std;

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

输入输出

加速 cin/cout（必加）

ios::sync_with_stdio(false);
cin.tie(nullptr);
// 注意：加速后不能混用 scanf/printf

基本输入

int n; cin >> n;
string s; cin >> s;          // 读到空白符停止
getline(cin, s);             // 读整行（含空格）
// 混合使用时注意 cin >> 后残留换行，需 cin.ignore()

// 读到 EOF
while (cin >> x) { ... }
while (scanf("%d", &x) != EOF) { ... }

// 读整行直到 EOF
string line;
while (getline(cin, line)) { ... }

基本输出

cout << ans << "\n";         // 比 endl 快（endl 会刷缓冲）
printf("%.2f\n", x);        // 格式化输出
cout << fixed << setprecision(6) << x << "\n";  // 小数位数

scanf/printf 格式符

%d   int          %lld  long long
%u   unsigned     %llu  unsigned long long
%f   float        %lf   double
%c   char         %s    字符串
%x   十六进制      %o    八进制

多组测试数据

int T; cin >> T;
while (T--) {
    // 每组逻辑
}

字符串

string s = "hello";
string s(5, 'a');            // "aaaaa"

// 长度
s.size(); s.length();        // 同义，返回 size_t（无符号）
(int)s.size();               // 避免与 int 比较时符号问题

// 访问
s[0]; s.front(); s.back();

// 拼接
s += "world";
s = s + "!";

// 子串
s.substr(pos, len);          // 从 pos 开始取 len 个字符
s.substr(pos);               // 从 pos 到末尾

// 查找（找不到返回 string::npos）
s.find("ll");                // 第一次出现的位置
s.rfind("l");                // 最后一次出现
s.find('l', 3);              // 从位置3开始找
if (s.find("xx") != string::npos) { ... }

// 替换 & 插入 & 删除
s.replace(pos, len, "new");
s.insert(pos, "abc");
s.erase(pos, len);
s.erase(pos);                // 删除 pos 到末尾

// 比较（字典序）
s1 < s2; s1 == s2;

// 转换
reverse(s.begin(), s.end());
sort(s.begin(), s.end());

// 字符判断（#include <cctype>）
isdigit(c); isalpha(c); islower(c); isupper(c); isspace(c);
tolower(c); toupper(c);

// 数字与字符串互转
string t = to_string(123);      // int/ll → string
int x = stoi("42");             // string → int（十进制）
ll y  = stoll("1234567890");    // string → long long
double d = stod("3.14");        // string → double

// 指定进制的字符串转整数（第二参数为末尾指针，第三参数为进制，0=自动识别）
// stoi / stol / stoll（C++ 风格，base 范围 2~36，0=自动）
int a = stoi("ff", nullptr, 16);      // 十六进制 "ff"  → 255
int b = stoi("1010", nullptr, 2);     // 二进制 "1010" → 10
int c = stoi("77", nullptr, 8);       // 八进制 "77"   → 63
int d2= stoi("0xFF", nullptr, 0);     // 自动识别（0x前缀→16进制）→ 255
int e = stoi("010", nullptr, 0);      // 自动识别（0前缀→8进制）  → 8
ll  f = stoll("7fffffffffffffff", nullptr, 16); // 十六进制 → ll

// strtol / strtoll（C 风格，更灵活，可获取解析终止位置）
char* end;
long  g = strtol("ff", &end, 16);    // end 指向解析停止处
long long h = strtoll("1010", nullptr, 2);

// 整数转指定进制字符串（标准库无直接支持，用 stringstream 或手写）
// 十六进制（大写 HEX，小写 hex）
stringstream ss;
ss << hex << 255;          // "ff"
ss << uppercase << hex << 255; // "FF"
ss << oct << 8;            // "10"（八进制）
string hexStr = ss.str();

// 也可用 printf/sprintf
char buf[64];
sprintf(buf, "%x", 255);   // "ff"
sprintf(buf, "%X", 255);   // "FF"
sprintf(buf, "%o", 8);     // "10"
string s2(buf);

// 字符串流（灵活格式化）
#include <sstream>
stringstream ss;
ss << 42 << " " << 3.14;
string res = ss.str();
// 解析
ss.clear(); ss.str("1 2 3");
int a, b, c; ss >> a >> b >> c;

// 按字符遍历
for (char c : s) { ... }
for (int i = 0; i < (int)s.size(); i++) { ... }

vector

vector<int> v;
vector<int> v(n, 0);         // n 个 0
vector<int> v = {1, 2, 3};
vector<vector<int>> g(n, vector<int>(m, 0));  // 二维

// 增删
v.push_back(x);
v.pop_back();
v.insert(v.begin() + i, x); // 在位置 i 插入（O(n)）
v.erase(v.begin() + i);     // 删除位置 i（O(n)）
v.erase(v.begin()+l, v.begin()+r); // 删除 [l, r)

// 访问
v[i]; v.front(); v.back();
v.size(); v.empty();

// 遍历
for (int x : v) { ... }
for (int i = 0; i < (int)v.size(); i++) { ... }

// 修改
v.assign(n, val);            // 重新赋值为 n 个 val
v.resize(n);                 // 改变大小
v.clear();

// 排序 & 二分（需有序）
sort(v.begin(), v.end());                          // 升序
sort(v.begin(), v.end(), greater<int>());          // 降序
sort(v.begin(), v.end(), [](int a, int b){ return a > b; }); // 自定义

// 去重（先排序）
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

// 反转
reverse(v.begin(), v.end());

// 填充
fill(v.begin(), v.end(), val);

// 复制
vector<int> u = v;           // 深拷贝

pair & tuple

// pair
pair<int,int> p = {1, 2};
pair<int,int> p = make_pair(1, 2);
p.first; p.second;
// pair 默认按 first 升序，first 相同按 second 升序

// 结构化绑定（C++17）
auto [a, b] = p;

// tuple
tuple<int,int,string> t = {1, 2, "hi"};
get<0>(t); get<1>(t); get<2>(t);
auto [x, y, z] = t;          // C++17 结构化绑定

// 排序 pair 数组（按 first 升序，first 相同按 second 降序）
sort(v.begin(), v.end(), [](auto& a, auto& b){
    return a.first != b.first ? a.first < b.first : a.second > b.second;
});

stack / queue / deque

stack（后进先出）

stack<int> st;
st.push(x);
st.top();
st.pop();
st.empty(); st.size();

queue（先进先出）

queue<int> q;
q.push(x);
q.front(); q.back();
q.pop();
q.empty(); q.size();

deque（双端队列）

deque<int> dq;
dq.push_front(x); dq.push_back(x);
dq.pop_front();   dq.pop_back();
dq.front();       dq.back();
dq[i];            // 支持随机访问
dq.size(); dq.empty();

priority_queue

// 大根堆（默认，堆顶最大）
priority_queue<int> pq;

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

// pair 大根堆（按 first 降序）
priority_queue<pair<int,int>> pq;

// 自定义比较（小根堆写法）
auto cmp = [](int a, int b){ return a > b; }; // 返回true表示a优先级低
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

pq.push(x);
pq.top();          // 堆顶（不弹出）
pq.pop();          // 弹出堆顶
pq.empty(); pq.size();

set / multiset

set<int> s;                  // 元素唯一，自动升序
multiset<int> ms;            // 允许重复

s.insert(x);
s.erase(x);                  // 删除所有值为 x 的元素
s.erase(s.find(x));          // 只删除一个（multiset 用）
s.count(x);                  // 0 或 1（set），出现次数（multiset）
s.find(x);                   // 返回迭代器，找不到返回 s.end()
s.size(); s.empty();
s.clear();

// 有序相关
s.lower_bound(x);            // 第一个 >= x 的迭代器
s.upper_bound(x);            // 第一个 > x 的迭代器
*s.begin();                  // 最小值
*s.rbegin();                 // 最大值（最后一个元素）

// 遍历（升序）
for (int x : s) { ... }

// 降序 set
set<int, greater<int>> s;

map / multimap

map<string, int> mp;         // key 有序（按 key 升序）
multimap<string, int> mmp;   // 允许重复 key

mp["key"] = val;             // 不存在时自动创建（默认值0）
mp.insert({key, val});
mp.erase(key);
mp.count(key);               // 0 或 1
mp.find(key);                // 迭代器
mp.size(); mp.empty();

// 访问（key 不存在时会插入！用 find 替代）
if (mp.count(key)) { int v = mp[key]; }
auto it = mp.find(key);
if (it != mp.end()) { it->second; }

// 遍历
for (auto& [k, v] : mp) { ... }  // C++17
for (auto& p : mp) { p.first; p.second; }

// 有序操作
mp.lower_bound(key);
mp.upper_bound(key);

unordered_map / unordered_set

// 哈希表，O(1) 平均，不保证顺序
unordered_map<int, int> ump;
unordered_set<int> us;

// 用法与 map/set 相同，但不支持 lower_bound/upper_bound
// 注意：极端情况下哈希碰撞导致 O(n)，竞赛中可能被卡
// 防卡方案：
struct custom_hash {
    size_t operator()(int x) const {
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        return (x >> 16) ^ x;
    }
};
unordered_map<int, int, custom_hash> safe_map;

bitset

bitset<32> bs;               // 32位，初始全0
bitset<32> bs(42);           // 从整数构造
bitset<32> bs("1010");       // 从字符串构造

bs.set(i);                   // 第 i 位置1
bs.reset(i);                 // 第 i 位置0
bs.flip(i);                  // 第 i 位取反
bs.flip();                   // 全部取反
bs[i];                       // 访问第 i 位

bs.count();                  // 1 的个数
bs.any();                    // 是否有1
bs.none();                   // 是否全0
bs.all();                    // 是否全1

bs.to_ulong();               // 转 unsigned long
bs.to_string();              // 转字符串 "0101..."

// 支持位运算 &, |, ^, ~, <<, >>
bitset<8> a("10110"), b("01101");
a & b; a | b; a ^ b;

常用算法函数

排序

sort(a, a+n);                         // 数组升序
sort(v.begin(), v.end());             // 容器升序
sort(v.begin(), v.end(), greater<int>()); // 降序
stable_sort(...);                     // 稳定排序

// 自定义（结构体排序）
struct Node { int x, y; };
sort(nodes.begin(), nodes.end(), [](const Node& a, const Node& b){
    return a.x != b.x ? a.x < b.x : a.y < b.y;
});

二分查找（需有序）

// 返回指向第一个 >= val 的迭代器/指针
lower_bound(v.begin(), v.end(), val);
lower_bound(a, a+n, val);

// 返回指向第一个 > val 的迭代器/指针
upper_bound(v.begin(), v.end(), val);

// 判断元素是否存在
binary_search(v.begin(), v.end(), val);  // 返回 bool

// 示例：找 val 在有序数组中的个数
int cnt = upper_bound(v.begin(), v.end(), val)
        - lower_bound(v.begin(), v.end(), val);

// 找第一个 >= val 的下标
int idx = lower_bound(v.begin(), v.end(), val) - v.begin();

最值

max(a, b); min(a, b);
max({a, b, c});              // C++11 初始化列表
min({a, b, c});

// 迭代器版
*max_element(v.begin(), v.end());
*min_element(v.begin(), v.end());
// 返回迭代器，取下标：
int idx = max_element(v.begin(), v.end()) - v.begin();

// 限制范围
clamp(x, lo, hi);           // C++17，等价于 min(max(x,lo),hi)

其他常用

// 全排列
sort(v.begin(), v.end());
do {
    // 处理当前排列
} while (next_permutation(v.begin(), v.end()));
prev_permutation(v.begin(), v.end()); // 上一个排列

// 反转
reverse(v.begin(), v.end());

// 填充
fill(v.begin(), v.end(), val);
memset(arr, 0, sizeof(arr));   // 只用于0或-1(0xff)
memset(arr, 0x3f, sizeof(arr));// 赋极大值（每字节0x3f）

// 累加 / 累乘
accumulate(v.begin(), v.end(), 0);       // 求和，初始值0
accumulate(v.begin(), v.end(), 1LL, multiplies<ll>()); // 求积

// 计数
count(v.begin(), v.end(), val);          // 等于 val 的个数
count_if(v.begin(), v.end(), [](int x){ return x > 0; });

// 查找
find(v.begin(), v.end(), val);           // 返回迭代器

// 复制
copy(src.begin(), src.end(), dst.begin());

// 去重（先排序）
v.erase(unique(v.begin(), v.end()), v.end());

// 区间移位
rotate(v.begin(), v.begin()+k, v.end()); // 左移 k 位

// 归并（两个有序区间）
merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));

// 集合操作（需有序）
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
set_intersection(...);
set_difference(...);

数学工具

// 绝对值
abs(x);                      // int/long long（需 <cstdlib> 或万能头）
fabs(x);                     // double

// 幂、根号、对数
pow(base, exp);              // double，注意精度！整数幂手写
sqrt(x);
log(x); log2(x); log10(x);
ceil(x); floor(x); round(x);

// 最大公约数 / 最小公倍数（C++17）
__gcd(a, b);                 // 旧写法，仍可用
gcd(a, b);                   // C++17 <numeric>
lcm(a, b);                   // C++17 <numeric>

// 取模注意负数
((a % m) + m) % m;           // 保证结果非负

// 常用常量
const int INF = 0x3f3f3f3f;  // ~1e9，常用极大值，两个相加不溢出int
const ll LINF = 0x3f3f3f3f3f3f3f3fLL; // ll 极大值
const double PI = acos(-1.0);
const double EPS = 1e-9;     // 浮点比较精度

// 快速幂（手写）
ll qpow(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

代码简化技巧

宏定义

#define rep(i,l,r) for(int i=(l);i<(r);i++)
#define per(i,r,l) for(int i=(r)-1;i>=(l);i--)
#define all(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define eb emplace_back  // 比 push_back 少一次拷贝

// 用法示例
rep(i, 0, n) v[i] = i;
sort(all(v));
v.pb(42);

Lambda & 简化写法

// 自动类型推导
auto x = 1LL;
auto it = mp.find(key);

// Range-based for（引用避免拷贝）
for (auto& x : v) x *= 2;
for (const auto& [k, v] : mp) cout << k << " " << v << "\n";

// 三目运算符
int res = (a > b) ? a : b;

// 初始化列表
vector<int> v = {1,2,3,4,5};
map<int,int> mp = {{1,2},{3,4}};

// 多变量交换
swap(a, b);
tie(a, b) = make_pair(b, a);  // 同时更新多个变量

// 读入多个值
int a, b, c;
cin >> a >> b >> c;

// 输出 Yes/No
cout << (ok ? "YES" : "NO") << "\n";

数组初始化

int a[105] = {};             // 全部初始化为0
int a[105][105] = {};        // 二维同理
fill(a, a+n, val);
memset(a, 0, sizeof(a));
memset(a, -1, sizeof(a));    // 全部设为-1（每字节0xff）
memset(a, 0x3f, sizeof(a));  // 全部设为极大值（每字节0x3f）

常见模板

// 离散化
vector<int> vals = {3,1,4,1,5,9,2,6};
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
auto getid = [&](int x) {
    return lower_bound(all(vals), x) - vals.begin();
};

// 前缀和
vector<int> pre(n+1, 0);
for (int i = 0; i < n; i++) pre[i+1] = pre[i] + a[i];
int sum = pre[r+1] - pre[l];  // 区间 [l, r] 之和

// 差分数组
vector<int> diff(n+1, 0);
// 区间 [l,r] 加 val：
diff[l] += val; diff[r+1] -= val;
// 还原：
for (int i = 1; i < n; i++) diff[i] += diff[i-1];

// 邻接表建图
vector<vector<int>> adj(n);
adj[u].push_back(v);
adj[v].push_back(u);  // 无向图

// 带权邻接表
vector<vector<pair<int,int>>> adj(n);
adj[u].push_back({v, w});