算法常用板子

常用函数

STL算法

1	next_permutation(a.begin(), a.end()) // 全排列生成

进制运算的内置函数（GCC/Clang）

1
2
3

__builtin_clz(unsigned int x)  // 统计前导零的数量
__builtin_ctz(unsigned int x)  // 统计末尾零的数量
__builtin_popcount(unsigned int x)  // 统计1的数量

C++ 匿名函数（Lambda 表达式）

// 基本语法
[捕获列表](参数列表) -> 返回类型 { 函数体 }

// 示例
auto add = [](int a, int b) -> int { return a + b; };

// 递归lambda需要指定类型
function<返回类型(传入类型)> func = [&](参数) -> 返回类型 {
    // 函数体
};

注意：有的递归lambda不能自动推导函数类型，需手写，例如：function<int(int, int)> 返回int，传入两个int。

基础算法模板

二分查找模板

int l = 0, r = INT_MAX;
while (l <= r) {
    int mid = (l + r) / 2;
    if (judge(mid)) {
        // 满足条件
        l = mid + 1;
    } else {
        // 不满足条件
        r = mid - 1;
    }
}

二分答案适用场景：

答案满足单调性（前半部分符合，后半部分不符合）
求最大/最小符合的值

小数精度处理：

题目要求保留3位小数时，可对每个数乘10000（多一位用于四舍五入）
计算完答案后除以10000.0

三分查找模板

用于单峰函数（先减后增或先增后减）寻找极值点。

1. 实数域（求极小值）

double l = 0, r = 1e9;
while (r - l > 1e-9) {
    double m1 = (2 * l + r) / 3;
    double m2 = (l + 2 * r) / 3;
    if (f(m1) < f(m2))
        r = m2;  // 极小值点在左侧
    else
        l = m1;  // 极小值点在右侧
}
double ans = f(l);

2. 整数域（求极小值）

long long l = 0, r = 1e9;
while (r - l > 5) {  // 剩下小区间时暴力枚举
    long long m1 = (2 * l + r) / 3;
    long long m2 = (l + 2 * r) / 3;
    if (f(m1) < f(m2))
        r = m2;
    else
        l = m1;
}
long long ans = f(l);
for (long long i = l + 1; i <= r; ++i)
    ans = min(ans, f(i));

3. 求极大值（凹函数）

将比较符号反转即可：

1	if (f(m1) > f(m2)) r = m2; else l = m1;

注意事项：

函数必须在给定区间内严格单峰

实数域精度 1e-9 可根据题目调整

整数域通常把小区间长度设为3~10，最后暴力枚举

滑动窗口（双端队列）

deque<int> dq;  // 一般存下标
for (int i = 0; i < n; i++) {
    // 维护最大值为例
    while (!dq.empty() && a[dq.back()] < a[i]) dq.pop_back();
    dq.push_back(i);

    // 边界维护
    // k定长：在while中加入 dq.front() <= i - k
    // 不定长：特殊讨论
}

核心思路：维护左边界还是右边界是个重要问题，一般维护右边界的较多。

数学公式与技巧

运算符优先级（从高到低）

() 括号
* / % 乘除取余
+ - 加减
<< >> 移位
< > <= >= 比较运算符
== != 相等判断
& 按位与
^ 按位异或
| 按位或
&& 逻辑与
|| 逻辑或
= 赋值

注意：位运算符（&, ^, |）的优先级低于比较运算符！遇到不确定的就加括号。

求和化简

$i \bmod j = i - [i/j] \times j$

交集计算

设两不等式 $l_1 \leq x \leq r_1$ 和 $l_2 \leq x \leq r_2$ 的交集：

1	L = max(min(r₁, r₂), max(l₁, l₂), 0)

需要严格保证 $l \leq r$ 。

整数取整

向下取整：x / t
向上去整：(x + t - 1) / t

一些复杂度

调和级数： $\sum_{i=1}^{m} \frac{1}{i} = O(\log m)$

正方形旋转坐标变换

设子矩阵左上角为 $(x_0, y_0)$ ，边长为 len。相对坐标：

$i_{rel} = x - x_0 + 1$
$j_{rel} = y - y_0 + 1$

顺时针旋转90°正变换： $(i', j') = (j, len - i + 1)$

逆时针旋转90°正变换： $(i', j') = (len - j + 1, i)$

逆变换（逆向查询）：

顺时针旋转（op=1）： $i = j', j = len - i' + 1$ （逆时针旋转）
逆时针旋转（op=2）： $i = len - j' + 1, j = i'$ （顺时针旋转）

if (op.op == 1) { // 顺时针旋转 → 逆变换为逆时针
    new_i_rel = len - j_rel + 1;
    new_j_rel = i_rel;
} else {          // 逆时针旋转 → 逆变换为顺时针
    new_i_rel = j_rel;
    new_j_rel = len - i_rel + 1;
}

数论

素数相关

埃氏筛

vector<bool> vis(N + 1, false);
for (int i = 2; i <= N; i++) {
    if (!vis[i]) {
        for (int j = i * i; j <= N; j += i) {
            vis[j] = true;
        }
    }
}

判断素数

bool isprime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

Miller-Rabin 素数测试

适用于 $10^{18}$ 范围内的大数素数判断，使用以下12个基底 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 可得到100%准确结果。

// 使用 __int128 实现大数模乘
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        exp /= 2;
    }
    return res;
}

bool miller_rabin_check(long long d, long long n) {
    long long a = 2 + rand() % (n - 4);
    long long x = power(a, d, n);

    if (x == 1 || x == n - 1) return true;

    while (d != n - 1) {
        x = (__int128)x * x % n;
        d *= 2;
        if (x == 1) return false;
        if (x == n - 1) return true;
    }
    return false;
}

bool is_prime(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    long long bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;

    for (long long a : bases) {
        if (n == a) return true;
        if (power(a, d, n) != 1) {
            long long t = d;
            bool prime = false;
            while (t < n - 1) {
                if (power(a, t, n) == n - 1) {
                    prime = true;
                    break;
                }
                t *= 2;
            }
            if (!prime) return false;
        }
    }
    return true;
}

GCD与LCM

GCD性质

$\gcd(a+c, b+c) = \gcd(a+c, b-a)$

性质解释：对于任意整数 $x, y$ ，有： $\gcd(x, y) = \gcd(x, y-x)$

这是因为 $\gcd(x, y)$ 整除 $x$ 和 $y$ ，所以也整除 $y-x$ ；反过来，任何整除 $x$ 和 $y-x$ 的数也能整除 $x + (y-x) = y$ 。因此两个数对的公约数集合完全相同。

常见应用：

欧几里得算法（辗转相除法）：不断用大数减小数（或取模）
化简GCD问题：当两个数同时加上同一个数 $c$ 时，它们的差保持不变
求解线性丢番图方程：若 $\gcd(a, b) = d$ ，则存在整数 $x, y$ 使 $ax + by = d$
判断互质：若 $|a-b| = 1$ ，则两数一定互质

快速幂与逆元

快速幂模板

int qpow(int base, int exp, int mod) {
    int res = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp & 1) res = (long long)res * base % mod;
        base = (long long)base * base % mod;
        exp >>= 1;
    }
    return res;
}

乘法逆元

// 逆元（mod为质数时）
int inv(int n, int mod) {
    return qpow(n, mod - 2, mod);
}

// a * inv(b) % mod 等价于 a / b % mod

扩展欧几里得求逆元（mod为非质数）

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

void solve() {
    ll a, m;
    cin >> a >> m;
    ll inv, tmp;
    exgcd(a, m, inv, tmp);
    inv = (inv % m + m) % m;  // 处理负数
    cout << inv << '\n';
}

组合数

阶乘与组合数（结合快速幂逆元取模）

vector<int> fac(n + 1, 1);
for (int i = 1; i <= n; i++) {
    fac[i] = (long long)fac[i - 1] * i % mod;
}

auto C = [&](int a, int b) -> int {
    if (a < 0 || b < 0 || b > a) return 0;
    return (long long)fac[a] * inv(fac[b]) % mod * inv(fac[a - b]) % mod;
};

隔板法

part(n, k) 的含义

定义：将 $n$ 个相同的物品分成 $k$ 个非空连续组的方法数。

直观理解：

有 $n$ 个物品排成一行：○ ○ ○ ○ ○（5个）

要分成 $k$ 组，需要在 $n-1$ 个空隙中放 $k-1$ 个隔板。

从 $n-1$ 个空隙选 $k-1$ 个放隔板。

公式推导：

n个物品 → n-1个空隙
分成k组 → 需要k-1个隔板
从n-1个空隙选k-1个放隔板
选法数 = C(n-1, k-1)

用公式表示：

1
2
3

int part(int n, int k) {
    return C(n - 1, k - 1);
}

线性基

作用

判断一个数能否被异或出来：通过不断消去高位，看最后是否能得到0
求最大异或和：贪心从高位到低位，如果异或后变大就异或
求最小异或和：最小的非0 basis元素
求第k小异或和：需要重构线性基

创建

vector<int> a(n + 1);
vector<int> basis(61, 0);  // int 32位, long long 64位

// 插入操作（构建线性基）
void insert(int x) {
    for (int i = 60; i >= 0; i--) {
        if (!(x & (1LL << i))) continue;
        if (!basis[i]) {
            basis[i] = x;
            return;
        }
        x ^= basis[i];
    }
}

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

查询（是否可以异或出某数）

bool query(int x) {
    for (int i = 60; i >= 0; i--) {
        if ((x >> i) & 1) {
            if (!basis[i]) return false;
            x ^= basis[i];
        }
    }
    return x == 0;
}

得到最大异或

int getmax() {
    int ans = 0;
    for (int i = 60; i >= 0; i--) {
        if ((ans ^ basis[i]) > ans) ans ^= basis[i];
    }
    return ans;
}

带掩码的线性基

用于记录每个基向量由哪些原向量异或而成。

vector<int> bas(35), msk(35), idd(70);
for (int i = 1; i <= n; i++) {
    int v = (a[i] ^ b[i]);
    if (!v) continue;
    int cur = v;
    unsigned long long curm = (1ULL << cnt);
    for (int j = 31; j >= 0; j--) {
        if ((cur >> j) & 1) {
            if (!bas[j]) {
                bas[j] = cur;
                msk[j] = curm;
                idd[cnt] = i;
                cnt++;
                break;
            }
            cur ^= bas[j];
            curm ^= msk[j];
        }
    }
}

// 查询是否能得到X
unsigned long long pick = 0;
int cur = X;
for (int j = 31; j >= 0; j--) {
    if ((cur >> j) & 1) {
        if (!bas[j]) {
            cout << -1 << endl;
            return;
        }
        cur ^= bas[j];
        pick ^= msk[j];
    }
}
vector<bool> use(n + 1);
for (int i = 0; i < cnt; i++)
    if ((pick >> i) & 1) use[idd[i]] = 1;
for (int i = 1; i <= n; i++)
    cout << (use[i] ? b[i] : a[i]) << " \n"[i == n];

其他数论算法

秦九韶算法

一种高效求多项式值的算法，将多项式 $P(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$

改写为嵌套形式： $P(x) = (\cdots((a_nx + a_{n-1})x + a_{n-2})x + \cdots + a_1)x + a_0$

只需 $n$ 次乘法和 $n$ 次加法，避免直接计算高次幂。

取模版本：

1	ans = (ans * x + a_i) mod M

大数/小数近似

对于一个数 $N = M \cdot 10^L$ ，其中 $L = \log_{10}(n)$ 。

那么对于 $\lfloor N/n \rfloor$ 的前几位与 $M$ 相同。

快速找到某数组中有几个该数的约数

类似线性筛的思想：

int maxnum = 2e6;
vector<int> c(maxn + 1);
for (int i = 1; i <= maxnum; i++) {
    if (cnt[i] == 0) continue;
    for (int j = i; j <= n; j += i) {
        c[j] += cnt[i];
    }
}

注意：先预处理数组中数的出现次数，要求数的范围不大。

图论

最短路

Floyd-Warshall 算法

寻找加权图中所有顶点对之间最短路径的动态规划算法。

特点：

允许负权边（但不能有负权环）
时间复杂度： $O(V^3)$
空间复杂度： $O(V^2)$

核心思想：逐步允许每个顶点作为”中转点”，更新任意两点之间的距离：

1	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

算法步骤：

初始化距离矩阵 dist
对于 $k = 1$ 到 $n$ （中转点）
对于 $i = 1$ 到 $n$
对于 $j = 1$ 到 $n$
更新最短路径

检测负权环：若任意 dist[i][i] < 0，则存在负权环。

图的连通性

判环 - 三色DFS

用于有向图检测环。

颜色	数值	含义
白色(White)	0	未访问
灰色(Gray)	1	正在访问（在递归栈中）
黑色(Black)	2	访问完成

判环条件：遇到灰色邻居节点。

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

class DirectedGraphCycle {
private:
    vector<vector<int>> adj;
    vector<int> color;  // 0:白 1:灰 2:黑
    int n;

    bool dfs(int u) {
        color[u] = 1;  // 标记为灰色

        for (int v : adj[u]) {
            if (color[v] == 0) {          // 白色：未访问
                if (dfs(v)) return true;
            } else if (color[v] == 1) {   // 灰色：发现环！
                return true;
            }
        }

        color[u] = 2;  // 回溯，标记为黑色
        return false;
    }

public:
    DirectedGraphCycle(int vertices) : n(vertices) {
        adj.resize(n);
        color.assign(n, 0);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    bool hasCycle() {
        color.assign(n, 0);
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) {
                if (dfs(i)) return true;
            }
        }
        return false;
    }
};

强联通分量 SCC（Tarjan算法）

基本概念：

dfn[u]：节点u的时间戳
low[u]：u及其子树，最多走一条回边能到达的最早节点
belong[u]：节点u所属的SCC编号
stk：收集遍历的节点

const int maxn = 1e5 + 10;
vector<int> edge[maxn], belong(maxn);
vector<int> dfn(maxn), low(maxn);
vector<int> num(maxn);
vector<bool> vis(maxn);
stack<int> st;
int scc = 0, tim = 0;

void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    vis[u] = true;
    st.push(u);

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

    if (dfn[u] == low[u]) {
        scc++;
        while (!st.empty()) {
            int cur = st.top();
            st.pop();
            belong[cur] = scc;
            num[scc]++;
            vis[cur] = false;
            if (cur == u) break;
        }
    }
}

Kosaraju算法

算法流程：

在原图执行DFS，记录每个顶点的完成时间，按完成时间降序排序（拓扑排序）
在转置图中，按排序顺序依次DFS，找到所有连通分量

int n, m;
cin >> n >> m;
vector<int> g[n], r[n];  // g:原图, r:转置图

for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    r[v].push_back(u);
}

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

// DFS lambda
auto dfs = [&](this auto const &dfs, int u, int type) -> void {
    vis[u] = 1;
    vector<int> &p = type ? r[u] : g[u];
    for (auto v : p) {
        if (!vis[v]) dfs(v, 0);
    }
    if (!type) topo.push_back(u);
};

// 第一次DFS：拓扑排序
for (int i = 1; i <= n; i++) {
    if (!vis[i]) dfs(i, 0);
}

vis.assign(n + 1, 0);
int SCC = 0;

// 第二次DFS：在转置图中找SCC
for (auto it = topo.rbegin(); it != topo.rend(); it++) {
    if (!vis[*it]) {
        SCC++;
        dfs(*it, 1);
    }
}

cout << SCC << endl;

二分图与匹配

最大匹配（匈牙利算法）

// 1. 建图
vector<int> a[n];  // 左部节点的邻接表
vector<int> b;      // 右部节点（可离散化）

// 2. 初始化
vector<int> vis(b.size()), match(b.size(), -1);
int t = 0;  // 时间戳优化

// 3. DFS寻找增广路
function<bool(int)> dfs = [&](int u) -> bool {
    for (auto v : a[u]) {
        if (vis[v] == t) continue;
        vis[v] = t;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
};

// 4. 为每个左部节点尝试匹配
int cnt = 0;
for (int i = 0; i < n; i++) {
    t++;
    if (dfs(i)) cnt++;
}
cout << cnt << endl;

时间复杂度： $O(n \cdot E)$ ，最坏 $O(VE)$

拓扑排序

对有向无环图（DAG）的顶点进行线性排序，若存在边 $A \to B$ ，则 $A$ 排在 $B$ 前面。

核心思想：不断移除入度为0的节点。

vector<int> p(n + 1);           // 入度
vector<vector<int>> mp(n + 1);   // 邻接表

// 读入边时更新入度
for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    mp[u].push_back(v);
    p[v]++;
}

queue<int> q;
vector<int> ans;

// 所有入度为0的节点入队
for (int i = 1; i <= n; i++) {
    if (p[i] == 0) q.push(i);
}

while (!q.empty()) {
    int t = q.front();
    q.pop();
    ans.push_back(t);

    for (auto x : mp[t]) {
        p[x]--;
        if (p[x] == 0) q.push(x);
    }
}

// 若ans大小 != n，说明图中有环

最小生成树

Prim算法

贪心算法，针对 $n-1$ 条边。

vector<pair<int, int>> p[n + 1];  // 邻接表 (终点, 权值)
vector<int> vis(n + 1, 0);
vector<long long> dis(n + 1, LLONG_MAX);

dis[1] = 0;

for (int i = 1; i < n; i++) {  // 循环n-1次
    int cur = -1;
    long long minnum = LLONG_MAX;

    for (int j = 1; j <= n; j++) {
        if (!vis[j] && minnum > dis[j]) {
            cur = j;
            minnum = dis[j];
        }
    }

    // if (cur == -1) 图不连通

    vis[cur] = 1;

    for (auto [x, t] : p[cur]) {
        if (!vis[x] && t < dis[x]) {
            dis[x] = t;
        }
    }
}

// dis数组存储的即为最小生成树的边权值
// 求和即为最小生成树的权值和

Kruskal算法

按边贪心，用并查集维护连通性。

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

vector<Edge> edges;

int ans = 0, cnt = 0;
sort(edges.begin(), edges.end());

for (auto &e : edges) {
    int u = e.u, v = e.v, w = e.w;
    if (unio(u, v)) {  // 并查集合并
        ans += w;
        cnt++;
        if (cnt == n - 1) break;
    }
}

if (cnt != n - 1) ans = -1;  // 图不连通

并查集模板

vector<int> par(n + 1), sz(n + 1);

void init(int n) {
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
}

int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);  // 路径压缩
}

bool unio(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;

    // 按大小合并
    if (sz[x] < sz[y]) swap(x, y);
    par[y] = x;
    sz[x] += sz[y];
    return true;
}

字符串

KMP算法

核心作用：字符串查找（在文本中查找模式串）

核心思想：保证文本串的指针永不回溯，利用已经匹配成功的部分信息，跳过绝不可能匹配成功的中间位置。

四大作用

作用	说明	对应函数
精准定位	返回模式串在文本中所有出现位置	`searchAll()`
重叠计数	统计重叠出现的次数	`countOccurrences()`
最长前缀匹配	计算文本与模式串的最长匹配长度	`longestPrefixMatch()`
寻找循环节	判断字符串是否由重复子串组成	利用前缀函数

C++ KMP通用模板

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

class KMP {
private:
    string pattern;
    vector<int> pi;  // 前缀函数数组
    int m;

    // 构建前缀函数
    void buildPrefix() {
        pi.resize(m);
        int j = 0;
        for (int i = 1; i < m; ++i) {
            while (j && pattern[i] != pattern[j]) {
                j = pi[j - 1];
            }
            if (pattern[i] == pattern[j]) ++j;
            pi[i] = j;
        }
    }

public:
    KMP(const string& p) : pattern(p), m(p.size()) {
        if (m > 0) buildPrefix();
    }

    // 返回所有匹配的起始下标
    vector<int> searchAll(const string& text) const {
        vector<int> positions;
        if (m == 0) return positions;

        int j = 0;
        for (int i = 0; i < (int)text.size(); ++i) {
            while (j > 0 && text[i] != pattern[j]) {
                j = pi[j - 1];
            }
            if (text[i] == pattern[j]) ++j;
            if (j == m) {
                positions.push_back(i - m + 1);
                j = pi[j - 1];  // 支持重叠匹配
            }
        }
        return positions;
    }

    // 统计匹配次数
    int countOccurrences(const string& text) const {
        return (int)searchAll(text).size();
    }

    // 最长前缀匹配
    int longestPrefixMatch(const string& text) const {
        if (m == 0) return 0;
        int j = 0, res = 0;

        for (char c : text) {
            while (j > 0 && c != pattern[j]) {
                j = pi[j - 1];
            }
            if (c == pattern[j]) {
                ++j;
                res = max(res, j);
                if (j == m) j = pi[j - 1];
            }
        }
        return res;
    }
};

字符串哈希

哈希公式

对于字符串 $S = s_1s_2...s_n$ ：

基数（base）：通常取质数，如 131, 13331, 137
模数（mod）：通常取大质数，如 $10^9+7$ , $10^9+9$ , 998244353

$hash(S) = (s_1 \times base^{n-1} + s_2 \times base^{n-2} + \cdots + s_n \times base^0) \bmod mod$

创建哈希数组

const int mod = 1e9 + 7;
const int BASE = 131;
const int N = 1e6 + 5;
string str;
int n;
int Hash[N], P[N];

void initHASH() {
    P[0] = 1;
    for (int i = 1; i <= n; i++) {
        Hash[i] = (Hash[i - 1] * BASE + str[i]) % mod;
        P[i] = (long long)P[i - 1] * BASE % mod;
    }
}

// 获取子串 [l, r] 的哈希值
int getHash(int l, int r) {
    return ((Hash[r] - (long long)Hash[l - 1] * P[r - l + 1] % mod + mod) % mod);
}

结构体包装

struct StringHash {
    vector<int> p, h;
    StringHash(const string& s) {
        int n = s.size();
        p.resize(n + 1, 1);
        h.resize(n + 1, 0);
        for (int i = 0; i < n; i++) {
            p[i + 1] = (long long)p[i] * BASE % MOD;
            h[i + 1] = ((long long)h[i] * BASE + s[i]) % MOD;
        }
    }

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

哈希判断回文

时间复杂度： $O(2n)$

同时维护正推和倒推的哈希数组，通过比较区间哈希值判断回文。

循环移位判断

子串 $S[0..k-1]$ 循环移位后的哈希：

ll rotate_hash(const string &s, int k) {
    int n = s.length();
    k %= n;
    if (k == 0) return h[n];

    ll prefix = get_hash(0, k);      // hash(S[0..k-1])
    ll total = h[n];                 // hash(S)
    ll suffix_hash = (total - (long long)prefix * p[n - k] % mod + mod) % mod;
    ll rotated = ((long long)suffix_hash * p[k] % mod + prefix) % mod;

    return rotated;
}

数据结构

线段树

模板一：区间求和（支持区间加法）

class SegmentTreeSumAdd {
private:
    int n;
    vector<long long> st;     // 区间和
    vector<long long> lazy;   // 加法懒标记

    void build(int p, int L, int R, const vector<int>& A) {
        if (L == R) {
            st[p] = A[L];
            return;
        }
        int m = (L + R) / 2;
        build(p * 2, L, m, A);
        build(p * 2 + 1, m + 1, R, A);
        st[p] = st[p * 2] + st[p * 2 + 1];
    }

    void propagate(int p, int L, int R) {
        if (lazy[p] == 0) return;

        st[p] += lazy[p] * (R - L + 1);
        if (L != R) {
            lazy[p * 2] += lazy[p];
            lazy[p * 2 + 1] += lazy[p];
        }
        lazy[p] = 0;
    }

    long long query(int p, int L, int R, int i, int j) {
        propagate(p, L, R);
        if (i > j) return 0;
        if (L >= i && R <= j) return st[p];

        int m = (L + R) / 2;
        return query(p * 2, L, m, i, min(m, j)) +
               query(p * 2 + 1, m + 1, R, max(i, m + 1), j);
    }

    void update(int p, int L, int R, int i, int j, long long val) {
        propagate(p, L, R);
        if (i > j) return;

        if (L >= i && R <= j) {
            st[p] += val * (R - L + 1);
            if (L != R) {
                lazy[p * 2] += val;
                lazy[p * 2 + 1] += val;
            }
            return;
        }

        int m = (L + R) / 2;
        update(p * 2, L, m, i, min(m, j), val);
        update(p * 2 + 1, m + 1, R, max(i, m + 1), j, val);
        st[p] = st[p * 2] + st[p * 2 + 1];
    }

public:
    SegmentTreeSumAdd(int sz) : n(sz) {
        st.assign(4 * n + 1, 0);
        lazy.assign(4 * n + 1, 0);
    }

    SegmentTreeSumAdd(const vector<int>& init) : n(init.size()) {
        st.assign(4 * n + 1, 0);
        lazy.assign(4 * n + 1, 0);
        build(1, 1, n, init);
    }

    long long query(int i, int j) { return query(1, 1, n, i, j); }
    void add(int i, int j, long long val) { update(1, 1, n, i, j, val); }
};

模板二：区间最值（支持区间赋值）

class SegmentTreeMaxAssign {
private:
    int n;
    vector<int> A;
    vector<int> st;
    vector<int> lazy;  // -1表示无标记

    int l(int p) { return p << 1; }
    int r(int p) { return (p << 1) + 1; }

    int conquer(int a, int b) {
        if (a == -1) return b;
        if (b == -1) return a;
        return max(a, b);
    }

    void build(int p, int L, int R) {
        if (L == R) {
            st[p] = A[L];
            return;
        }
        int m = (L + R) / 2;
        build(l(p), L, m);
        build(r(p), m + 1, R);
        st[p] = conquer(st[l(p)], st[r(p)]);
    }

    void propagate(int p, int L, int R) {
        if (lazy[p] == -1) return;

        st[p] = lazy[p];

        if (L != R) {
            lazy[l(p)] = lazy[p];
            lazy[r(p)] = lazy[p];
        }
        lazy[p] = -1;
    }

    int query(int p, int L, int R, int i, int j) {
        propagate(p, L, R);
        if (i > j) return -1;
        if (L >= i && R <= j) return st[p];

        int m = (L + R) / 2;
        return conquer(
            query(l(p), L, m, i, min(m, j)),
            query(r(p), m + 1, R, max(i, m + 1), j)
        );
    }

    void update(int p, int L, int R, int i, int j, int val) {
        propagate(p, L, R);
        if (i > j) return;

        if (L >= i && R <= j) {
            st[p] = val;
            lazy[p] = val;
            return;
        }

        int m = (L + R) / 2;
        update(l(p), L, m, i, min(m, j), val);
        update(r(p), m + 1, R, max(i, m + 1), j, val);
        st[p] = conquer(st[l(p)], st[r(p)]);
    }

public:
    SegmentTreeMaxAssign(int sz) : n(sz), A(n + 1),
                                   st(4 * n + 1, -1),
                                   lazy(4 * n + 1, -1) {}

    int query(int i, int j) { return query(1, 1, n, i, j); }
    void assign(int i, int j, int val) { update(1, 1, n, i, j, val); }
};

模板三：区间求和（支持区间赋值 + 区间加法）

class SegmentTreeSumBoth {
private:
    int n;
    vector<long long> st;
    vector<long long> lazy_set;  // 赋值懒标记，LLONG_MIN表示无标记
    vector<long long> lazy_add;  // 加法懒标记

    void apply_set(int p, int L, int R, long long val) {
        st[p] = val * (R - L + 1);
        lazy_set[p] = val;
        lazy_add[p] = 0;  // 赋值清空加法标记
    }

    void apply_add(int p, int L, int R, long long val) {
        st[p] += val * (R - L + 1);
        if (lazy_set[p] != LLONG_MIN) {
            lazy_set[p] += val;
        } else {
            lazy_add[p] += val;
        }
    }

    void propagate(int p, int L, int R) {
        if (L == R) return;

        int m = (L + R) / 2;

        // 先传播赋值标记（优先级高）
        if (lazy_set[p] != LLONG_MIN) {
            apply_set(p * 2, L, m, lazy_set[p]);
            apply_set(p * 2 + 1, m + 1, R, lazy_set[p]);
            lazy_set[p] = LLONG_MIN;
        }

        // 再传播加法标记
        if (lazy_add[p] != 0) {
            apply_add(p * 2, L, m, lazy_add[p]);
            apply_add(p * 2 + 1, m + 1, R, lazy_add[p]);
            lazy_add[p] = 0;
        }
    }

    // ... 其他函数类似模板二

public:
    SegmentTreeSumBoth(int sz) : n(sz),
                                 st(4 * n + 1, 0),
                                 lazy_set(4 * n + 1, LLONG_MIN),
                                 lazy_add(4 * n + 1, 0) {}

    long long query(int i, int j) { return query(1, 1, n, i, j); }
    void assign(int i, int j, long long val) { update_set(1, 1, n, i, j, val); }
    void add(int i, int j, long long val) { update_add(1, 1, n, i, j, val); }
};

三种模板对比：

特性	模板一	模板二	模板三
查询	最值	区间和	区间和
更新	区间赋值	区间加法	赋值+加法
懒标记数	1个	1个	2个
优先级	-	-	赋值 > 加法

树状数组（二叉索引树）

普通版

template<class T>
struct BIT {
    int n;
    vector<T> a;

    BIT(int sz = 0) : n(sz), a(sz + 1) {}

    // 单点修改：位置p增加v
    void add(int p, T v) {
        for (; p <= n; p += p & -p) a[p] += v;
    }

    // 前缀查询：1到p的和
    T ask(int p) {
        T r = 0;
        for (; p; p -= p & -p) r += a[p];
        return r;
    }

    // 区间查询：[l, r]的和
    T ASK(int l, int r) { return ask(r) - ask(l - 1); }

    // 区间修改：[l, r]增加v（差分思想）
    void ADD(int l, int r, T v) {
        add(l, v);
        add(r + 1, -v);
    }

    // 查询第k大（前缀和>=k的最小位置）
    int kth(T k) {
        int idx = 0;
        int bitmax = (1 << (int)log2(n));

        while (bitmax > 0) {
            int nextidx = idx + bitmax;
            if (nextidx <= n && a[nextidx] < k) {
                k -= a[nextidx];
                idx = nextidx;
            }
            bitmax >>= 1;
        }
        return idx + 1;
    }
};

进阶版（带权差分）

维护两个数组 c1（存d[i]）和 c2（存带权差分 $(i-1) \cdot d[i]$ ）。

template <class T>
struct BIT {
    int n;
    vector<T> c1, c2;

    BIT(int sz = 0) : n(sz), c1(sz + 5), c2(sz + 5) {}

    void _add(int p, T v, vector<T>& c) {
        for (; p <= n; p += p & -p) c[p] += v;
    }

    T _ask(int p, vector<T>& c) {
        T r = 0;
        for (; p; p -= p & -p) r += c[p];
        return r;
    }

    // 区间修改：[l, r]增加v
    void range_add(int l, int r, T v) {
        _add(l, v, c1);
        _add(r + 1, -v, c1);
        _add(l, (l - 1) * v, c2);
        _add(r + 1, r * (-v), c2);
    }

    // 前缀和：sum(1..x)
    T prefix_sum(int x) {
        T sum1 = _ask(x, c1);
        T sum2 = _ask(x, c2);
        return x * sum1 - sum2;
    }

    // 区间查询：[l, r]的和
    T range_sum(int l, int r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
};

珂朵莉树（区间赋值操作）

又称老司机树，用 set 维护区间，复杂度近似 $O(m \log n)$ 。

节点定义与split操作

struct Node {
    int l, r;
    mutable int v;  // mutable允许在const函数中修改

    Node(int L, int R = -1, int V = 0) : l(L), r(R), v(V) {}

    bool operator<(const Node &other) const {
        return l < other.l;
    }
};

set<Node> s;

// split操作：分离区间
set<Node>::iterator split(int pos) {
    auto it = s.lower_bound(pos);
    if (it != s.end() && it->l == pos) return it;

    --it;
    if (pos > it->r) return s.end();

    int L = it->l, R = it->r, V = it->v;
    s.erase(it);
    s.insert(Node(L, pos - 1, V));
    return s.insert(Node(pos, R, V)).first;
}

区间操作

// 区间加法
void add(int l, int r, int val = 1) {
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl++) itl->v += val;
}

// 区间赋值
void assign(int l, int r, int val = 0) {
    auto itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(Node(l, r, val));
}

// 区间求和
int sum(int l, int r, int ex, int mod) {
    auto itr = split(r + 1), itl = split(l);
    int res = 0;
    for (; itl != itr; itl++) {
        res = (res + (long long)(itl->r - itl->l + 1) * qpow(itl->v, ex, mod)) % mod;
    }
    return res;
}

// 区间第k小（倒数第k小）
int rank(int l, int r, int k, bool reversed = false) {
    if (reversed) k = r - l + 2 - k;

    auto itr = split(r + 1), itl = split(l);
    vector<pair<int, int>> vp;

    for (; itl != itr; itl++) {
        vp.push_back({itl->v, itl->r - itl->l + 1});
    }

    sort(vp.begin(), vp.end());
    for (auto &i : vp) {
        k -= i.second;
        if (k <= 0) return i.first;
    }
    return -1;
}

单调栈

原理

单调栈是一种栈内元素保持单调性的数据结构。

核心思想：

入栈时，如果破坏单调性，就弹出栈顶元素，直到满足单调性
每个元素最多入栈一次、出栈一次，时间复杂度 $O(n)$

应用场景

栈类型	寻找方向	寻找目标
单调递增栈	左/右	第一个比当前小的元素
单调递减栈	左/右	第一个比当前大的元素

常见口诀：

找右边第一个更大的 → 从右向左遍历，维护单调递减栈
找左边第一个更小的 → 从左向右遍历，维护单调递增栈

手写栈模板

vector<int> stk(n);
int top = 0;

// 入栈
stk[++top] = x;

// 取出栈顶元素
cout << stk[top];

// 获取大小
cout << top << endl;

// 是否为空
if (top) { /* 非空 */ }

// 遍历栈
for (int i = 1; i <= top; i++) { /* ... */ }

寻找下一个更大元素

vector<int> a(n + 1);
vector<int> st(n + 1);
int top = 0;
vector<int> ans(n + 1);

for (int i = 1; i <= n; i++) {
    while (top && a[i] > a[st[top]]) {
        ans[st[top]] = i;  // 第st[top]个元素的后一个更大元素是i
        top--;
    }
    st[++top] = i;
}

// 栈中留下的是没有下一个更大元素的数

单调栈上二分

因为单调栈中存的都是下标，满足二分的单调性，可以找某个下标。

动态规划

LIS最长递增子序列

$O(n \log n)$ 优化版本：

vector<int> LIS;
for (int i = 1; i <= n; i++) {
    auto idx = lower_bound(LIS.begin(), LIS.end(), a[i]);
    if (idx == LIS.end()) {
        LIS.push_back(a[i]);
    } else {
        *idx = a[i];
    }
}
cout << LIS.size() << endl;

背包问题

多重背包 - 二进制优化

时间复杂度： $O(T \times m \times \sum \log(s_i))$

int amount = s[i];
for (int k = 1; amount > 0; k <<= 1) {
    int num = min(k, amount);
    int volume = num * v[i];
    int value = num * w[i];

    // 01背包
    for (int j = m; j >= volume; j--) {
        dp[j] = max(dp[j], dp[j - volume] + value);
    }

    amount -= num;
}

多重背包 - 单调队列优化

const int maxn = 1e6 + 10;
vector<int> dp(maxn), backdp(maxn);

for (int i = 1; i <= n; i++) {
    backdp = dp;
    int volume = v[i];
    int value = w[i];
    int amount = s[i];

    // 分为 0~volume 组，r表示余数
    for (int r = 0; r < volume; r++) {
        deque<int> dq;

        for (int k = 0; r + k * volume <= m; k++) {
            int j = r + k * volume;

            // dp[j] = max(backdp[t] + (k-t) * value)
            // 即 dp[j] > backdp[t] - t*value + k*value

            while (!dq.empty() &&
                   backdp[j] - k * value >= backdp[dq.back()] -
                   (dq.back() - r) / volume * value) {
                dq.pop_back();
            }

            dq.push_back(j);

            // 移除超出数量限制的元素
            while (!dq.empty() && (j - dq.front()) / volume > amount) {
                dq.pop_front();
            }

            // 更新dp[j]
            dp[j] = max(dp[j],
                        backdp[dq.front()] + (j - dq.front()) / volume * value);
        }
    }
}

杂项

高精度

模板一：非负大整数（基数1e9）

struct BigInt {
    static const int BASE = 1000000000;  // 基数：10^9
    vector<int> d;  // 低位在前，高位在后

    BigInt(long long x = 0) { *this = x; }

    BigInt& operator=(long long x) {
        d.clear();
        if (x == 0) {
            d.push_back(0);
            return *this;
        }
        while (x) {
            d.push_back(x % BASE);
            x /= BASE;
        }
        return *this;
    }

    void trim() {
        while (d.size() > 1 && d.back() == 0) d.pop_back();
    }

    string toString() const {
        if (d.empty()) return "0";
        string s = to_string(d.back());
        for (int i = (int)d.size() - 2; i >= 0; --i) {
            string t = to_string(d[i]);
            s += string(9 - t.size(), '0') + t;
        }
        return s;
    }
};

// 比较运算符
static inline bool operator<(const BigInt& a, const BigInt& b) {
    if (a.d.size() != b.d.size()) return a.d.size() < b.d.size();
    for (int i = (int)a.d.size() - 1; i >= 0; --i) {
        if (a.d[i] != b.d[i]) return a.d[i] < b.d[i];
    }
    return false;
}

// 乘以整数
static inline void mul_int(BigInt& a, int m) {
    if (m == 0) {
        a = 0;
        return;
    }
    long long carry = 0;
    for (size_t i = 0; i < a.d.size(); ++i) {
        long long cur = carry + 1LL * a.d[i] * m;
        a.d[i] = cur % BigInt::BASE;
        carry = cur / BigInt::BASE;
    }
    while (carry) {
        a.d.push_back(carry % BigInt::BASE);
        carry /= BigInt::BASE;
    }
}

// 除以整数
static inline BigInt div_int(const BigInt& a, int v) {
    BigInt q;
    q.d.assign(a.d.size(), 0);
    long long rem = 0;
    for (int i = (int)a.d.size() - 1; i >= 0; --i) {
        long long cur = a.d[i] + rem * BigInt::BASE;
        q.d[i] = cur / v;
        rem = cur % v;
    }
    q.trim();
    return q;
}

模板二：支持负数（字符串存储）

class BigInt {
private:
    string num;

    void trim() {
        if (num.empty()) {
            num = "0";
            return;
        }

        bool negative = (num[0] == '-');
        string digits = negative ? num.substr(1) : num;

        size_t pos = digits.find_first_not_of('0');
        if (pos == string::npos) {
            num = "0";
            return;
        }

        digits = digits.substr(pos);
        num = negative ? "-" + digits : digits;
    }

public:
    BigInt() : num("0") {}
    BigInt(const long long &n) : num(to_string(n)) {}
    BigInt(const string &n) : num(n) { trim(); }

    BigInt multiply(const BigInt &rhs) const {
        string a = num, b = rhs.num;
        int sign = 1;

        if (a[0] == '-') {
            sign *= -1;
            a = a.substr(1);
        }
        if (b[0] == '-') {
            sign *= -1;
            b = b.substr(1);
        }

        a = a.substr(a.find_first_not_of('0'));
        b = b.substr(b.find_first_not_of('0'));
        if (a.empty() || b.empty()) return BigInt(0);

        vector<int> c(a.length() + b.length(), 0);

        for (int i = a.length() - 1; i >= 0; i--) {
            for (int j = b.length() - 1; j >= 0; j--) {
                int mul = (a[i] - '0') * (b[j] - '0');
                int sum = mul + c[i + j + 1];
                c[i + j + 1] = sum % 10;
                c[i + j] += sum / 10;
            }
        }

        string result;
        for (int digit : c) {
            if (!(result.empty() && digit == 0)) {
                result.push_back(digit + '0');
            }
        }

        if (result.empty()) result = "0";
        if (sign == -1 && result != "0") result = "-" + result;

        return BigInt(result);
    }

    friend BigInt operator *(const BigInt &a, const BigInt &b) {
        return a.multiply(b);
    }

    friend ostream& operator <<(ostream &os, const BigInt &n) {
        os << n.num;
        return os;
    }

    // 比较运算符（完整支持负数）
    friend bool operator <(const BigInt &lhs, const BigInt &rhs) {
        string a = lhs.num, b = rhs.num;
        bool na = (a[0] == '-'), nb = (b[0] == '-');

        if (na && !nb) return true;
        if (!na && nb) return false;

        if (na) a = a.substr(1);
        if (nb) b = b.substr(1);

        if (!na && !nb) {
            if (a.length() != b.length()) return a.length() < b.length();
            return a < b;
        }

        if (a.length() != b.length()) return a.length() > b.length();
        return a > b;
    }

    friend bool operator >(const BigInt &lhs, const BigInt &rhs) { return rhs < lhs; }
    friend bool operator ==(const BigInt &lhs, const BigInt &rhs) { return lhs.num == rhs.num; }
};

位运算与格雷码

位运算操作

^   按位异或
&   按位与
|   按位或
<<  左移（乘以2^n）
>>  右移（整除2^n）

常用技巧：

操作	代码	说明
判断奇偶	`n & 1`	结果为1是奇数
获取最低8位	`n & 0xFF`
清零第k位	`n & (~(1 << k))`
第k位置1	`n \| (1 << k)`
取反	`n ^ 1`	对带符号整数：`1 ^ A = -A - 1`

异或性质：

$x \oplus 0 = x$
$x \oplus x = 0$
满足交换律和结合律
两次异或同一个数会还原： $a \oplus b \oplus b = a$

格雷码

性质：

单位距离性：相邻数字有且仅有一位不同
循环性：首尾也仅一位不同
反射构造：可通过镜像对称前一位格雷码并加前缀递归生成

转换公式：

二进制转格雷码： $G = B \oplus (B >> 1)$

格雷码转二进制：

$b_{n-1} = g_{n-1}$
$b_i = g_i \oplus b_{i+1}$ 对 $i = n-2 \ldots 0$

其他技巧

__int128的使用

用于处理超大整数运算（超过64位）。

输入输出（因为标准流不支持）：

__int128 read() {
    char arr[30];
    __int128 res = 0;
    scanf("%s", arr);
    for (int i = 1; i <= strlen(arr); i++) {
        res = res * 10 + (arr[i] - '0');
    }
    return res;
}

void print(__int128 num) {
    if (num > 9) print(num / 10);
    putchar(num % 10 + '0');
}

注意事项：

在GCC、Linux系统、大多数OJ上支持

在VS2017等可能不支持

不能关闭同步流

判断回文数

bool isreverse(int x) {
    if (x < 0) return false;
    if (x != 0 && x % 10 == 0) return false;

    int reversedHalf = 0;
    while (x > reversedHalf) {
        reversedHalf = reversedHalf * 10 + x % 10;
        x /= 10;
    }

    return x == reversedHalf || x == reversedHalf / 10;
}

构造回文数

for (int i = 1; i <= 1000000; i++) {
    string ss = to_string(i), tt;
    tt = ss;
    reverse(tt.begin(), tt.end());

    // 构造偶数位回文
    string s1 = ss + tt;
    // 构造奇数位回文
    string s2 = ss;
    for (int j = 1; j < tt.size(); j++)
        s2 += tt[j];
}

暴力寻找MEX

vector<int> vis(n);
int mex = 0;

for (int i = 0; i < n; i++) {
    vis[a[i]]++;
}

while (max < n && vis[mex]) mex++;

只使用/2和-1变为0的最小操作次数

int minSteps(int a) {
    if (a == 0) return 0;

    int bits = 32 - __builtin_clz(a);      // 二进制位数
    int ones = __builtin_popcount(a);      // 1的个数

    return bits + ones - 1;
}

差分

普通差分

1	d[i] = a[i] - a[i-1]

O(1)区间修改：d[l] += k; d[r+1] -= k;
O(n)区间查询

带权差分

引入两个数组：

c1：存 $d[i] = a[i] - a[i-1]$
c2：存带权差分 $(i-1) \cdot d[i]$

区间修改（O(1)）：

1 2	c1[l] += k; c1[r+1] -= k; c2[l] += (l-1) * k; c2[r+1] -= r * k;

区间查询（O(1)）：

1 2	pre[x] = x * sum(c1[1..x]) - sum(c2[1..x]) pre[l..r] = pre[r] - pre[l-1]

前缀和

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

二维差分

格子点坐标（ $x_1, y_1$ 到 $x_2, y_2$ ）：

dif[x1][y1]++
dif[x2 + 1][y1]--
dif[x1][y2 + 1]--
dif[x2 + 1][y2 + 1]++

边的交点（ $x_1, y_1$ 到 $x_2, y_2$ ）：

dif[x1][y1]++
dif[x2][y1]--
dif[x1][y2]--
dif[x2][y2]++

容斥原理

待补充完整内容。

错误与经验总结

常见错误

计算连续段的初始长度：当条件不符时，初始长度应该为1
map vs unordered_map：尽量使用map，unordered_map可能因为创建太多而超时
变量命名：避免重复变量名，因为有时变量会定义在全局中
运算符优先级：特别注意优先级问题
取模运算：注意取模的细节
BFS/DFS标记：应在入队前标记，而不是出队后
环的处理：遇到环、前后相连并要删去元素时，向链表思考
代码注释：把dill注释掉要记得恢复
标记问题：注意标记的正确性
思维缜密性：代码错误往往在想不到的地方
手模的重要性：手模是很重要的

附录

常用小知识

行号构成的集合

这些行号构成的集合是 $\{1 + k \cdot a \bmod n \mid k = 0,1,2,\ldots\}$ ，等价于1加上由 $a$ 生成的加法子群。

在模 $n$ 的整数环中，由 $a$ 生成的循环子群的大小为 $n / \gcd(n, a)$ 。

手动模拟的重要性

手模是很重要的，可以帮助发现逻辑错误。

文件信息

整理日期：2026-07-16
总行数：3437行
分类数：7个主要分类

文档持续更新中…