本文是一份面向 ACM/ICPC 算法竞赛的 C++17 模板与速查手册，整理了竞赛中常用的数据结构、图论、动态规划、数学、字符串、计算几何等各类算法模板与速查内容。

文章覆盖基础输入输出、调试技巧、高级图论、数论模板等十四个章节，并附有算法选择速查表与常用公式。所有代码均基于 C++17 标准，可直接在竞赛环境中使用。

比赛时先求正确，再求漂亮。漂亮代码不会替错误答案领奖。

本文的pdf版本以及其他acm算法模板资料：https://github.com/dcjaychou-design/acm-icpc-cpp17-reference

基本信息

项目 内容
作者 dcjoker
邮箱 dcjaychou@gmail.com
最后更新 2026 年 5 月 13 日

文章目录

内容总览

部分 主要内容
第 1 章 赛场速查与基本约定 题面信号、复杂度、整数范围、提交前检查
第 2 章 C++17 基础模板 主函数、输入输出、调试宏、__int128、哈希
第 3 章 枚举、前缀、差分、双指针与二分 子集枚举、前缀和、差分、离散化、二分
第 4 章 排序、贪心与基础题型 区间调度、最小合并代价、逆序对、括号匹配
第 5 章 数据结构 单调栈、单调队列、并查集、树状数组、线段树
第 6 章 图论 BFS、最短路、MST、LCA、SCC、最大流、2-SAT
第 7 章 动态规划 背包、LIS、LCS、区间 DP、树形 DP、数位 DP
第 8 章 字符串 KMP、Z 函数、Trie、哈希、Manacher、AC 自动机
第 9 章 数学与数论 gcd、逆元、筛法、组合数、CRT、矩阵快速幂
第 10 章 计算几何 点与向量、线段相交、面积、凸包、距离
第 11 章 搜索、构造、博弈与杂项 DFS、BFS、A*、位运算、Nim、SG、bitset
第 12 章 常见题型速用模板 高频模型与直接可套用模板
第 13 章 调试、对拍与赛前检查 bug 定位、对拍、边界样例、赛前自检
第 14 章 速查表 算法选型、STL、模运算、二分边界
附录 常用公式与代码片段索引

第 1 章 赛场速查与基本约定

1.1 从题面信号到算法

题面信号 优先思路 常用模板与提醒
最大值最小、最小值最大、答案单调 二分答案 先写 check(x)，确认单调性再二分。
大量静态区间和、区间矩形和 前缀和 / 二维前缀和 预处理一次，查询 O(1)。
区间加，最后统一输出 差分 在线查询不适合差分。
单点修改 + 区间和 树状数组 最常见动态求和结构。
区间修改 + 区间查询 线段树懒标记 注意 push 与边界。
连通块、合并集合、判环 并查集 最小生成树也常配合使用。
无权最短路、最少步数 BFS 首次到达即最短。
边权 0/1 最短路 0-1 BFS 双端队列。
非负边权最短路 Dijkstra 负边不能用。
允许负边、判负环 Bellman-Ford / SPFA 判环 看规模，SPFA 不作复杂度保证。
小图多源最短路 Floyd n 通常不宜超过几百。
任务依赖、先后顺序 拓扑排序 可顺手判环。
树上祖先、距离查询 LCA 倍增 DFS 建树，注意根。
强连通分量、缩点 Tarjan SCC 有向图常用。
选或不选、容量限制 背包 DP 0/1 倒序，完全背包正序。
子集状态，n ≤ 20 状态压缩 DP 复杂度常见 n·2^n。
数字位约束、区间计数 数位 DP 记忆化搜索写法更稳。
最长上升子序列 LIS O(n log n) 用 lower_bound。
模式串匹配 KMP / Z 函数 精确匹配、周期性质。
多模式匹配 AC 自动机 字典树 + fail 指针。
回文子串 Manacher / 回文 DP 需要最长回文时优先 Manacher。
质数、因子、整除 筛法 / 质因数分解 看 n 与询问次数。
模意义组合数 阶乘逆元 / Lucas 模数是否为质数非常关键。
线段相交、凸包、面积 计算几何 先统一精度与叉积方向。

1.2 复杂度与数据范围

数据范围 常见可接受复杂度 典型算法
n ≤ 20 2^n、n·2^n、3^n 视常数 子集枚举、状压 DP、Meet-in-the-Middle
n ≤ 100 n^3 Floyd、区间 DP、三重枚举
n ≤ 1000 n^2 LCS、朴素 DP、二维转移
n ≤ 10^5 n log n 排序、堆、树状数组、线段树、Dijkstra
n ≤ 10^6 n 或常数较小的 n log n 前缀和、双指针、筛法、哈希
n ≤ 10^9 log n、√n 或数学公式 快速幂、二分、试除分解

复杂度估算经验

  • 10^7 级别简单整数操作通常可接受，10^8 往往开始冒烟。

  • map/set 的常数显著大于数组与 vector，别把所有题都写成红黑树展览。

  • 多组数据要看“总和限制”。没有总和限制时，按每组都取最大估算。

1.3 整数范围、下标与初始化

类型 典型范围 使用提醒
int 约 ±2.1 × 10^9 数组下标、普通计数。乘法容易溢出。
long long 约 ±9.22 × 10^18 距离、答案、前缀和首选。
__int128 远大于 long long 大乘法、中间过程防溢出。
double 约 15 位有效数字 几何与实数二分。用 eps 比较。

常见溢出

  • int * int 会先按 int 计算，再赋给 long long。写成 1LL * a * b。

  • Dijkstra 的 dist[u] + w 可能溢出，INFLL 不要取到 LLONG_MAX。

  • 组合数乘法和 CRT 中间项常要 __int128。

1.4 提交前检查清单

  • 变量类型是否足够大。

  • 取模减法是否加了 MOD。

  • 数组是否开到 n + 5 或需要的上界。

  • 树 DFS 是否可能爆栈。

  • 多组数据是否清空图、队列、计数器。

  • 输出格式是否严格一致。

  • 图是有向还是无向，边是否加反。

  • 空集、单元素、全相等、全极端值是否测过。

  • 二分边界是否会死循环。

  • 读入字符串前是否处理换行。

  • 最短路是否误用 Dijkstra 跑负边。

  • 坐标与下标从 0 还是 1，是否一致。

第 2 章 C++17 基础模板

2.1 通用主函数与常量

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

const int INF = 0x3f3f3f3f;
const ll INFLL = (1LL << 62);
const int MOD = 1000000007;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template<class T>
bool chmax(T& a, const T& b) {
    if (a < b) { a = b; return true; }
    return false;
}
template<class T>
bool chmin(T& a, const T& b) {
    if (b < a) { a = b; return true; }
    return false;
}

void solve() {
    // write solution here
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

2.2 多组数据与常见输入方式

2.2.1 已知组数 T

int T;
cin >> T;
while (T--) solve();

2.2.2 读到 EOF

int n, m;
while (cin >> n >> m) {
    // solve one case
}

2.2.3 哨兵结束

int n;
while (cin >> n && n) {
    // n == 0 stops
}

2.2.4 带 Case 编号

int T;
cin >> T;
for (int tc = 1; tc <= T; ++tc) {
    cout << "Case #" << tc << ": ";
    solve();
}

2.3 调试宏与条件输出

#ifdef LOCAL
#define dbg(x) cerr << "[DBG] " << #x << " = " << (x) << '\n'
#else
#define dbg(x) ((void)0)
#endif

template<class T>
void printVec(const vector<T>& a) {
#ifdef LOCAL
    cerr << "[";
    for (int i = 0; i < (int)a.size(); ++i) {
         if (i) cerr << ", ";
         cerr << a[i];
    }

      cerr << "]\n";
#endif
}

调试原则
本地调试输出写到 cerr，并用 LOCAL 宏包住。提交前不需要手忙脚乱删一堆 cout，人类已经有足够多
的低级事故。

2.4 排序、去重与自定义比较

vector<int> a = {4, 1, 4, 2, 2, 3};
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());

struct Node {
      int x, y;
};

// x 升序，x 相同按 y 降序
sort(v.begin(), v.end(), [](const Node& a, const Node& b) {
      if (a.x != b.x) return a.x < b.x;
      return a.y > b.y;
});

2.5 __int128 输入输出

using i128 = __int128_t;

i128 read128() {
      string s;
      cin >> s;
      int sign = 1, pos = 0;
      if (s[0] == '-') sign = -1, pos = 1;
      i128 x = 0;
      for (; pos < (int)s.size(); ++pos) {
          x = x * 10 + (s[pos] - '0');
      }
      return sign == 1 ? x : -x;
}

void print128(i128 x) {
      if (x == 0) {
          cout << 0;
          return;
      }
      if (x < 0) {
          cout << '-';
          x = -x;

    }
    string s;
    while (x) {
         s.push_back(char('0' + x % 10));
         x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}

2.6 浮点比较与实数格式

const double EPS = 1e-9;

int sgn(double x) {
    if (fabs(x) < EPS) return 0;
    return x < 0 ? -1 : 1;
}
bool eq(double a, double b) { return fabs(a - b) < EPS; }
bool lt(double a, double b) { return a < b - EPS; }
bool le(double a, double b) { return a < b + EPS; }

double ans = 3.141592653589793;
cout << fixed << setprecision(10) << ans << '\n';

2.7 整行读取、字符串切分、字符处理

2.7.1 先读整数再读整行

int n;
cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), '\n');

string line;
getline(cin, line);

2.7.2 用 stringstream 切分

string line;
getline(cin, line);
stringstream ss(line);

int x;
vector<int> a;
while (ss >> x) a.push_back(x);

2.7.3 字符大小写与数字

char c = 'A';
c = tolower(c); // 'a'

bool isDigit = isdigit(c);
bool isLetter = isalpha(c);

2.8 pair、tuple 与结构化绑定

pair<int, int> p = {3, 5};
auto [x, y] = p;

tuple<int, int, string> t = {1, 2, "ok"};
auto [a, b, s] = t;

2.9 随机数

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

int randInt(int l, int r) {
     return uniform_int_distribution<int>(l, r)(rng);
}
long long randLL(long long l, long long r) {
     return uniform_int_distribution<long long>(l, r)(rng);
}

2.10 自定义哈希，防止 unordered_map 被卡

struct CustomHash {
     static uint64_t splitmix64(uint64_t x) {
         x += 0x9e3779b97f4a7c15ULL;
         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
         x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
         return x ^ (x >> 31);
     }
     size_t operator()(uint64_t x) const {
         static const uint64_t FIXED_RANDOM =
             chrono::steady_clock::now().time_since_epoch().count();
         return splitmix64(x + FIXED_RANDOM);
     }
};

unordered_map<long long, int, CustomHash> mp;

第 3 章 枚举、前缀、差分、双指针与二分

3.1 子集枚举

3.1.1 枚举 0 ∼ 2n − 1

int n;
for (int mask = 0; mask < (1 << n); ++mask) {
     for (int i = 0; i < n; ++i) {
         if (mask >> i & 1) {
             // choose i
         }
     }
}

3.1.2 枚举一个集合的所有子集

for (int sub = mask; ; sub = (sub - 1) & mask) {
     // sub is a subset of mask
     if (sub == 0) break;
}

3.1.3 Meet-in-the-Middle 思路

当 n 约为 40，直接 2n 不现实，可拆成两半分别枚举，再排序或双指针合并。

3.2 一维前缀和

vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; ++i) {
     pre[i] = pre[i - 1] + a[i];
}

long long sumRange(int l, int r) {
     return pre[r] - pre[l - 1];
}

3.3 二维前缀和

vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
     for (int j = 1; j <= m; ++j) {

         s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
     }
}

long long sumRect(int x1, int y1, int x2, int y2) {
     return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

3.4 差分

3.4.1 一维差分

vector<long long> diff(n + 2, 0);

auto addRange = [&](int l, int r, long long v) {
     diff[l] += v;
     diff[r + 1] -= v;
};

for (int i = 1; i <= n; ++i) {
     diff[i] += diff[i - 1];
     a[i] += diff[i];
}

3.4.2 二维差分

vector<vector<long long>> d(n + 2, vector<long long>(m + 2, 0));

auto addRect = [&](int x1, int y1, int x2, int y2, long long v) {
     d[x1][y1] += v;
     d[x2 + 1][y1] -= v;
     d[x1][y2 + 1] -= v;
     d[x2 + 1][y2 + 1] += v;
};

for (int i = 1; i <= n; ++i) {
     for (int j = 1; j <= m; ++j) {
         d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
         a[i][j] += d[i][j];
     }
}

3.5 离散化

vector<long long> xs = raw;
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());

auto getId = [&](long long x) {
     return int(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1;
};

3.6 双指针与滑动窗口

3.6.1 最长满足约束的区间

适合“连续子数组”且窗口条件随左右端点单调变化。

int l = 0, ans = 0;
long long sum = 0;

for (int r = 0; r < n; ++r) {
     sum += a[r];
     while (l <= r && sum > limit) {
         sum -= a[l++];
     }
     ans = max(ans, r - l + 1);
}

3.6.2 有序数组去重式双指针

sort(a.begin(), a.end());
int j = 0;
for (int i = 0; i < n; ++i) {
     if (i == 0 || a[i] != a[i - 1]) {
         a[j++] = a[i];
     }
}
a.resize(j);

3.7 区间合并

vector<pair<int,int>> segs;
sort(segs.begin(), segs.end());

vector<pair<int,int>> merged;
for (auto [l, r] : segs) {
     if (merged.empty() || merged.back().second < l) {
         merged.push_back({l, r});
     } else {
         merged.back().second = max(merged.back().second, r);
     }
}

3.8 整数二分

3.8.1 找第一个满足条件的位置

条件形如 false, false, false, true, true。

int l = 0, r = n; // answer in [0, n]
while (l < r) {
      int mid = l + (r - l) / 2;
      if (check(mid)) r = mid;
      else l = mid + 1;
}
// l is first satisfying position

3.8.2 找最后一个满足条件的位置

条件形如 true, true, true, false, false。

int l = 0, r = n; // answer in [0, n]
while (l < r) {
      int mid = l + (r - l + 1) / 2;
      if (check(mid)) l = mid;
      else r = mid - 1;
}
// l is last satisfying position

3.9 二分答案

  1. 先确定答案区间。

  2. 写出只回答“能不能”的 check(mid)。

  3. 验证单调性，再决定找第一个还是最后一个。

long long l = 0, r = 1e18;
while (l < r) {
      long long mid = l + (r - l) / 2;
      if (check(mid)) r = mid;
      else l = mid + 1;
}
cout << l << '\n';

3.10 浮点二分

double l = 0, r = 1e9;
for (int it = 0; it < 100; ++it) {
      double mid = (l + r) / 2;
      if (check(mid)) r = mid;
      else l = mid;
}

cout << fixed << setprecision(10) << r << '\n';

第 4 章 排序、贪心与基础题型

4.1 排序与稳定性

  • sort：平均与最坏复杂度均为 O(n log n)，默认升序。

  • stable_sort：保持相等元素原有顺序，常用于“先按次关键字排，再按主关键字排”的场景。

  • 自定义比较必须满足严格弱序，否则排序行为不可靠。

4.2 贪心题常见证明角度

  • 交换论证：若存在非贪心选择，可交换成贪心且不变差。

  • 局部最优推进：每一步选择不会影响后续最优性。

  • 排序后选取：区间调度、最小代价合并、按截止时间安排。

4.3 区间调度：最多不相交区间

按右端点升序，每次选当前能接上的最早结束区间。

vector<pair<int,int>> segs; // [l, r]
sort(segs.begin(), segs.end(), [](auto a, auto b) {
      if (a.second != b.second) return a.second < b.second;
      return a.first < b.first;
});

int ans = 0;
int lastR = -INF;
for (auto [l, r] : segs) {
      if (l >= lastR) {
          ++ans;
          lastR = r;
      }
}

4.4 Huffman 式最小合并代价

priority_queue<long long, vector<long long>, greater<long long>> pq;
for (long long x : a) pq.push(x);

long long cost = 0;
while (pq.size() > 1) {
      long long x = pq.top(); pq.pop();

    long long y = pq.top(); pq.pop();
    cost += x + y;
    pq.push(x + y);
}

4.5 扫描线差分：最大重叠数

map<int, int> diff;
for (auto [l, r] : intervals) {
    diff[l] += 1;
    diff[r + 1] -= 1; // 闭区间 [l, r]
}

int cur = 0, ans = 0;
for (auto [x, d] : diff) {
    cur += d;
    ans = max(ans, cur);
}

4.6 逆序对计数：归并排序

long long mergeCount(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (l >= r) return 0;
    int m = (l + r) / 2;
    long long ans = mergeCount(a, l, m, tmp) + mergeCount(a, m + 1, r, tmp);

    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            ans += (m - i + 1);
        }
    }
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int p = l; p <= r; ++p) a[p] = tmp[p];
    return ans;
}

4.7 括号匹配

bool validParentheses(const string& s) {
    stack<char> st;
    auto match = [&](char l, char r) {
        return (l == '(' && r == ')') ||
                  (l == '[' && r == ']') ||

                  (l == '{' && r == '}');
    };

    for (char c : s) {
         if (c == '(' || c == '[' || c == '{') st.push(c);
         else {
             if (st.empty() || !match(st.top(), c)) return false;
             st.pop();
         }
    }
    return st.empty();
}

第 5 章 数据结构

5.1 单调栈

5.1.1 每个位置左侧第一个严格更小值

vector<int> leftLess(n, -1);
stack<int> st; // store indices

for (int i = 0; i < n; ++i) {
    while (!st.empty() && a[st.top()] >= a[i]) st.pop();
    if (!st.empty()) leftLess[i] = st.top();
    st.push(i);
}

5.1.2 柱状图最大矩形

long long largestRectangle(vector<int> h) {
    h.push_back(0);
    stack<int> st;
    long long ans = 0;

    for (int i = 0; i < (int)h.size(); ++i) {
        while (!st.empty() && h[st.top()] > h[i]) {
            int height = h[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            long long width = i - left - 1;
            ans = max(ans, 1LL * height * width);
        }
        st.push(i);
    }
    return ans;
}

5.2 单调队列

5.2.1 滑动窗口最大值

deque<int> q;
for (int i = 0; i < n; ++i) {
    while (!q.empty() && q.front() <= i - k) q.pop_front();
    while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
    q.push_back(i);

      if (i >= k - 1) {
          cout << a[q.front()] << ' ';
      }
}

5.3 并查集 DSU

struct DSU {
      vector<int> p, sz;

      DSU(int n = 0) { init(n); }

      void init(int n) {
          p.resize(n + 1);
          sz.assign(n + 1, 1);
          iota(p.begin(), p.end(), 0);
      }

      int find(int x) {
          return p[x] == x ? x : p[x] = find(p[x]);
      }

      bool unite(int a, int b) {
          a = find(a);
          b = find(b);
          if (a == b) return false;
          if (sz[a] < sz[b]) swap(a, b);
          p[b] = a;
          sz[a] += sz[b];
          return true;
      }

      bool same(int a, int b) {
          return find(a) == find(b);
      }

      int size(int x) {
          return sz[find(x)];
      }
};

5.4 带权并查集

设 d[x] 表示“x 到父节点”的权值差。下面维护关系

weight[b] − weight[a] = w.

struct WeightedDSU {

     vector<int> p, sz;
     vector<long long> d; // d[x] = weight[x] - weight[parent[x]]

     WeightedDSU(int n = 0) { init(n); }

     void init(int n) {
         p.resize(n + 1);
         sz.assign(n + 1, 1);
         d.assign(n + 1, 0);
         iota(p.begin(), p.end(), 0);
     }

     int find(int x) {
         if (p[x] == x) return x;
         int fa = p[x];
         int rt = find(fa);
         d[x] += d[fa];
         return p[x] = rt;
     }

     bool unite(int a, int b, long long w) {
         int ra = find(a);
         long long da = d[a];
         int rb = find(b);
         long long db = d[b];

         if (ra == rb) {
              return db - da == w;
         }

         if (sz[ra] < sz[rb]) {
              p[ra] = rb;
              d[ra] = db - da - w;
              sz[rb] += sz[ra];
         } else {
              p[rb] = ra;
              d[rb] = da + w - db;
              sz[ra] += sz[rb];
         }
         return true;
     }
};

5.5 树状数组 Fenwick

5.5.1 单点加，前缀和与区间和

template<class T>
struct Fenwick {
     int n;

     vector<T> tr;

     Fenwick(int n = 0) { init(n); }

     void init(int n_) {
         n = n_;
         tr.assign(n + 1, 0);
     }

     void add(int x, T v) {
         for (; x <= n; x += x & -x) tr[x] += v;
     }

     T sumPrefix(int x) const {
         T res = 0;
         for (; x > 0; x -= x & -x) res += tr[x];
         return res;
     }

     T rangeSum(int l, int r) const {
         if (l > r) return 0;
         return sumPrefix(r) - sumPrefix(l - 1);
     }
};

5.5.2 区间加，区间和

template<class T>
struct RangeFenwick {
     int n;
     Fenwick<T> b1, b2;

     RangeFenwick(int n = 0) { init(n); }

     void init(int n_) {
         n = n_;
         b1.init(n);
         b2.init(n);
     }

     void rangeAdd(int l, int r, T v) {
         b1.add(l, v);
         b1.add(r + 1, -v);
         b2.add(l, v * (l - 1));
         b2.add(r + 1, -v * r);
     }

     T prefixSum(int x) const {
         return b1.sumPrefix(x) * x - b2.sumPrefix(x);
     }

     T rangeSum(int l, int r) const {
          return prefixSum(r) - prefixSum(l - 1);
     }
};

5.5.3 树状数组上二分：找第 k 个 1

int kth(long long k) { // smallest pos with prefix sum >= k
     int x = 0;
     for (int bit = 1 << __lg(n); bit; bit >>= 1) {
          int nx = x + bit;
          if (nx <= n && tr[nx] < k) {
              x = nx;
              k -= tr[nx];
          }
     }
     return x + 1;
}

5.6 线段树

5.6.1 区间加，区间和

struct SegTree {
     struct Node {
          long long sum = 0;
          long long lazy = 0;
     };

     int n;
     vector<Node> tr;

     SegTree(int n = 0) { init(n); }

     void init(int n_) {
          n = n_;
          tr.assign(4 * n + 4, {});
     }

     void pull(int p) {
          tr[p].sum = tr[p * 2].sum + tr[p * 2 + 1].sum;
     }

     void apply(int p, int l, int r, long long v) {
          tr[p].sum += v * (r - l + 1);
          tr[p].lazy += v;
     }

     void push(int p, int l, int r) {

         if (tr[p].lazy == 0 || l == r) return;
         int m = (l + r) / 2;
         long long v = tr[p].lazy;
         apply(p * 2, l, m, v);
         apply(p * 2 + 1, m + 1, r, v);
         tr[p].lazy = 0;
     }

     void build(int p, int l, int r, const vector<long long>& a) {
         if (l == r) {
             tr[p].sum = a[l];
             return;
         }
         int m = (l + r) / 2;
         build(p * 2, l, m, a);
         build(p * 2 + 1, m + 1, r, a);
         pull(p);
     }

     void rangeAdd(int p, int l, int r, int ql, int qr, long long v) {
         if (ql <= l && r <= qr) {
             apply(p, l, r, v);
             return;
         }
         push(p, l, r);
         int m = (l + r) / 2;
         if (ql <= m) rangeAdd(p * 2, l, m, ql, qr, v);
         if (qr > m) rangeAdd(p * 2 + 1, m + 1, r, ql, qr, v);
         pull(p);
     }

     long long query(int p, int l, int r, int ql, int qr) {
         if (ql <= l && r <= qr) {
             return tr[p].sum;
         }
         push(p, l, r);
         int m = (l + r) / 2;
         long long ans = 0;
         if (ql <= m) ans += query(p * 2, l, m, ql, qr);
         if (qr > m) ans += query(p * 2 + 1, m + 1, r, ql, qr);
         return ans;
     }
};

5.6.2 线段树使用提示

  • 只要是可合并信息，都能上树，但先判断树状数组是否已足够。

  • push 负责把懒标记下传，pull 负责由子节点合并当前节点。

  • 查询与修改的边界条件必须同一种闭区间约定。

5.7 Sparse Table

5.7.1 静态区间最小值

struct SparseTable {
     int n, K;
     vector<int> lg;
     vector<vector<int>> st;

     void build(const vector<int>& a) {
         n = (int)a.size();
         K = __lg(n) + 1;

         lg.assign(n + 1, 0);
         for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;

         st.assign(K, vector<int>(n));
         st[0] = a;

         for (int k = 1; k < K; ++k) {
               for (int i = 0; i + (1 << k) <= n; ++i) {
                   st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
               }
         }
     }

     int queryMin(int l, int r) {
         int k = lg[r - l + 1];
         return min(st[k][l], st[k][r - (1 << k) + 1]);
     }
};

5.8 优先队列、set 与 multiset

5.8.1 最小堆

priority_queue<int, vector<int>, greater<int>> pq;
pq.push(5);
pq.push(2);
cout << pq.top() << '\n'; // 2

5.8.2 set 常用操作

set<int> s;
s.insert(5);
s.insert(2);
s.erase(5);

auto it = s.lower_bound(3); // first >= 3

if (it != s.end()) cout << *it << '\n';

5.8.3 multiset 删除一个元素

multiset<int> ms;
ms.insert(4);
ms.insert(4);

auto it = ms.find(4);
if (it != ms.end()) ms.erase(it); // only erase one 4

第 6 章 图论

6.1 建图模板

6.1.1 无权图

int n, m;
vector<vector<int>> g(n + 1);

for (int i = 0; i < m; ++i) {
     int u, v;
     cin >> u >> v;
     g[u].push_back(v);
     g[v].push_back(u); // directed graph: remove this line
}

6.1.2 带权图

struct Edge {
     int to;
     long long w;
};

vector<vector<Edge>> g(n + 1);

for (int i = 0; i < m; ++i) {
     int u, v;
     long long w;
     cin >> u >> v >> w;
     g[u].push_back({v, w});
     g[v].push_back({u, w}); // directed graph: remove this line
}

6.2 BFS 与网格最短路

6.2.1 无权图最短路

vector<int> dist(n + 1, -1);
queue<int> q;

dist[s] = 0;
q.push(s);

while (!q.empty()) {

     int u = q.front();
     q.pop();

     for (int v : g[u]) {
         if (dist[v] != -1) continue;
         dist[v] = dist[u] + 1;
         q.push(v);
     }
}

6.2.2 网格 BFS

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int,int>> q;

dist[sx][sy] = 0;
q.push({sx, sy});

while (!q.empty()) {
     auto [x, y] = q.front();
     q.pop();

     for (int k = 0; k < 4; ++k) {
         int nx = x + dx[k];
         int ny = y + dy[k];
         if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
         if (grid[nx][ny] == '#') continue;
         if (dist[nx][ny] != -1) continue;

         dist[nx][ny] = dist[x][y] + 1;
         q.push({nx, ny});
     }
}

6.3 0-1 BFS

边权只可能为 0 或 1 时使用双端队列。

const long long INFLL = (1LL << 62);
vector<long long> dist(n + 1, INFLL);
deque<int> dq;

dist[s] = 0;
dq.push_back(s);

while (!dq.empty()) {
     int u = dq.front();

    dq.pop_front();

    for (auto [v, w] : g[u]) { // w is 0 or 1
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            if (w == 0) dq.push_front(v);
            else dq.push_back(v);
        }
    }
}

6.4 DFS、连通块与树遍历

6.4.1 连通块

vector<int> vis(n + 1, 0);

void dfs(int u) {
    vis[u] = 1;
    for (int v : g[u]) {
        if (!vis[v]) dfs(v);
    }
}

int comps = 0;
for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {
        ++comps;
        dfs(i);
    }
}

6.4.2 树上 DFS

vector<int> parent(n + 1), depth(n + 1);
vector<long long> distRoot(n + 1, 0);

void dfsTree(int u, int p) {
    parent[u] = p;
    for (auto [v, w] : tree[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        distRoot[v] = distRoot[u] + w;
        dfsTree(v, u);
    }
}

6.5 拓扑排序

vector<int> indeg(n + 1, 0);
vector<vector<int>> g(n + 1);

// add edge u -> v
// g[u].push_back(v);
// ++indeg[v];

queue<int> q;
for (int i = 1; i <= n; ++i) {
    if (indeg[i] == 0) q.push(i);
}

vector<int> topo;
while (!q.empty()) {
    int u = q.front();
    q.pop();
    topo.push_back(u);

    for (int v : g[u]) {
        if (--indeg[v] == 0) q.push(v);
    }
}

bool hasCycle = ((int)topo.size() != n);

6.6 Dijkstra

vector<long long> dijkstra(int s, const vector<vector<Edge>>& g) {
    int n = (int)g.size() - 1;
    vector<long long> dist(n + 1, INFLL);
    priority_queue<pair<long long,int>,
                      vector<pair<long long,int>>,
                      greater<pair<long long,int>>> pq;

    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [du, u] = pq.top();
        pq.pop();
        if (du != dist[u]) continue;

        for (auto e : g[u]) {
               int v = e.to;
               long long nd = du + e.w;
               if (nd < dist[v]) {
                   dist[v] = nd;
                   pq.push({nd, v});

             }
         }
     }
     return dist;
}

6.7 Floyd

vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INFLL));
for (int i = 1; i <= n; ++i) d[i][i] = 0;

// d[u][v] = min(d[u][v], w);

for (int k = 1; k <= n; ++k) {
     for (int i = 1; i <= n; ++i) {
         if (d[i][k] == INFLL) continue;
         for (int j = 1; j <= n; ++j) {
             if (d[k][j] == INFLL) continue;
             d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
         }
     }
}

6.8 Bellman-Ford 与负环

struct E {
     int u, v;
     long long w;
};
vector<E> edges;

vector<long long> dist(n + 1, 0); // detect any negative cycle
bool negCycle = false;

for (int i = 1; i <= n; ++i) {
     bool changed = false;
     for (auto e : edges) {
         if (dist[e.v] > dist[e.u] + e.w) {
             dist[e.v] = dist[e.u] + e.w;
             changed = true;
             if (i == n) negCycle = true;
         }
     }
     if (!changed) break;
}

6.9 SPFA 判负环

bool hasNegativeCycleSPFA(int n, const vector<vector<Edge>>& g) {
     vector<long long> dist(n + 1, 0);
     vector<int> cnt(n + 1, 0), inq(n + 1, 1);
     queue<int> q;

     for (int i = 1; i <= n; ++i) q.push(i);

     while (!q.empty()) {
         int u = q.front();
         q.pop();
         inq[u] = 0;

         for (auto e : g[u]) {
              int v = e.to;
              if (dist[v] > dist[u] + e.w) {
                    dist[v] = dist[u] + e.w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) return true;
                    if (!inq[v]) {
                        inq[v] = 1;
                        q.push(v);
                    }
              }
         }
     }
     return false;
}

SPFA 的位置
SPFA 常写、能用，但复杂度不稳定。能用 Dijkstra 时不要换 SPFA，评测机不会因为你怀旧就手下留情。

6.10 最小生成树

6.10.1 Kruskal

struct MstEdge {
     int u, v;
     long long w;
     bool operator<(const MstEdge& other) const {
         return w < other.w;
     }
};

sort(edges.begin(), edges.end());
DSU dsu(n);

long long cost = 0;

int used = 0;
for (auto e : edges) {
    if (dsu.unite(e.u, e.v)) {
        cost += e.w;
        ++used;
    }
}
bool connected = (used == n - 1);

6.10.2 Prim

long long prim(int s, const vector<vector<Edge>>& g) {
    int n = (int)g.size() - 1;
    vector<int> vis(n + 1, 0);
    priority_queue<pair<long long,int>,
                      vector<pair<long long,int>>,
                      greater<pair<long long,int>>> pq;

    pq.push({0, s});
    long long cost = 0;
    int cnt = 0;

    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        cost += w;
        ++cnt;

        for (auto e : g[u]) {
            if (!vis[e.to]) pq.push({e.w, e.to});
        }
    }
    if (cnt != n) return -1; // not connected
    return cost;
}

6.11 二分图判定

vector<int> color(n + 1, -1);
bool ok = true;

for (int s = 1; s <= n; ++s) {
    if (color[s] != -1) continue;

    queue<int> q;
    color[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : g[u]) {
            if (color[v] == -1) {
                   color[v] = color[u] ^ 1;
                   q.push(v);
            } else if (color[v] == color[u]) {
                   ok = false;
            }
        }
    }
}

6.12 二分图最大匹配 Kuhn

int nLeft, nRight;
vector<vector<int>> g(nLeft + 1);
vector<int> matchR(nRight + 1, 0), vis;

bool aug(int u) {
    for (int v : g[u]) {
        if (vis[v]) continue;
        vis[v] = 1;
        if (matchR[v] == 0 || aug(matchR[v])) {
            matchR[v] = u;
            return true;
        }
    }
    return false;
}

int maxMatch = 0;
for (int u = 1; u <= nLeft; ++u) {
    vis.assign(nRight + 1, 0);
    if (aug(u)) ++maxMatch;
}

6.13 LCA 倍增

const int LOG = 21; // enough for n <= 2e6 use larger as needed
vector<vector<int>> up(LOG, vector<int>(n + 1));
vector<int> depth(n + 1);
vector<vector<int>> tree(n + 1);

void dfsLca(int u, int p) {
    up[0][u] = p;

    for (int k = 1; k < LOG; ++k) {
        up[k][u] = up[k - 1][up[k - 1][u]];
    }

    for (int v : tree[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfsLca(v, u);
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    int diff = depth[a] - depth[b];
    for (int k = 0; k < LOG; ++k) {
        if (diff >> k & 1) a = up[k][a];
    }

    if (a == b) return a;

    for (int k = LOG - 1; k >= 0; --k) {
        if (up[k][a] != up[k][b]) {
            a = up[k][a];
            b = up[k][b];
        }
    }
    return up[0][a];
}

6.13.1 树上距离

int distTree(int a, int b) {
    int c = lca(a, b);
    return depth[a] + depth[b] - 2 * depth[c];
}

6.14 树的直径

6.14.1 两次 BFS / DFS

  1. 任取一点 s，找到离它最远点 u。

  2. 再从 u 出发，最远点 v，距离即直径长度。

pair<int, long long> farthest(int s) {
    vector<long long> dist(n + 1, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto [v, w] : tree[u]) {
            if (dist[v] != -1) continue;
            dist[v] = dist[u] + w;
            q.push(v);
        }
    }

    int id = s;
    for (int i = 1; i <= n; ++i) {
        if (dist[i] > dist[id]) id = i;
    }
    return {id, dist[id]};
}

6.15 Tarjan 强连通分量

int timer = 0, sccCnt = 0;
vector<int> dfn(n + 1, 0), low(n + 1, 0), inSt(n + 1, 0), comp(n + 1, 0);
stack<int> st;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    inSt[u] = 1;

    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inSt[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) {
        ++sccCnt;
        while (true) {
            int x = st.top();
            st.pop();
            inSt[x] = 0;
            comp[x] = sccCnt;
            if (x == u) break;
        }
    }
}

6.16 Dinic 最大流

struct Dinic {
    struct Edge {
         int to, rev;
         long long cap;
    };

    int n;
    vector<vector<Edge>> g;
    vector<int> level, it;

    Dinic(int n = 0) { init(n); }

    void init(int n_) {
         n = n_;
         g.assign(n + 1, {});
    }

    void addEdge(int u, int v, long long c) {
         Edge a{v, (int)g[v].size(), c};
         Edge b{u, (int)g[u].size(), 0};
         g[u].push_back(a);
         g[v].push_back(b);
    }

    bool bfs(int s, int t) {
         level.assign(n + 1, -1);
         queue<int> q;
         level[s] = 0;
         q.push(s);

         while (!q.empty()) {
             int u = q.front();
             q.pop();
             for (auto &e : g[u]) {
                   if (e.cap > 0 && level[e.to] == -1) {
                        level[e.to] = level[u] + 1;
                        q.push(e.to);
                   }
             }
         }
         return level[t] != -1;
    }

    long long dfs(int u, int t, long long f) {
         if (u == t) return f;
         for (int &i = it[u]; i < (int)g[u].size(); ++i) {
             Edge &e = g[u][i];
             if (e.cap <= 0 || level[e.to] != level[u] + 1) continue;
             long long ret = dfs(e.to, t, min(f, e.cap));
             if (ret > 0) {

                    e.cap -= ret;
                    g[e.to][e.rev].cap += ret;
                    return ret;
               }
          }
          return 0;
      }

      long long maxFlow(int s, int t) {
          long long flow = 0, pushed;
          while (bfs(s, t)) {
               it.assign(n + 1, 0);
               while ((pushed = dfs(s, t, INFLL)) > 0) {
                    flow += pushed;
               }
          }
          return flow;
      }
};

6.17 2-SAT 基本模板

每个变量 xi 有两个点：2i 表示假，2i+1 表示真。子句 (a ∨ b) 转成蕴含 (¬a ⇒ b) 与 (¬b ⇒ a)。

struct TwoSAT {
      int n;
      vector<vector<int>> g, rg;
      vector<int> comp, order, vis, assignment;

      TwoSAT(int n = 0) { init(n); }

      void init(int n_) {
          n = n_;
          g.assign(2 * n, {});
          rg.assign(2 * n, {});
      }

      int id(int x, bool val) {
          return 2 * x + (val ? 1 : 0);
      }

      void addImp(int a, int b) {
          g[a].push_back(b);
          rg[b].push_back(a);
      }

      void addOr(int x, bool xv, int y, bool yv) {
          int a = id(x, xv);
          int b = id(y, yv);
          addImp(a ^ 1, b);
          addImp(b ^ 1, a);

     }

     void dfs1(int u) {
         vis[u] = 1;
         for (int v : g[u]) if (!vis[v]) dfs1(v);
         order.push_back(u);
     }

     void dfs2(int u, int c) {
         comp[u] = c;
         for (int v : rg[u]) if (comp[v] == -1) dfs2(v, c);
     }

     bool solve() {
         vis.assign(2 * n, 0);
         order.clear();
         for (int i = 0; i < 2 * n; ++i) {
             if (!vis[i]) dfs1(i);
         }

         comp.assign(2 * n, -1);
         int cid = 0;
         reverse(order.begin(), order.end());
         for (int u : order) {
             if (comp[u] == -1) dfs2(u, cid++);
         }

         assignment.assign(n, 0);
         for (int i = 0; i < n; ++i) {
             if (comp[2 * i] == comp[2 * i + 1]) return false;
             assignment[i] = comp[2 * i] < comp[2 * i + 1];
         }
         return true;
     }
};

第 7 章 动态规划

7.1 DP 的基本四问

  1. 状态：dp[i] 或 dp[i][j] 表示什么。

  2. 转移：最后一步从哪里来。

  3. 初始化：空状态、边界状态、不可达状态。

  4. 枚举顺序：正序、倒序、按区间长度、按拓扑序。

DP 的老毛病
“感觉差不多”不是状态定义。状态一旦含糊，转移就会像泥里开车，最后每个样例都像在嘲笑你。

7.2 背包

7.2.1 0/1 背包

每件物品最多选一次，容量循环倒序。

vector<long long> dp(V + 1, 0);
for (int i = 1; i <= n; ++i) {
    for (int j = V; j >= w[i]; --j) {
        dp[j] = max(dp[j], dp[j - w[i]] + val[i]);
    }
}

7.2.2 完全背包

每件物品可选无限次，容量循环正序。

vector<long long> dp(V + 1, 0);
for (int i = 1; i <= n; ++i) {
    for (int j = w[i]; j <= V; ++j) {
        dp[j] = max(dp[j], dp[j - w[i]] + val[i]);
    }
}

7.2.3 多重背包二进制拆分

vector<pair<int,int>> items;
for (int i = 1; i <= n; ++i) {
    int c = cnt[i];
    for (int k = 1; c > 0; k <<= 1) {
        int take = min(k, c);

         items.push_back({w[i] * take, val[i] * take});
         c -= take;
     }
}

vector<long long> dp(V + 1, 0);
for (auto [ww, vv] : items) {
     for (int j = V; j >= ww; --j) {
         dp[j] = max(dp[j], dp[j - ww] + vv);
     }
}

7.2.4 分组背包

每组最多选一件。

vector<long long> dp(V + 1, 0);
for (auto &group : groups) {
     vector<long long> old = dp;
     for (auto [ww, vv] : group) {
         for (int j = ww; j <= V; ++j) {
             dp[j] = max(dp[j], old[j - ww] + vv);
         }
     }
}

7.3 最长上升子序列 LIS

7.3.1 O(n log n) 严格上升

vector<int> tail;
for (int x : a) {
     auto it = lower_bound(tail.begin(), tail.end(), x);
     if (it == tail.end()) tail.push_back(x);
     else *it = x;
}
int lis = (int)tail.size();

7.3.2 非严格上升

把 lower_bound 换成 upper_bound。

7.4 LCS 与最长公共子串

7.4.1 最长公共子序列 LCS

int n = s.size(), m = t.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
}

7.4.2 最长公共子串

int ans = 0;
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (s[i - 1] == t[j - 1]) {
               dp[i][j] = dp[i - 1][j - 1] + 1;
               ans = max(ans, dp[i][j]);
        }
    }
}

7.5 区间 DP

典型顺序是按区间长度从小到大。

for (int len = 2; len <= n; ++len) {
    for (int l = 1; l + len - 1 <= n; ++l) {
        int r = l + len - 1;
        dp[l][r] = INFLL;
        for (int k = l; k < r; ++k) {
               dp[l][r] = min(dp[l][r],
                              dp[l][k] + dp[k + 1][r] + cost(l, r));
        }
    }
}

7.6 树形 DP

7.6.1 树上最大独立集骨架

vector<vector<int>> tree(n + 1);
vector<array<long long, 2>> dp(n + 1);

void dfs(int u, int p) {
    dp[u][0] = 0;
    dp[u][1] = weight[u];

     for (int v : tree[u]) {
         if (v == p) continue;
         dfs(v, u);
         dp[u][0] += max(dp[v][0], dp[v][1]);
         dp[u][1] += dp[v][0];
     }
}

7.6.2 换根 DP 思路

常见套路：

  1. 第一次 DFS 求子树贡献。

  2. 第二次 DFS 把父亲方向的贡献传给儿子。

  3. 每次转移前先“删掉儿子贡献”，算儿子答案，再恢复。

7.7 状态压缩 DP

7.7.1 旅行商 TSP 形式

const long long INF = (1LL << 62);
int FULL = 1 << n;
vector<vector<long long>> dp(FULL, vector<long long>(n, INF));
dp[1][0] = 0;

for (int mask = 0; mask < FULL; ++mask) {
     for (int u = 0; u < n; ++u) {
         if (dp[mask][u] == INF) continue;
         for (int v = 0; v < n; ++v) {
             if (mask >> v & 1) continue;
             int nmask = mask | (1 << v);
             dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + w[u][v]);
         }
     }
}

7.8 数位 DP

7.8.1 记忆化搜索骨架

统计 0 ∼ X 中满足条件的数，常写成 solve(X)。

string s;
long long memo[20][2];
bool vis[20][2];

long long dfs(int pos, bool tight, bool started) {
     if (pos == (int)s.size()) {
         return started ? 1 : 0;

     }

     if (!tight && vis[pos][started]) return memo[pos][started];

     int up = tight ? s[pos] - '0' : 9;
     long long ans = 0;

     for (int d = 0; d <= up; ++d) {
         bool ntight = tight && (d == up);
         bool nstarted = started || (d != 0);

         // 在这里加入“是否满足限制”的判断
         ans += dfs(pos + 1, ntight, nstarted);
     }

     if (!tight) {
         vis[pos][started] = true;
         memo[pos][started] = ans;
     }
     return ans;
}

long long solve(long long x) {
     if (x < 0) return 0;
     s = to_string(x);
     memset(vis, 0, sizeof(vis));
     return dfs(0, true, false);
}

7.9 DAG 上 DP

若图无环，拓扑序就是天然 DP 顺序。

vector<long long> dp(n + 1, -INFLL);
dp[s] = 0;

for (int u : topo) {
     if (dp[u] == -INFLL) continue;
     for (auto [v, w] : g[u]) {
         dp[v] = max(dp[v], dp[u] + w);
     }
}

7.10 最短路计数

若边权非负，用 Dijkstra 同时维护最短路条数。

const int MOD = 1000000007;
vector<long long> dist(n + 1, INFLL);
vector<int> ways(n + 1, 0);

priority_queue<pair<long long,int>,
                  vector<pair<long long,int>>,
                  greater<pair<long long,int>>> pq;

dist[s] = 0;
ways[s] = 1;
pq.push({0, s});

while (!pq.empty()) {
    auto [du, u] = pq.top();
    pq.pop();
    if (du != dist[u]) continue;

    for (auto e : g[u]) {
        int v = e.to;
        long long nd = du + e.w;
        if (nd < dist[v]) {
               dist[v] = nd;
               ways[v] = ways[u];
               pq.push({nd, v});
        } else if (nd == dist[v]) {
               ways[v] += ways[u];
               if (ways[v] >= MOD) ways[v] -= MOD;
        }
    }
}

第 8 章 字符串

8.1 KMP 前缀函数

8.1.1 计算 prefix function

vector<int> prefixFunction(const string& s) {
    int n = (int)s.size();
    vector<int> pi(n, 0);

    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

8.1.2 模式串匹配

vector<int> kmpMatch(const string& text, const string& pat) {
    string s = pat + "#" + text;
    vector<int> pi = prefixFunction(s);
    vector<int> pos;

    int m = (int)pat.size();
    for (int i = m + 1; i < (int)s.size(); ++i) {
        if (pi[i] == m) {
            pos.push_back(i - 2 * m);
        }
    }
    return pos;
}

8.2 Z 函数

vector<int> zFunction(const string& s) {
    int n = (int)s.size();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) {

               l = i;
               r = i + z[i] - 1;
         }
    }
    z[0] = n;
    return z;
}

8.3 Trie 字典树

适用于小写字母字符串集合。

struct Trie {
    struct Node {
         int nxt[26];
         int cnt = 0;
         bool end = false;
         Node() {
               memset(nxt, -1, sizeof(nxt));
         }
    };

    vector<Node> tr;

    Trie() {
         tr.push_back(Node());
    }

    void insert(const string& s) {
         int u = 0;
         for (char c : s) {
               int x = c - 'a';
               if (tr[u].nxt[x] == -1) {
                    tr[u].nxt[x] = (int)tr.size();
                    tr.push_back(Node());
               }
               u = tr[u].nxt[x];
               tr[u].cnt++;
         }
         tr[u].end = true;
    }

    bool find(const string& s) {
         int u = 0;
         for (char c : s) {
               int x = c - 'a';
               if (tr[u].nxt[x] == -1) return false;
               u = tr[u].nxt[x];
         }
         return tr[u].end;
    }

};

8.4 字符串哈希

8.4.1 单哈希骨架

struct RollingHash {
     static const long long MOD = 1000000007;
     static const long long BASE = 911382323;

     vector<long long> h, p;

     RollingHash(const string& s = "") {
         build(s);
     }

     void build(const string& s) {
         int n = (int)s.size();
         h.assign(n + 1, 0);
         p.assign(n + 1, 1);
         for (int i = 1; i <= n; ++i) {
             h[i] = (h[i - 1] * BASE + s[i - 1]) % MOD;
             p[i] = p[i - 1] * BASE % MOD;
         }
     }

     long long get(int l, int r) { // 0-indexed inclusive
         long long res = (h[r + 1] - h[l] * p[r - l + 1]) % MOD;
         if (res < 0) res += MOD;
         return res;
     }
};

哈希提醒
单哈希有碰撞风险。高要求题可用双模数或 64 位自然溢出哈希。题解里一句“概率很低”不是数学证明，
但比赛里常够用。

8.5 Manacher 最长回文子串

下面模板返回原串中最长回文长度。

int manacherLongest(const string& s) {
     string t = "^";
     for (char c : s) {
         t += "#";
         t += c;
     }
     t += "#$";

    int n = (int)t.size();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    int best = 0;

    for (int i = 1; i + 1 < n; ++i) {
         int mirror = 2 * center - i;
         if (i < right) p[i] = min(right - i, p[mirror]);

         while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) ++p[i];

         if (i + p[i] > right) {
             center = i;
             right = i + p[i];
         }
         best = max(best, p[i]);
    }
    return best;
}

8.6 AC 自动机

struct ACAutomaton {
    struct Node {
         int nxt[26];
         int fail = 0;
         int out = 0;
         Node() {
             memset(nxt, 0, sizeof(nxt));
         }
    };

    vector<Node> tr;

    ACAutomaton() {
         tr.push_back(Node());
    }

    void insert(const string& s) {
         int u = 0;
         for (char c : s) {
             int x = c - 'a';
             if (!tr[u].nxt[x]) {
                    tr[u].nxt[x] = (int)tr.size();
                    tr.push_back(Node());
             }
             u = tr[u].nxt[x];
         }
         tr[u].out++;
    }

     void build() {
         queue<int> q;
         for (int c = 0; c < 26; ++c) {
             int v = tr[0].nxt[c];
             if (v) q.push(v);
         }

         while (!q.empty()) {
             int u = q.front();
             q.pop();

             tr[u].out += tr[tr[u].fail].out;

             for (int c = 0; c < 26; ++c) {
                 int v = tr[u].nxt[c];
                 if (v) {
                        tr[v].fail = tr[tr[u].fail].nxt[c];
                        q.push(v);
                 } else {
                        tr[u].nxt[c] = tr[tr[u].fail].nxt[c];
                 }
             }
         }
     }

     long long query(const string& s) {
         int u = 0;
         long long ans = 0;
         for (char c : s) {
             int x = c - 'a';
             u = tr[u].nxt[x];
             ans += tr[u].out;
         }
         return ans;
     }
};

8.7 后缀数组用途速记

  • 排序所有后缀，支持最长公共前缀、不同子串计数、字典序相关问题。

  • 现场赛若未熟练，不建议临场硬写。需要时可优先考虑哈希、二分、KMP 或 Z 函数是否足够。

第 9 章 数学与数论

9.1 gcd 与 lcm

long long gcdll(long long a, long long b) {
    return b == 0 ? llabs(a) : gcdll(b, a % b);
}

long long lcmll(long long a, long long b) {
    return a / gcdll(a, b) * b;
}

9.2 快速幂

long long qpow(long long a, long long e, long long mod) {
    long long r = 1 % mod;
    a %= mod;
    while (e > 0) {
        if (e & 1) r = (__int128)r * a % mod;
        a = (__int128)a * a % mod;
        e >>= 1;
    }
    return r;
}

9.3 扩展欧几里得与逆元

9.3.1 exgcd

long long exgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

9.3.2 一般模逆

当且仅当 gcd(a, m) = 1 时存在逆元。

long long invGeneral(long long a, long long mod) {
     long long x, y;
     long long g = exgcd(a, mod, x, y);
     if (g != 1) return -1;
     x %= mod;
     if (x < 0) x += mod;
     return x;
}

9.3.3 质数模逆

若 MOD 为质数且 a ≠ 0 (mod MOD)，则：

a − 1 ≡ a M O D − 2 ( m o d M O D ) a^{-1} \equiv a^{MOD-2} \pmod{MOD} a−1≡aMOD−2(modMOD)

9.4 线性筛

vector<int> primes;
vector<int> isComp(n + 1, 0);

for (int i = 2; i <= n; ++i) {
     if (!isComp[i]) primes.push_back(i);
     for (int p : primes) {
         if (1LL * i * p > n) break;
         isComp[i * p] = 1;
         if (i % p == 0) break;
     }
}

9.5 质因数分解

vector<pair<long long,int>> factorize(long long x) {
     vector<pair<long long,int>> fac;
     for (long long p = 2; p * p <= x; ++p) {
         if (x % p) continue;
         int cnt = 0;
         while (x % p == 0) {
             x /= p;
             ++cnt;
         }
         fac.push_back({p, cnt});
     }
     if (x > 1) fac.push_back({x, 1});
     return fac;
}

9.6 欧拉函数

9.6.1 单个数的 φ(n)

long long phi(long long n) {
     long long ans = n;
     for (long long p = 2; p * p <= n; ++p) {
         if (n % p) continue;
         while (n % p == 0) n /= p;
         ans = ans / p * (p - 1);
     }
     if (n > 1) ans = ans / n * (n - 1);
     return ans;
}

9.6.2 筛出 1 ∼ n 的 φ

vector<int> phi(n + 1);
for (int i = 0; i <= n; ++i) phi[i] = i;
for (int i = 2; i <= n; ++i) {
     if (phi[i] == i) {
         for (int j = i; j <= n; j += i) {
             phi[j] = phi[j] / i * (i - 1);
         }
     }
}

9.7 组合数预处理

适用于模数为质数且 n < MOD 的常见情形。

const long long MOD = 1000000007;
vector<long long> fact, invFact;

long long modPow(long long a, long long e) {
     long long r = 1;
     while (e) {
         if (e & 1) r = r * a % MOD;
         a = a * a % MOD;
         e >>= 1;
     }
     return r;
}

void initComb(int N) {
     fact.assign(N + 1, 1);
     invFact.assign(N + 1, 1);

     for (int i = 1; i <= N; ++i) {
         fact[i] = fact[i - 1] * i % MOD;

     }

     invFact[N] = modPow(fact[N], MOD - 2);
     for (int i = N; i >= 1; --i) {
         invFact[i - 1] = invFact[i] * i % MOD;
     }
}

long long C(int n, int k) {
     if (k < 0 || k > n) return 0;
     return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

9.8 Lucas 定理

适用于质数模 p，计算大 n, m 下的组合数模 p。

long long lucas(long long n, long long k, long long p) {
     if (k == 0) return 1;
     return C(n % p, k % p) * lucas(n / p, k / p, p) % p;
}

Lucas 注意

上面 C 需要按模 p 预处理，而不是沿用固定的 10^9 + 7 版本。

9.9 中国剩余定理 CRT

模数两两互质时：

x ≡ a i ( m o d m i ) x \equiv a_i \pmod{m_i} x≡ai​(modmi​)

long long crt(const vector<long long>& a, const vector<long long>& m) {
     long long M = 1;
     for (long long x : m) M *= x;

     long long ans = 0;
     int n = (int)a.size();

     for (int i = 0; i < n; ++i) {
         long long Mi = M / m[i];
         long long inv = invGeneral(Mi % m[i], m[i]);
         ans = (ans + (__int128)a[i] * Mi % M * inv) % M;
     }
     return (ans % M + M) % M;
}

9.10 矩阵快速幂

using Mat = vector<vector<long long>>;
const long long MODM = 1000000007;

Mat mul(const Mat& A, const Mat& B) {
    int n = (int)A.size();
    int m = (int)B[0].size();
    int p = (int)B.size();
    Mat C(n, vector<long long>(m, 0));

    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < p; ++k) {
            if (A[i][k] == 0) continue;
            for (int j = 0; j < m; ++j) {
                   C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MODM;
            }
        }
    }
    return C;
}

Mat mpow(Mat A, long long e) {
    int n = (int)A.size();
    Mat R(n, vector<long long>(n, 0));
    for (int i = 0; i < n; ++i) R[i][i] = 1;

    while (e) {
        if (e & 1) R = mul(R, A);
        A = mul(A, A);
        e >>= 1;
    }
    return R;
}

9.11 Miller-Rabin 64 位素性测试

using u128 = __uint128_t;
using ull = unsigned long long;

ull modMul(ull a, ull b, ull mod) {
    return (u128)a * b % mod;
}

ull modPow64(ull a, ull d, ull mod) {
    ull r = 1;
    while (d) {
        if (d & 1) r = modMul(r, a, mod);
        a = modMul(a, a, mod);
        d >>= 1;
    }
    return r;

}

bool isPrime64(ull n) {
    if (n < 2) return false;
    for (ull p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL,
         37ULL}) {
        if (n % p == 0) return n == p;
    }

    ull d = n - 1, s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        ++s;
    }

    for (ull a : {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL}) {
        if (a % n == 0) continue;
        ull x = modPow64(a, d, n);
        if (x == 1 || x == n - 1) continue;

        bool composite = true;
        for (ull r = 1; r < s; ++r) {
               x = modMul(x, x, n);
               if (x == n - 1) {
                   composite = false;
                   break;
               }
        }
        if (composite) return false;
    }
    return true;
}

9.12 高精度基础

9.12.1 高精度加法

string addBig(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string c;
    int carry = 0;
    int n = max(a.size(), b.size());

    for (int i = 0; i < n; ++i) {
        int x = i < (int)a.size() ? a[i] - '0' : 0;
        int y = i < (int)b.size() ? b[i] - '0' : 0;
        int s = x + y + carry;
        c.push_back(char('0' + s % 10));

        carry = s / 10;
    }
    if (carry) c.push_back(char('0' + carry));

    reverse(c.begin(), c.end());
    return c;
}

9.12.2 高精度乘小整数

string mulBigSmall(string a, int b) {
    reverse(a.begin(), a.end());
    string c;
    long long carry = 0;

    for (char ch : a) {
        long long cur = 1LL * (ch - '0') * b + carry;
        c.push_back(char('0' + cur % 10));
        carry = cur / 10;
    }
    while (carry) {
        c.push_back(char('0' + carry % 10));
        carry /= 10;
    }

    while (c.size() > 1 && c.back() == '0') c.pop_back();
    reverse(c.begin(), c.end());
    return c;
}

第 10 章 计算几何

10.1 基础约定

  • 若坐标是整数且范围不大，优先用 long long 计算叉积，避免浮点误差。

  • 若涉及距离、圆、角度，通常使用 double，并统一 EPS。

  • 几何题先画图。闭眼写几何，通常是在和错误答案培养感情。

10.2 点、向量、点积、叉积

const double EPS = 1e-9;

int sgn(double x) {
     if (fabs(x) < EPS) return 0;
     return x < 0 ? -1 : 1;
}

struct Point {
     double x, y;

     Point() {}
     Point(double x, double y): x(x), y(y) {}

     Point operator + (const Point& o) const { return {x + o.x, y + o.y}; }
     Point operator - (const Point& o) const { return {x - o.x, y - o.y}; }
     Point operator * (double k) const { return {x * k, y * k}; }

     bool operator < (const Point& o) const {
         if (sgn(x - o.x) != 0) return x < o.x;
         return y < o.y;
     }
};

double dot(Point a, Point b) {
     return a.x * b.x + a.y * b.y;
}

double cross(Point a, Point b) {
     return a.x * b.y - a.y * b.x;
}

double cross(Point a, Point b, Point c) {
     return cross(b - a, c - a);
}

double norm(Point a) {
    return sqrt(dot(a, a));
}

10.3 点在线段上

bool onSegment(Point p, Point a, Point b) {
    return sgn(cross(a, b, p)) == 0 &&
           sgn(dot(p - a, p - b)) <= 0;
}

10.4 线段相交

bool segmentIntersect(Point a, Point b, Point c, Point d) {
    double c1 = cross(a, b, c);
    double c2 = cross(a, b, d);
    double c3 = cross(c, d, a);
    double c4 = cross(c, d, b);

    if (sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0) return true;

    if (sgn(c1) == 0 && onSegment(c, a, b)) return true;
    if (sgn(c2) == 0 && onSegment(d, a, b)) return true;
    if (sgn(c3) == 0 && onSegment(a, c, d)) return true;
    if (sgn(c4) == 0 && onSegment(b, c, d)) return true;

    return false;
}

10.5 多边形面积

double polygonArea(const vector<Point>& p) {
    int n = (int)p.size();
    double s = 0;
    for (int i = 0; i < n; ++i) {
        s += cross(p[i], p[(i + 1) % n]);
    }
    return fabs(s) / 2.0;
}

10.6 凸包 Andrew

返回逆时针凸包。若需要保留共线点，可调整比较符号。

vector<Point> convexHull(vector<Point> p) {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end(), [](const Point& a, const Point& b) {
        return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
    }), p.end());

    int n = (int)p.size();
    if (n <= 1) return p;

    vector<Point> h;

    for (int i = 0; i < n; ++i) {
        while (h.size() >= 2 &&
                sgn(cross(h[h.size() - 2], h.back(), p[i])) <= 0) {
            h.pop_back();
        }
        h.push_back(p[i]);
    }

    int lowerSize = (int)h.size();
    for (int i = n - 2; i >= 0; --i) {
        while ((int)h.size() > lowerSize &&
                sgn(cross(h[h.size() - 2], h.back(), p[i])) <= 0) {
            h.pop_back();
        }
        h.push_back(p[i]);
    }

    h.pop_back();
    return h;
}

10.7 点到直线距离

double distancePointLine(Point p, Point a, Point b) {
    return fabs(cross(b - a, p - a)) / norm(b - a);
}

10.8 圆与线段的一点速查

  • 两点距离： ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} (x1​−x2​)2+(y1​−y2​)2 ​。

  • 圆面积： π r 2 \pi r^2 πr2，周长： 2 π r 2\pi r 2πr。

  • 圆心到直线距离小于半径时相交，大于半径时不交。

  • 若题目只要比较距离，尽量比较平方，避免无意义开根号。

第 11 章 搜索、构造、博弈与杂项

11.1 DFS 回溯骨架

vector<int> path;
vector<int> used(n + 1, 0);

void dfs(int step) {
    if (step == target) {
        // process one solution
        return;
    }

    for (int x = 1; x <= n; ++x) {
        if (used[x]) continue;
        used[x] = 1;
        path.push_back(x);

        dfs(step + 1);

        path.pop_back();
        used[x] = 0;
    }
}

11.2 BFS 状态搜索

queue<State> q;
unordered_map<State, int, HashState> dist;

dist[start] = 0;
q.push(start);

while (!q.empty()) {
    State cur = q.front();
    q.pop();

    for (State nxt : expand(cur)) {
        if (dist.count(nxt)) continue;
        dist[nxt] = dist[cur] + 1;
        q.push(nxt);
    }
}

11.3 A* 的谨慎说明

  • 启发函数 h(x) 必须不高估真实代价，才保证最优性。

  • 常见于八数码、网格最短路等搜索题。

  • 若不熟，普通 BFS、Dijkstra 往往更稳。赛场上算法不是越花越好，能 AC 的才有尊严。

11.4 位运算速查

操作 写法
取第 k 位 (mask >> k) & 1
把第 k 位设为 1 `mask
把第 k 位设为 0 mask & ~(1 << k)
翻转第 k 位 mask ^ (1 << k)
最低位 1 mask & -mask
删掉最低位 1 mask & (mask - 1)
判断子集 (a & b) == a

11.5 Nim 博弈

若若干堆石子每次任选一堆取若干个，则：

先手必胜 ⇐⇒ a1 ⊕ a2 ⊕ · · · ⊕ an ̸= 0.

int xorsum = 0;
for (int x : piles) xorsum ^= x;
bool firstWin = (xorsum != 0);

11.6 SG 函数骨架

int mex(const vector<int>& vals) {
    unordered_set<int> s(vals.begin(), vals.end());
    int g = 0;
    while (s.count(g)) ++g;
    return g;
}

vector<int> sg(MAXN + 1, -1);

int getSG(int x) {
    if (sg[x] != -1) return sg[x];
    vector<int> nextVals;
    for (int y : moves(x)) {
        nextVals.push_back(getSG(y));

    }
    return sg[x] = mex(nextVals);
}

11.7 常见构造题思路

  • 先构造小规模样例，观察规律。

  • 约束若是“相邻不同”“异或固定”
    “排列满足条件”，优先考虑分块、奇偶、对称。

  • 构造题答案经常不唯一。先拿到一个合法解，再考虑是否需要最优。

11.8 bitset 常用法

bitset<100000> bs;
bs.set(3);
bs[10] = 1;
bs.flip(3);
int cnt = bs.count();

bitset 的价值
位集常用于集合转移、可达性、布尔卷积式优化。能把 64 个布尔状态打包并行，属于让 CPU 干点正事。

第 12 章 常见题型速用模板

12.1 子数组和等于 k

前缀和 + 哈希表。

long long ans = 0, pre = 0;
unordered_map<long long, long long> cnt;
cnt[0] = 1;

for (long long x : a) {
     pre += x;
     ans += cnt[pre - k];
     cnt[pre]++;
}

12.2 最长不含重复字符的子串

vector<int> last(256, -1);
int ans = 0, l = 0;

for (int r = 0; r < (int)s.size(); ++r) {
     l = max(l, last[(unsigned char)s[r]] + 1);
     last[(unsigned char)s[r]] = r;
     ans = max(ans, r - l + 1);
}

12.3 拓扑 DP

vector<long long> dp(n + 1, -INFLL);
dp[s] = 0;

for (int u : topo) {
     if (dp[u] == -INFLL) continue;
     for (auto [v, w] : dag[u]) {
         dp[v] = max(dp[v], dp[u] + w);
     }
}

12.4 最近更小元素的贡献统计

若要统计以 a[i] 为最小值的子数组数量，常先求左边第一个严格更小与右边第一个小于等于它的位置。

vector<int> L(n), R(n);
stack<int> st;

for (int i = 0; i < n; ++i) {
    while (!st.empty() && a[st.top()] > a[i]) st.pop();
    L[i] = st.empty() ? -1 : st.top();
    st.push(i);
}
while (!st.empty()) st.pop();

for (int i = n - 1; i >= 0; --i) {
    while (!st.empty() && a[st.top()] >= a[i]) st.pop();
    R[i] = st.empty() ? n : st.top();
    st.push(i);
}

long long contribution = 0;
for (int i = 0; i < n; ++i) {
    contribution += 1LL * a[i] * (i - L[i]) * (R[i] - i);
}

12.5 Dijkstra 中记录前驱恢复路径

vector<int> pre(n + 1, -1);

while (!pq.empty()) {
    auto [du, u] = pq.top();
    pq.pop();
    if (du != dist[u]) continue;

    for (auto e : g[u]) {
        int v = e.to;
        long long nd = du + e.w;
        if (nd < dist[v]) {
            dist[v] = nd;
            pre[v] = u;
            pq.push({nd, v});
        }
    }
}

vector<int> path;
for (int cur = t; cur != -1; cur = pre[cur]) path.push_back(cur);
reverse(path.begin(), path.end());

12.6 二维网格连通块计数

int comps = 0;

vector<vector<int>> vis(n, vector<int>(m, 0));

function<void(int,int)> dfs = [&](int x, int y) {
      vis[x][y] = 1;
      for (int k = 0; k < 4; ++k) {
          int nx = x + dx[k], ny = y + dy[k];
          if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
          if (grid[nx][ny] == '#') continue;
          if (!vis[nx][ny]) dfs(nx, ny);
      }
};

for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
          if (grid[i][j] != '#' && !vis[i][j]) {
              ++comps;
              dfs(i, j);
          }
      }
}

12.7 固定窗口最小值

把单调队列里的比较方向反过来即可。

deque<int> q;
for (int i = 0; i < n; ++i) {
      while (!q.empty() && q.front() <= i - k) q.pop_front();
      while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
      q.push_back(i);

      if (i >= k - 1) cout << a[q.front()] << ' ';
}

12.8 离线查询排序技巧

例如按右端点排序，再用树状数组维护前缀信息。

struct Query {
      int l, r, id;
};
sort(qs.begin(), qs.end(), [](const Query& a, const Query& b) {
      return a.r < b.r;
});

12.9 并查集判无向图是否成环

bool hasCycle = false;

DSU dsu(n);

for (auto [u, v] : edges) {
    if (!dsu.unite(u, v)) {
        hasCycle = true;
    }
}

第 13 章 调试、对拍与赛前检查

13.1 最小化定位 bug

  1. 先确认输入：打印 n, m 和前几项，防止题目格式比人类更狡猾。

  2. 手造最小样例：n = 1、空边、全相等、全递增、全递减、不可达。

  3. 对 DP 打印表，对图论打印边，对二分打印 l, r, mid。

  4. 复杂题先写暴力，再随机对拍。眼睛常常很自信，输出并不会因此正确。

13.2 本地对拍流程

  1. gen.cpp 生成随机数据。

  2. brute.cpp 写容易确信正确的暴力。

  3. sol.cpp 写待验证正解。

  4. 循环运行，输出不一致就保存数据并停止。

13.2.1 Linux shell 伪脚本

g++ -std=c++17 gen.cpp -O2 -o gen
g++ -std=c++17 brute.cpp -O2 -o brute
g++ -std=c++17 sol.cpp -O2 -o sol

for ((i=1; ; i++)); do
       ./gen > data.in
       ./brute < data.in > ans1.out
       ./sol < data.in > ans2.out
       diff ans1.out ans2.out || break
       echo "OK $i"
done

13.3 常见 WA / RE / TLE / MLE 原因

现象 常见原因
样例过，提交 WA 边界、下标、long long、题意漏条件、输出格式、重复元素处理错误。
本地对，OJ RE 数组开小、递归爆栈、除以零、多组数据未清空、非法访问。
TLE 复杂度估算错、常数过大、重复计算、忘记剪枝、没有去重。
MLE 二维数组过大、vector 套 vector 太重、图边重复存太多、记忆化状态爆炸。
二分死循环 中点取法与边界更新不配套。
最短路错 用 Dijkstra 跑负边、无向边漏反向、INF 太小、没有过滤过期堆元素。
DP 错 状态定义模糊、初始化错误、枚举顺序错、滚动数组覆盖了仍需使用的旧值。
字符串错 0/1 下标混用、模式串长度与拼接偏移计算错、哈希忘记取模修正。

13.4 边界样例清单

  • n = 0 或空集合。

  • 图不连通。

  • n = 1。

  • 只有一条边。

  • 全部相等。

  • 起点等于终点。

  • 严格递增、严格递减。

  • 字符串长度为 1。

  • 最大值、最小值、负数。

  • 全重复字符。

  • 图无边、图完全连通。

  • 模数下结果为 0。

13.5 赛前模板自检

  • 亲手默写：二分、前缀和、差分、并查集、树状数组、Dijkstra、Kruskal、LCA、KMP。

  • 核对本资料中你最常用模板的下标习惯。

  • 记住每类算法的适用前提，不要把模板当护身符。

第 14 章 速查表

14.1 算法选择速查

需求 首选 备注
静态区间和 前缀和 修改后失效。
静态区间最值 Sparse Table 查询 O(1)。
单点改，区间和 树状数组 简洁高频。
区间改，区间查 线段树 懒标记。
动态频次第 k 小 树状数组二分 需离散化。
连续区间满足约束 双指针 条件需单调。
答案具有单调性 二分答案 写清 check。
最少步数 BFS 边权相同。
0/1 边权最短路 0-1 BFS 双端队列。
非负最短路 Dijkstra 负边禁用。
负边最短路 Bellman-Ford 还能判负环。
多源最短路小图 Floyd n^3。
最小生成树 Kruskal / Prim 稀疏图常用 Kruskal。
有向图缩点 Tarjan SCC 强连通分量。
约束真值 2-SAT 建蕴含图。
容量选择 背包 DP 先辨别物品类型。
子集状态 状压 DP n 不宜大。
字符串精确匹配 KMP / Z 线性。
多模式匹配 AC 自动机 多个词典串。
最长回文 Manacher 线性。
质因数与欧拉函数 分解 / φ 看规模。
组合数模质数 阶乘逆元 n < MOD 常见。
线段相交与凸包 计算几何 统一精度。

14.2 常用 STL 速查

容器 / 算法 常用操作 提醒
vector push_back、sort、erase 连续内存，最常用。
queue push、front、pop BFS。
deque 两端压入弹出 0-1 BFS、单调队列。
stack push、top、pop 单调栈、括号。
priority_queue 最大堆 / greater 最小堆 Dijkstra。
set insert、lower_bound 有序去重。
multiset 可重复、有序 删除一个元素要先找迭代器。
map 键值映射且有序 常数偏大。
unordered_map 均摊哈希映射 可能被卡，必要时自定义哈希。
bitset 位并行、count 状态集合优化。
lower_bound 第一个 ≥ x 有序序列。
upper_bound 第一个 > x 有序序列。
next_permutation 下一个排列 先排序后枚举。

14.3 模运算速查

  • 加法：(a + b) mod M 。

  • 减法：(a − b + M ) mod M 。

  • 乘法：(a · b) mod M ，大数时用 __int128。

  • 除法：不能直接除，须乘逆元。

  • 组合数：模数为质数时常用阶乘逆元。

14.4 二分边界速查

目标 mid 写法 更新
找第一个满足 (l + r) / 2 满足则 r = mid，否则 l = mid + 1
找最后一个满足 (l + r + 1) / 2 满足则 l = mid，否则 r = mid - 1

14.5 模板选型顺序

  1. 能用数组别上树。

  2. 能用前缀和别上树状数组。

  3. 能用树状数组别上懒标记线段树。

  4. 能用 BFS 别上 Dijkstra。

  5. 能用 Dijkstra 别上 SPFA。

  6. 能不用复杂模板就别把题写成工程项目。

附录 A 常用公式

A.1 数列与求和

  • 等差数列和： S n = n ( a 1 + a n ) 2 S_n = \dfrac{n(a_1 + a_n)}{2} Sn​=2n(a1​+an​)​。
  • 等比数列和： S n = a 1 1 − q n 1 − q S_n = a_1 \dfrac{1-q^n}{1-q} Sn​=a1​1−q1−qn​，其中 q ≠ 1 q \ne 1 q=1。
  • 前 n n n 个正整数和： n ( n + 1 ) 2 \dfrac{n(n+1)}{2} 2n(n+1)​。
  • 平方和： n ( n + 1 ) ( 2 n + 1 ) 6 \dfrac{n(n+1)(2n+1)}{6} 6n(n+1)(2n+1)​。

A.2 排列组合

  • 排列数： A n m = n ! ( n − m ) ! A_n^m = \dfrac{n!}{(n-m)!} Anm​=(n−m)!n!​。
  • 组合数： C n m = n ! m ! ( n − m ) ! C_n^m = \dfrac{n!}{m!(n-m)!} Cnm​=m!(n−m)!n!​。
  • 二项式定理： ( a + b ) n = ∑ k = 0 n C n k a n − k b k (a+b)^n = \sum_{k=0}^{n} C_n^k a^{n-k} b^k (a+b)n=∑k=0n​Cnk​an−kbk。
  • 卡特兰数： C a t n = 1 n + 1 C 2 n n Cat_n = \dfrac{1}{n+1} C_{2n}^{n} Catn​=n+11​C2nn​。

A.3 图论常识

  • 树有 n − 1 n-1 n−1 条边。
  • 连通无向图加一条非树边形成一个环。
  • DAG 存在拓扑序。
  • 无向图所有点度数之和为 2 m 2m 2m。

附录 B 代码片段索引

主题 位置
主函数、调试宏、__int128 第 2 章
前缀和、差分、双指针、二分 第 3 章
区间调度、逆序对、括号匹配 第 4 章
单调栈、DSU、Fenwick、线段树、ST 表 第 5 章
BFS、Dijkstra、最小生成树、LCA、SCC、Dinic、2-SAT 第 6 章
背包、LIS、LCS、区间 DP、树形 DP、数位 DP 第 7 章
KMP、Z 函数、Trie、哈希、Manacher、AC 自动机 第 8 章
数论、组合、CRT、矩阵快速幂、Miller-Rabin、高精度 第 9 章
计算几何基础与凸包 第 10 章
搜索、博弈、bitset 第 11 章
常见题型模板 第 12 章
调试、对拍与错误排查 第 13 章
算法选型与 STL 速查 第 14 章

结束语

这份资料的目标不是堆出一座模板博物馆，而是让常见问题有稳定入口：知道该翻哪一页、该套哪一类结构、该查哪一种边界。比赛时先求正确，再求漂亮。漂亮代码不会替错误答案领奖。

# c++ # 算法 # 数据结构 # 贪心算法 # 动态规划 # 剪枝 # 深度优先
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

深入Spring Boot生态中最核心部分 数据库交互spring-boot-starter-data-jpa和Hibernate (指南五)

avatar 亚马逊云科技技术品牌专区
cover

搜维尔科技：TESOLLO为世界机器人配备更智能的双手

avatar 亚马逊云科技技术品牌专区
cover

多模态推理的“思维之跃”：紫东太初4.0如何重塑AI认知边界

avatar 亚马逊云科技技术品牌专区