标签：std 知识点 NOI int sum 2023 mathcal 可以 dp

NOI 2023 考前知识点总复习

其实就是把熟悉或不熟悉的东西再过一遍，防止考场上出现会了做法却因为忘了算法而写不出来的问题。

可能会一句话概括，也可能附上一点代码片段。

如果不想复习知识点，只想要一点考前提示，可以直接翻到本文最底部。

I. 数据结构、树上问题

Hash Table

设 Hash Table 的大小为 $V$，对元素维护一个 $[0,V-1]$ 的键值，并插入键值对应位置的链表中，访问时遍历该键值对应链表中所有元素。链表用邻接表实现。随机情况下单次查询 $\mathcal O(\dfrac{n}{V})$。

std::unordered_map 被卡常的时候可能有用。

并查集

只路径压缩、只按秩合并单次查询复杂度均为 $\mathcal O(\log n)$，两个一起做复杂度 $\mathcal O(\alpha(n))$。

可以用栈记录操作序列，支持撤销。需要撤销时不能路径压缩。

单调栈/笛卡尔树

笛卡尔树的键值满足堆的性质，结点的下标满足二叉搜索树的性质。

笛卡尔树建树：单调栈维护极右链。

for(int i = 1; i <= n; ++i){
    while(tp && a[i] >= a[st[tp]]) R[st[tp]] = i - 1, --tp;
    L[i] = st[tp] + 1;
    st[++tp] = i;
}
while(tp) R[st[tp]] = n, --tp;

每个点有一个”控制区间“：即这个点在序列的某个连续区间内是最值。这些区间只可能不交或包含。

在动态维护单调栈的过程中，可以用线段树维护单调栈中区间来求出以当前栈顶为右端点的信息。

树状数组

x & -x 可以取出 x 的 lowbit。树状数组本身支持的操作是单点修改，前缀/后缀查询。

区间加区间求和：对差分数组进行修改的时候对每个位置的贡献形如 $kx+b$，其中 $x$ 是下标。

树状数组上二分：本质上就是倍增，访问结点 $cur+2^k$ 时累加上 $[cur+1,cur+2^k]$ 的信息。

常数小。

线段树

支持半群信息的合并与区间查询。维护矩阵等不具有交换律的信息时，要特别注意顺序问题。

注意标记下放顺序。

99% 的题目不需要 Segbeats。只对区间某个数取 $\max$ 或其他类似操作考虑标记永久化。

线段树合并一定是递归到较浅的叶子时返回。启发式合并有的时候也可以多一个 $\log$ 做线段树合并做的事情。

可持久化线段树跟正常线段树没有特别显著的区别。注意空间一定要开够，卡空间时可以用一个栈回收不再使用的结点。

线段树上二分一定注意卡边界，要特别考虑不存在的情况。

对于某些势能均摊的问题暴力向下递归复杂度是有保证的。

序列分治

三维偏序：一维排序后分治下去，左右两边做二维偏序。

出现“左边对右边的贡献”时，可以考虑分治是否可做。

线段树正是在动态维护分治结构。

“线段树分治”：就是对时间轴分治，规避掉信息的删除，用多一个 $\log$ 的代价改为“撤销”。

扫描线/二维数点

离线算法。

比如最经典的：二维平面上单点加，矩形求和。考虑从左向右扫描横坐标，树状数组上维护前缀每个纵坐标位置的贡献，那么矩形和就是其右边界的贡献减去左边界之前的贡献。

for(int i = 1; i <= n; ++i){
    rec[l - 1].push_back({L, R, -1});
    rec[r].push_back({L, R, 1});
}
for(int i = 1; i <= m; ++i) ins[x].push_back(y);
for(int i = 1; i <= n; ++i){
    for(auto p : ins[i]) BIT.upd(p, 1);
    for(auto p : rec[i]) ans += BIT.qry(p.l, p.r) * p.w;
}

很多问题可以转化成二维数点问题。常见的例子：序列与时间轴、子树结点深度与时间戳编号、对区间左右端点合法位置的限制等。

平衡树

能用 std::set 和权值线段树维护的就不要写平衡树。

单点插入删除+区间修改或区间翻转的时候考虑用平衡树。

fhq-treap 的 split 可以按权值分裂，也可以按子树大小分裂。

void split_val(int p, int k, int &x, int &y){
    if(!p) return x = y = 0, void();
    if(val[p] <= k) x = p, split_val(rs, k, rs, y);
    else y = p, split_val(ls, k, x, ls);
    pushup(p);
}

void split_siz(int p, int k, int &x, int &y){
    if(!p) return x = y = 0, void();
    if(k <= siz[ls]) y = p, split(ls, k, x, ls);
    else x = p, split(rs, k - siz[ls] - 1, rs, y);
    pushup(p);
}

二叉搜索树左旋或右旋，中序遍历保持不变。

fhq-treap 可以可持久化。

ODT

就是 std::set 暴力维护连续段。哪来的这么多花里胡哨的名字。

用于区间覆盖问题，复杂度是均摊的。

01-Trie

可以维护权值线段树维护的部分信息。

全局加一：从低位向高位插入，极右链打翻转标记。

K-D Tree

交替维度取中点（std::nth_element）划分建树，树上维护信息的方式类似平衡树。本质上就是优化过的暴力。

带动态插入结点时用替罪羊树（定期重构）。

链剖分

重链剖分

从任意结点到根只经过 $\mathcal O(\log n)$ 条重链，每一条重链必然延伸到某个叶子。

所有轻儿子子树大小和为 $\mathcal O(n\log n)$。

继承重儿子信息，暴力递归轻儿子求解被广泛称为 “dsu on tree” 或树上启发式合并。在很多题目中有较容易实现的优势，而且常数一般不大。

链分治：在重儿子处打标记，记录轻儿子信息。

重链 dfn 序连续，且是子树中的一段前缀。

长链剖分

关于内存池分配：

int *f[N], buf[N * 10], *ptr = buf;
void add(int x){f[x] = ptr, ptr += len[x] + 1;}
void dfs(int x){
    // do something
    if(son[x]) f[x] = f[son[x]] + 1, dfs(son[x]);
    for(auto y : G[x]) if(y != fa[x] && y != son[x]){
        add(y);
        dfs(y);
        // do something
    }
}

当某些与深度有关的信息可以大范围继承的时候，考虑长链剖分。

树的直径

两棵树合并，新的直径端点必然是原来四个点中的两个。

树分治

树的重心

重心的性质：最大子树最小（小于等于一半）、到所有点的距离和最小

点数为偶数的树可能有两个重心，这时两个重心一定被一条边连接。

树添加一个叶子，重心最多移动一条边。

点分治/边分治

考虑经过分治中心的贡献。

点对间经过分治中心的贡献：可以先不考虑在同一子树的情况，再遍历每个子树将算重的贡献减去。

边分治三度化：每个儿子上多接一个虚点，虚点从左到右连接，父亲连接第一个虚点。注意虚点不能参与任何贡献的统计。

将分治结构显式建出，便有了点分树、边分树。有树高 $\mathcal O(\log n)$ 的优异性质，同时可以在上面用数据结构维护更复杂的信息。

重构树

重构树满足叶子是原树上的节点，其余点是原树上的边，点权是原树边的边权，任意两个叶子 lca 的点权为它们在原树路径上的边权最大/最小值。

构造：用 Kruskal 的过程解决：从小到大枚举边权，每次合并两个连通块，如果成功合并则建一个点权为该边边权的点，并将该点作为合并前两个连通块根的父亲。

重构树常被用于解决生成树上的瓶颈路问题。

树哈希

ull calc(int x){
    x ^= (x << 13);
    x ^= (x >> 7);
    x ^= (x << 17);
    return x;
}
void get_hash(int x){
    f[x] = 1;
    for(auto y : G[x]) f[x] += calc(f[y]);
}

Huffman 树

给定一些串的出现次数，要求将每个串映射到一个不同的二进制串上，使得二进制串长总和最短。

直接贪心，每次选两个最小的元素合并。

可以扩展到 $k$ 进制，就是选最小的 $k$ 个元素合并。

II. 数论

线性筛

每一个合数都被最小的质因子筛掉。可以线性筛的东西包括但不限于：$\varphi,\mu,\sigma_k,i^k$ 或者一些自己构造的积性函数。

整除分块

将所有 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 值相同的一起处理。

for(int l = 1, r; l <= n; l = r + 1){
    r = n / (n / l);
    ans += calc(n / l) * (pre(r) - pre(l - 1));
}

狄利克雷卷积

定义两个函数 $f(x)$ 和 $g(x)$ 的 Dirichlet 卷积结果 $h(x)$ 为：

\[h(x)=\sum_{d\mid x}f(d)g(\frac{x}{d}) \]

也记为 $f *g=h$。

Dirichlet 卷积满足交换律、结合律、分配律。

常用结论：$\varphi*1=\text{id},\mu*1=\epsilon,1*1=\sigma_0,1*\text{id}=\sigma_1,\mu*\text{id}=\varphi$。

就此可以得到莫比乌斯反演最常见的形式：$\sum\limits_{d\mid n}\mu(d)=[n=1]$。

杜教筛

在 $\mathcal O(n^{\frac{2}{3}})$ 时间内求积性函数前缀和。

设有积性函数 $f,g, h$ 满足 $f*g=h$，$F,G,H$ 为 $f,g,h$ 的前缀和。

那么由 $H(n)=\sum\limits_{i=1}^nF(\left\lfloor\dfrac{n}{i}\right\rfloor)g(i)$ 可以得到 $F(n)g(1)=H(n)-\sum\limits_{i=2}^nF(\left\lfloor\dfrac{n}{i}\right\rfloor)g(i)$，右边整除分块+记忆化搜索。

线性预处理出前 $\mathcal O(n^{\frac{2}{3}})$ 项后时间复杂度为 $\mathcal O(n^{\frac{2}{3}})$。

扩展欧几里得（exgcd）

用于求出 $ax+by=\gcd(a,b)$ 的一组整数解。

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

扩展中国剩余定理

用于同余方程的合并。假设有

\[\begin{cases} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2} \end{cases} \]

两个方程。将它们转化为 $x=k_1m_1+a_1=k_2m_2+a_2$，即 $a_2-a_1=k_1m_1-k_2m_2$。

转化为 $ax+by=\gcd(a,b)$ 的形式用 exgcd 求解。其中如果 $a_2-a_1\nmid \gcd(m_1,m_2)$ 则无解。

假设 $(q_1,q_2)$ 是求出的可行解，那么 $x\equiv q_1m_1+a_1\pmod{\text{lcm}(m_1,m_2)}$。

扩展欧拉定理

\[a^b\equiv \begin{cases} a^b, & b < \varphi(p)\\ a^{b\bmod \varphi(p)+\varphi(p)}, & b\ge\varphi(p) \end{cases} \pmod{p} \]

在解决幂塔问题时常用。注意 $\varphi(\varphi(\cdots))$ 只需要 $\mathcal O(\log n)$ 层就可以将值变为 $1$。

BSGS

在 $\mathcal O(\sqrt p)$ 时间内求解 $a^x\equiv b\pmod p$。要求 $a,p$ 互质。

令 $B=\lceil\sqrt p\rceil,x=qB-r$，则 $a^{qB}\equiv ba^r\pmod p$。那么维护好 $a^k$ 和 $a^{kB} (k\le B)$ 在哈希表上查就行了。

原根

定义：称 $\gcd(a,m)=1$ 时，满足 $a^n\equiv 1\pmod m$ 的最小正整数 $n$ 为 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$，那么 $g$ 为模 $m$ 的原根当且仅当 $\gcd(g,m)=1$ 且 $\delta_m(g)=\varphi(m)$。即，$g$ 满足 $g^i\bmod m,0< i < \varphi(m)$ 两两不同。

一个数存在原根当且仅当 $n=1,2,4,p^k,2p^k$，原根存在时最小原根在 $\mathcal O(n^{\frac{1}{4}})$ 级别，所以暴力找原根（枚举 $\varphi(n)$ 的非平凡约数 $d$，若不存在 $g^d\equiv 1\pmod n$ 则 $g$ 为 $n$ 的一个原根）一般是可以接受的。

若 $n$ 有原根，则 $n$ 的原根个数为 $\varphi(\varphi(n))$。

Miller-Rabin

对一个数 $n$ 进行素性测试，快速判断其是否为质数。

费马素性测试告诉我们，如果 $a^{n-1}\not\equiv 1\pmod n$ 则 $n$ 一定不是质数。

但有一部分合数对于所有 $a\in [2,n-1]$ 都满足 $a^{n-1}\equiv 1\pmod n$，这时我们再结合二次探测定理进行判断：若 $n$ 是质数，则 $x^2\equiv 1\pmod n$ 的解只有 $x\equiv 1\pmod n$ 或 $x\equiv n-1\pmod n$。

那么每轮测试选取 $x$，令 $n-1=u\times 2^k$，特判 $x^u\equiv 1\pmod n$ 后依次枚举 $i\in [0,k)$ 判断是否存在 $u\times 2^i$ 满足 $x^{u\times 2^i}\equiv n-1\pmod n$，如果有，那么通过本轮测试，否则无法通过。在 $2^{64}$ 范围内，只需要检验前 $12$ 个质数（$\le 37$）即可保证正确性。

III. 组合数学、计数相关

感觉看完 ix35 的 NOI 一轮复习 IV：组合计数就足够了。

具体数学中的内容在 NOI 中有点 Overkill。

下面只写一些最常用的结论/用法。

由于我对生成函数/形式幂级数理解不深，这部分请参考网络上更深入的讲解，以下略去。

Lucas 定理

\[\binom{n}{m}\bmod p=\binom{n\bmod p}{m\bmod p}\cdot\binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\bmod p \]

即将 $n,m$ 在 $p$ 进制下的每一位求组合数后相乘。递归求解即可。

$p=2$ 时有经典结论：$\dbinom{n}{m}\bmod 2=[m\subseteq n]$。

Kummer 定理

$\dbinom{n+m}{n}$ 中质因子 $p$ 的次数恰好为 $n+m$ 在 $p$ 进制下计算时的进位次数。

使用 Kummer 定理可以将一些问题转化为数位 dp 求解。

二项式反演

附一篇讲二项式反演的博客

将“恰好选择”的问题转化为“钦定必选，剩余任意“有时能够简化问题，理解二项式反演需要对容斥原理有所了解。

常见的形式有两种：

\[g_n=\sum_{i=n}^m\binom{i}{n}f_i \Leftrightarrow f_n=\sum_{i=n}^m(-1)^{i-n}\binom{i}{n}g_i \qquad(1) \]

\[g_n=\sum_{i=m}^n\binom{n}{i}f_i \Leftrightarrow f_n=\sum_{i=m}^n(-1)^{n-i}\binom{n}{i}g_i \qquad(2) \]

其中 $(1)$ 式含义是钦定至少 $n$ 个满足条件，剩余随意；$(2)$ 式相反，表示钦定至多 $n$ 个满足条件。$(1)$ 式相对更常用一些。

组合恒等式

\[\begin{aligned} m\binom{n}{m} &= n\binom{n-1}{m-1} &(1)\\ \binom{n}{m}\binom{m}{r} &= \binom{n}{r}\binom{n-r}{m-r} &(2)\\ \sum_{i=0}^n\binom{i}{m} &= \binom{n+1}{m+1} &(3)\\ \sum_{i+j=k}\binom{n}{i}\binom{m}{j} &= \binom{n+m}{k} &(4)\\ \end{aligned} \]

组合意义：$(1)$ 从 $n$ 个球中选 $m$ 个，再钦定一个代表，等价于先选好代表，再在剩余求中选 $m-1$ 个。$(2)$ 从 $n$ 个球中选 $m$ 个，再从 $m$ 个里选 $r$ 个就是将所以球分成了大小为 $n-m,m-r,r$ 的三组，等价于从 $n$ 个球里选 $r$ 个，再从剩余 $n-r$ 个球里选 $m-r$ 个。$(3)$ 枚举最后一个选的球的位置 $i+1$，剩下 $m$ 个球在前 $i$ 个中选。$(4)$ 有两堆大小分别为 $n,m$ 的球，从两堆中共选出 $k$ 个。

斯特林数

用 $\begin{bmatrix}n \\ m\end{bmatrix}$ 表示第一类斯特林数：$n$ 个元素组成 $m$ 个圆排列的方案数。

用 $\begin{Bmatrix}n\\ m\end{Bmatrix}$ 表示第二类斯特林数：$n$ 个元素划分到 $m$ 个集合的方案数。

两类斯特林数均可以根据其组合意义 $\mathcal O(n^2)$ 递推。

第二类斯特林数可以 $\mathcal O(n)$ 求单项，$\begin{Bmatrix}n\\ m\end{Bmatrix}=\sum\limits_{i=0}^m(-1)^{m-i}\dfrac{i^n}{i!(m-i)!}$，证明考虑二项式反演。

普通幂和下降幂的相互转换：

\[x^n=\sum_k\begin{Bmatrix}n\\ k\end{Bmatrix}x^{\underline k} \Leftrightarrow x^{\underline n}=\sum_k\begin{bmatrix}n \\ k\end{bmatrix}(-1)^{n-k}x^k \]

普通幂和上升幂的相互转换：

\[x^n=\sum_k\begin{Bmatrix}n \\ k\end{Bmatrix}(-1)^{n-k}x^{\overline k} \Leftrightarrow x^{\overline n}=\sum_k\begin{bmatrix}n\\ k\end{bmatrix}x^k \]

Burnside 引理

粗略来说就是去除同构的本质不同方案数等于所有置换不动点个数的平均值。

无根树的 Prüfer 序列

以下默认 $n\ge 2$。

每次选择树上编号最小的叶节点并删掉它，将它的父亲编号加入当前序列的末尾，这样重复操作 $n-2$ 次便得到了一棵无根树的 Prüfer 序列。

所有 $n$ 个结点的无根树与所有 $n^{n-2}$ 种序列一一对应。

每个结点在 Prüfer 序列中出现的次数是其在树上的度数减 $1$。

常见数列

斐波那契数列：$1,1,2,3,5,8,13,\dots$；有通项公式 $F(n)=\dfrac{1}{\sqrt 5}((\dfrac{1+\sqrt 5}{2})^n-(\dfrac{1-\sqrt 5}{2})^n)$，可以矩阵快速幂求单项/前缀和，利用通项公式计算的时候可以考虑扩域。

卡特兰数：$1,2,5,14,42,\dots$；注意卡特兰数的各种意义（比如，括号匹配、二叉树），以及需要考虑能否将题目的奇怪条件转化成格路计数（这篇总结里就不详细写了）。

贝尔数：$1,2,5,15,52,\dots$；将 $n$ 个有标号元素划分成若干集合的方案数；是第二类斯特林数的行前缀和。

划分数：$1, 2, 3, 5, 7, 11, 15, 22,\dots$；划分数有经典的 $\mathcal O(n\sqrt n)$ 求法：每次添加一个 $1$ 或全局加一，根号分治。

错排列数：$1,2,9,44,265,\dots$；递推式 $D_n=(n-1)(D_{n-1}+D_{n-2})$。

III-i. 线性代数与其它数学相关

因为我目前没有系统学习大学知识，所以以下内容非常不严谨，仅供理解，不保证符合任何规范。

拉格朗日插值

已知 $n$ 次函数 $f$ 的 $n+1$ 个点值，可以在 $\mathcal O(n^2)$ 时间内求出任意 $f(x)$：

\[f(x)=\sum_{i=1}^{n+1}y_i\prod_{j\neq i}\dfrac{x-x_j}{x_i-x_j} \]

如果点值连续，可以通过预处理前缀后缀积做到线性。

将上式暴力乘起来求出每项系数即可得到 $f(x)$ 的系数表示。

二元函数的插值类似：

\[f(x,y)=\sum_i\sum_j z_{i,j}\prod_{k\neq i}\frac{x-x_k}{x_i-x_k}\prod_{p\neq j}\frac{y-y_p}{y_j-y_p} \]

行列式

定义：对于方阵 $A$，$\det A$ 表示其行列式，满足：

\[\det A=\sum_{\sigma\in S_n}\text{sgn}(\sigma)\prod_{i=1}^n a_{i,\sigma_i} \]

其中 $\text{sgn}(\sigma)$ 表示 $\sigma$ 中逆序数的奇偶性，若逆序数为偶数为 $1$，否则为 $-1$。

初等变换：$(1)$ 将某一行乘上 $k$，行列式值也乘 $k$。$(2)$ 将两行互换，行列式值乘 $-1$。$(3)$ 将第 $i$ 行的 $k$ 倍加到第 $j$ 行上，行列式值不变（行和列的初等变换是一致的）。

对于一般的 $A$，常用高斯消元法求解 $\det A$。

当题目中出现排列计数奇偶相减的时候，要考虑是否与行列式的定义相似，能否转化为行列式问题求解。

线性相关与线性无关

简单来说，一个向量组 $a_1,a_2,\dots,a_n$ 线性无关，当且仅当其中任意一个向量均无法被其余向量线性表出。

例如，在异或线性基中存储的基底就是线性无关的，其中每个向量长度为 $k$，向量中每个元素的取值为 $\{0,1\}$，并且任意一个满足上述条件的向量都能被该异或线性基中存储的 $k$ 个线性无关的向量线性表出。

线性基的插入：

void ins(int x){
    for(int i = 30; ~i; --i) if(x >> i & 1){
        if(!bas[i]) return bas[i] = x, void();
        else x ^= bas[i];
    }
}

按照上述的插入方式，$bas_i$ 中存储的元素第 $i$ 位一定为 $1$。

异或线性基经常被用来解决子集异或最大值、本质不同子集异或值的个数等问题。

矩阵树定理

定义 $A$ 为无向图 $G$ 的邻接矩阵，$D$ 为 $G$ 的度数矩阵（$d_{i,i}=\text{deg}(i)$，其余元素为 $0$）。

定义无向图 $G$ 的基尔霍夫矩阵 $K=D-A$，$K'$ 为 $K$ 去掉任何一行一列后的方阵，则 $G$ 的生成树个数为 $\det K'$。如果边带权，则 $\det K'=\sum\limits_{T \text{ is a spanning tree of }G}\prod\limits_{e\in T}w(e)$。

对于有向图，将 $D$ 定义改为出度/入度后，去掉 $K$ 的第 $i$ 行 $i$ 列，可以统计以 $i$ 为根的内向树/外向树个数。

如果希望将上述定义中的 $\prod$ 改为 $\sum$，可以将边权写成一次函数 $kx+1$ 的形式，最后取一次项。

统计恰好有 $k$ 条关键边，可以将关键边边权设为 $x$，其余为 $1$，最后取求出的行列式 $[x^k]$ 的值。在实际实现中可以将 $x$ 带入 $n+1$ 个点值，再插值回去求解。

LGV 引理

用于一类不相交路径计数问题的求解。

令 $A=\{a_1,a_2,\dots,a_n\}$ 为起点，$B=\{b_1,b_2,\dots,b_n\}$ 为终点，$e(a,b)$ 为 $a$ 到 $b$ 所有不同路径权值积的和，设矩阵

\[M=\begin{bmatrix} e(a_1,b_1), &e(a_1,b_2), &\dots, &e(a_1,b_n)\\ e(a_2,b_1), &e(a_2,b_2), &\dots, &e(a_2,b_n)\\ \vdots &\vdots & \ddots & \vdots\\ e(a_n,b_1), &e(a_n,b_2), &\dots, &e(a_n,b_n) \end{bmatrix} \]

则引理说明，$M$ 的行列式是所有从 $A$ 到 $B$ 的不相交路径 $P=\{p_1,p_2,\dots,p_n\}$ 的带符号和：

\[\det M = \sum_{P:A\rightarrow B}\text{sgn}(\sigma(P))\prod_iw(p_i) \]

当图中一个起点只对应一个固定终点时（比如，网格图边界上的两排点），利用 LGV 引理可以高效求解该类图中不相交路径的组数。

IV. 动态规划（dp）

背包问题

背包问题可以在伪多项式时间内求解。大值域的背包问题往往都有特殊解法，如果没有任何特殊性质目前是无法快速求解的。

多重背包优化：$(1)$ 二进制分组：例如，将体积为 $18$ 的物品分为 $1,2,4,8,3$ 五个物品（注意不是只取所有二进制位为 $1$ 的，在此例子中仅仅分为 $2,16$ 显然无法覆盖所有情况）。$(2)$ 单调队列优化：按 $\bmod v_i$ 分组，因为每一组内的元素只能内部转移。维护一个滑动窗口，如果元素过期（物品数不够）就从队头弹出，否则取队头更新答案。

背包可以合并。

区间 dp

当维护的信息只与区间长度有关时，状态中可以只记录长度。

对于区间最值的钦定，可以多记一维值域。

区间 dp 不一定先枚举区间长度，以某种顺序枚举左右端点可能会使得这个 dp 存在优化复杂度的空间。

区间 dp 可以将两维状态放在二维平面上考虑。

树上 dp

树上背包的 siz 优化：每个点对 $(u,v)$ 只在 $lca$ 处贡献一次，时间复杂度 $\mathcal O(n^2)$。

void dp(int x){
    siz[x] = 1;
    // do something
    for(auto y : G[x]){
        dp(y);
        for(int i = siz[x]; i >= 0; --i){
            for(int j = siz[y]; j >= 0; --j){
                // do something
            }
        }
        siz[x] += siz[y];
    }
}

有些树上的 dp 问题可以通过 dfs 序转化为序列问题。

换根：将子树外的所有结点也看作一棵子树处理。一般写法是两次 dfs，第一次处理子树内信息，第二次同时处理子树外信息。换根的信息需要具有可减性。

合适的状态可以通过线段树合并解决，线段树合并时分别记录需要合并的两个子树对对方的贡献，还是注意标记的下传顺序。

状态压缩

状态不一定是一个二进制数；很多东西都可以记到状态中。

当合法状态看似是指数级别但很稀疏时，利用 std::map 只转移合法状态可能有奇效。

网格上的逐行转移，可以考虑轮廓线 dp，即，二进制状态中只记录当前与继续填的格子有关系的格子的状态。

dp of dp：通常里层是判定性的 dp，外层用里层判定出的合法性做状态进行计数。不要认为一定过不去就不去写，一定要写一个记忆化搜索看看合法状态到底有多少。

有时，建出自动机后在自动机上 dp 也是不错的选择。

数位 dp

本身不难理解：将需要记录的关于数位的信息都记录到状态中，加上是否顶上界的判断，记忆化搜索。

但数位 dp 可以出现在很多奇奇怪怪的地方。当题目的值域很大，并且存在复杂度依赖值域的做法时，需要思考能否将问题拆分到数位上逐位解决。

递推的数位 dp 跟记忆化搜索其实没有本质区别，明确正确的转移顺序即可。

动态 dp

将转移写成矩阵的形式，线段树优化矩阵乘法。这里”矩阵乘法“多指广义上的，比如 $(\min,+)$ 矩乘。

在树上需要配合重链剖分，对每一条重链维护向上、向下两个方向的矩阵。

矩阵中 $a_{i,j}$ 的值可以理解为从 $f_{x,i}$ 转移到 $f_{x+1,j}$ 时的系数。

常见 dp 优化

优化状态设计：缩紧某一维的上界，将两维信息合并，将某一维状态移入 dp 数组中保存的值中，保存的值与某一维交换；使用更简洁的信息覆盖所有可行状态。

优化转移：

前缀和优化。

std::bitset 优化。

矩阵快速幂优化。

斜率优化：有各种不同的形式，需要具体问题具体分析。一般来说是将转移写成 $y=kx+b$ 的形式，维护出一个凸壳，然后通过给定斜率与凸壳相切来最大化/最小化截距（即，找到最优的转移点）。有小部分斜率优化需要变形出斜率的形式，然后在凸壳上找到最有的斜率。一般用单调队列或单调栈维护凸壳上的点。部分斜率优化可以用李超线段树（线段树下标是值域）插直线实现，简洁方便。

决策单调性：如果区间的权值满足四边形不等式（相交的两段和优于包含的两段和），那么转移必然具有决策单调性。决策单调性 dp 有经典的分治做法：即令 $[pl,pr]$ 为当前分治区间 $[l,r]$ 中点可能取到的决策点范围，暴力枚举找到对于 $mid$ 的最优决策点 $p$，然后两边递归解决 $[l,mid-1],[pl,p]$ 和 $[mid+1,r],[p,pr]$ 的子问题。

dp 的值可能是关于某一维大小的多项式，需要考虑能否通过拉格朗日插值得到结果。

计数相关

线头 dp：在当前状态下伸出”线头“，在之后的填数过程中将”线头“接起来。

排列计数常按值域从小到大/从大到小考虑。

使用容斥原理的题目，可以将容斥系数直接乘进转移的贡献中。

虽然说理论上不考卷积，但实在没办法的时候还是要看看转移式能否拆成卷积的形式进行优化。

V. 字符串

以下字符串 $s$ 的子串 $[l,r]$ 用记号 $s[l,r]$ 表示。$+$ 表示字符串前后拼接。

$\text{lcp}(i,j)$ 表示 $s$ 以 $i$ 开头的后缀与以 $j$ 开头的后缀的最长公共前缀。

Hash

Hash 是解决很多字符串问题的利器，尤其是在不想使用高级字符串算法时，二分+Hash 能够在多一个 $\log$ 的情况下达到几乎一致的效果。

哈希冲突是选手比赛时必须考虑的问题。假定选择的模数为 $p$，那么在字符串总数在 $\mathcal O(\sqrt p)$ 个时就容易发生哈希冲突。使用自然溢出哈希速度快，冲突概率小，但可以被特殊构造的数据卡掉：令 $s_1=\texttt{a}$，$s'_i$ 为 $s_i$ 中 $\texttt{a}$ 和 $\texttt{b}$ 互换，那么构造 $s_n=s_{n-1}+s'_{n-1}$，$n\ge 12$ 就可以卡掉自然溢出哈希。使用双模哈希+随机模数可以大大减小被卡哈希的概率，但代码常数会变大，因此谨慎使用。

KMP 与 border 相关结论

一个字符串的最小正周期等于其长度减去最长 border。

任意字符串的所有 border 长度最多形成 $\mathcal O(\log n)$ 个值域不交的等差数列。

Periodicity Lemma: 假设 $p,q$ 是 $s$ 的正周期，且 $p+q-\gcd(p,q)\le |s|$，则 $\gcd(p,q)$ 也是 $s$ 的正周期。

Z 函数（扩展 KMP）

定义 $z_i$ 为 $\text{lcp}(1,i)$。其实 Z 函数的功能与 border 类似，从 $i$ 开始向前是 border，向后是 Z 函数。

特判 $z_1=|s|$。从 $2$ 开始，按如下方法可以线性得到 $z_2\sim z_n$：

维护右端点最靠右的匹配段 $[l,r]$（初始 $l=r=0$），称之为 Z-box。计算 $z_i$ 时：如果当前 $i\le r$，那么 $z_i$ 至少有 $\min(z_{i-l+1},r-i+1)$，然后再暴力扩展（如果 $s_{z_i+1}=s_{z_i+i}$ 就将 $z_i$ 增加）到无法扩展为止。最后如果 $i+z_i-1 > r$，那么将 Z-box 更新为 $[i,i+z_i-1]$。

其实 Z 函数的作用很大程度上跟 KMP 是类似的，视情况哪个更方便一些用哪个就行。

Manacher

其实与 Z 函数的计算过程非常相似。

定义 $p_i$ 为以 $i$ 为回文中心的回文半径长度。为解决偶回文串的情况，我们预先在 $s$ 的每两个字符中间加一个相同的占位符。

还是维护右端点最靠右的回文半径 $[pos,r]$，计算 $p_i$ 时，如果 $i\le r$，$p_i$ 可以至少取到 $\min(p_{2i-pos},r-i+1)$（$2i-pos$ 与 $i$ 关于 $pos$ 对称），然后当 $s_{i-p_i}=s_{i+p_i}$ 就继续暴力扩展，最后再更新 $[pos,r]$。

Aho-Corasick 自动机

将 Trie 树建出失配边，便成为了 AC 自动机。用于多模式串匹配。

用于 dp 时和在其它自动机上 dp 是一致的：状态中记录当前在自动机的哪个结点。

注意在点 $u$ 时可以匹配上 fail 树上所有以 $u$ 祖先结束的串，所有 $fail_u$ 的贡献要继承到点 $u$ 上。

匹配的限制有时可以转化成”在子树内“，从而利用二维数点解决。

许多关于多模式串的询问可以平衡复杂度。

后缀数组

通过将一个字符串所有后缀按字典序从小到大排序，可以挖掘出很多关于”后缀的前缀“的信息，即子串信息。

定义 $sa_i$ 为排名为 $i$ 的后缀是哪个，$rk_i$ 为后缀 $i$ 的排名。

双关键字基数排序：

void build(){
    int *x = rk, *y = sav;
    for(int i = 1; i <= n; ++i) x[i] = s[i], ++buk[x[i]];
    for(int i = 1; i <= S; ++i) buk[i] += buk[i - 1];
    for(int i = n; i >= 1; --i) sa[buk[x[i]]--] = i;
    for(int k = 1; k <= n; k <<= 1){
        int p = 0;
        for(int i = n - k + 1; i <= n; ++i) y[++p] = i;
        for(int i = 1; i <= n; ++i) if(sa[i] > k) y[++p] = sa[i] - k;
        for(int i = 1; i <= S; ++i) buk[i] = 0;
        for(int i = 1; i <= n; ++i) ++buk[x[i]];
        for(int i = 1; i <= S; ++i) buk[i] += buk[i - 1];
        for(int i = n; i >= 1; --i) sa[buk[x[y[i]]]--] = y[i], y[i] = 0;
        std::swap(x, y);
        x[sa[1]] = p = 1;
        for(int i = 2; i <= n; ++i){
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);
        }
        if(p == n) break;
        S = p;
    }
}

排序后，我们可以处理出 height 数组 $h_i$ 表示 $\text{lcp}(sa_{i-1},sa_i)$，因为 $h_i\ge h_{i-1}-1$，所以直接暴力预处理复杂度为线性：

void getheight(){
    for(int i = 1, j, k = 0; i <= n; ++i){
        if(rk[i] == 1) continue;
        if(k) --k;
        j = sa[rk[i] - 1];
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
        h[rk[i]] = k;
    }
}

处理出 height 数组后，$\text{lcp}(i,j)(rk_i < rk_j)$ 等于 $x\in(rk_i,rk_j],\min\{h_x\}$。

后缀自动机

增量构造：

void extend(int c, int k){
    int p = lst, np = lst = ++idx;
    memset(ch[np], 0, sizeof ch[np]);
    len[np] = len[p] + 1, L[np] = R[np] = k;
    while(p && !ch[p][c]) ch[p][c] = np, p = par[p];
    if(!p) par[np] = 1;
    else{
        int q = ch[p][c];
        if(len[q] == len[p] + 1) par[np] = q;
        else{
            int nq = ++idx;
            L[nq] = 1e9, R[nq] = -1e9;
            memcpy(ch[nq], ch[q], sizeof ch[q]), len[nq] = len[p] + 1, par[nq] = par[q];
            par[np] = par[q] = nq;
            while(p && ch[p][c] == q) ch[p][c] = nq, p = par[p];
        }
    }
}

反串 parent 树是原串的后缀树。

parent 树上每个结点代表一个 endpos 集合等价类，$len$ 表示该等价类中最长串的长度。

通过 parent 树上线段树合并可以求出每个结点具体代表的 endpos 集合。

后缀树

后缀树是将字符串 $s$ 末尾加上一个占位符后将所有后缀依次插入 Trie 树中并缩链后得到的结构。

两个后缀的 $\text{lcp}$ 是它们在后缀树上 lca 的 $len$。

后缀树优秀的结构可以用来优化建图，或用数据结构维护树上信息。

VI. 图论

最短路

Floyd 可拓展性极强。可以将 Floyd 的转移过程理解为枚举 $k\in[1,n]$，从 $i$ 到 $j$ 只在中途经过 $[1,k]$ 的点时的最短路是多少。利用 Floyd 可以在 $\mathcal O(\frac{n^3}{w})$ 时间内求出一张图的传递闭包。

堆优化 Dijkstra 复杂度为 $\mathcal O((n+m)\log (n+m))$，在稠密图上表现不如朴素 $\mathcal O(n^2)$ 实现。

0/1 bfs：在边权只有 0 或 1 的图上，可以用 std::deque 代替堆，0 边放到队头、1 边放到队尾。

如果边权值域较小，可以开 $\mathcal O(v)$ 个栈来存当前最短路为 $[0,v]$ 的转移点，转移时从小到大扫值域。

当且仅当图有负权时使用 spfa。

以某个点开始到所有点求出最短路后可以建出相应的最短路树，即最优转移之间连边形成的以起点为根的树形结构。在这棵树上可以高效处理祖先-后代信息，还可以 dp。

次短路：转移最小值的时候同时记录次小值。

同余最短路：将余数视为点，从起点开始做 $d_{i+x\bmod p}=d_i+f(x)$ 的转移，最后 $d_i$ 中存储的就是 $\bmod p$ 意义下第一次达到余数 $i$ 的最小代价。

斯坦纳树：给定图中的一个点集，要求选出边权总和最小的边使得点集连通。直接状压。

差分约束

对于一个包含 $n$ 个变量 $x_1,x_2,\dots,x_n$ 以及 $m$ 个形如 $x_i-x_j\le k$ 的差分约束系统，我们将每个 $x_i$ 看作一个点，将限制写成 $x_i\le x_j+k$ 即最短路松弛的形式，从 $j$ 向 $i$ 连边权为 $k$ 的边。如果图中存在负环则无解，否则令 $d_1=0$ 得到每个点的 $d$ 就是一组合法解。

等于的限制可以转化成两个方向的小于等于限制。

大部分差分约束的题目最困难的部分在于转化为差分约束问题。当题目中有奇怪的判定要求时，可以尝试在其中挖掘出不等关系，从而通过差分约束解决。

路径计数

邻接矩阵的 $k$ 次方在 $(i,j)$ 位置的值 $A^k_{i,j}$ 等于从 $i$ 走到 $j$ 恰好走 $k$ 步的方案数。

图上不相交路径计数适用 LGV 引理。

图连通性相关

无向图连通性：并查集。

有向图弱连通：将有向边视为无向边后图连通。

有向图强连通：每个点都能通过图中的有向边到达其余的所有点。

tarjan 找到所有强连通分量：找到 dfs 树，看返祖边能到达的 dfs 序最靠前的点是哪个。

void tarjan(int x){
    dfn[x] = low[x] = ++tim;
    st[++tp] = x, vis[x] = 1;
    for(auto y : E[x]){
        if(!dfn[y]) tarjan(y), low[x] = std::min(low[x], low[y]);
        else if(vis[y]) low[x] = std::min(low[x], dfn[y]);
    }
    if(dfn[x] == low[x]){
        int u; ++scc;
        do{
            u = st[tp--];
            col[u] = scc;
            vis[u] = 0;
        }while(tp && u != x);
    }
}

点/边双连通分量：删掉其中任意一个点/一条边，图仍然连通。

割点的判断是 $\text{low}_v\ge \text{dfn}_u$，割边的判断是 $\text{low}_v > \text{dfn}_u$。

找割边：

void tarjan(int x, int f){
    dfn[x] = low[x] = ++tim, st[++tp] = x;
    for(int i = head[x]; i; i = e[i].u){
        int y = e[i].v;
        if(i == f) continue;
        if(!dfn[y]) tarjan(y, i ^ 1), low[x] = std::min(low[x], low[y]);
        else low[x] = std::min(low[x], dfn[y]);
    }
    if(dfn[x] == low[x]){
        int u; ++scc;
        do{
            u = st[tp--];
            col[u] = scc;
        }while(tp && u != x);
    }
}

圆方树：将每个点双中所有点（圆点）连向同一个方点，转化为树上问题解决。

竞赛图（有向完全图）缩点后是一条链，链上拓扑序靠前的点向所有拓扑序大于它的点连边。

2-SAT

要求若干个类似 $p\or q$ 的命题同时成立，判断是否存在方案/构造一组方案。

转化为图论模型，将 $n$ 个变量取真/假分别建点，共 $2n$ 个点。形如 $p\or q$ 的限制需要连 $(\neg p, q)$ 和 $(\neg q,p)$ 两条有向边，意义是如果算 $\neg p$ 则必须选 $q$，否则不合法。反之亦然。

最后判断 $p$ 与 $\neg p$ 是否在同一强连通分量中，如果在则无解（$p$ 不可能同时为真和为假），否则可以直接将强连通分量染色得到一组方案。

k-SAT 问题是 NP-Complete 的。

欧拉回路

判定（以下默认图连通）：

有向图存在欧拉回路当且仅当所有点入度等于出度，存在欧拉路径当且仅当恰好存在一个点入度比出度大 $1$，存在一个点出度比入度大 $1$，其余点入度等于出度。

无向图存在欧拉回路当且仅当所有点度数为偶数，存在欧拉路径当且仅当恰好存在两个点度数为奇数，其余点度数为偶数。

在判定合法的情况下输出方案：

对于每个点记录 $pos_u$ 表示下次到 $u$ 时应遍历点 $u$ 所有出边中第 $pos_u$ 条出边，直接 dfs 后将栈中的点倒序输出：

void dfs(int x){
    int siz = G[x].size();
    for(int i = pos[x]; i < siz; i = pos[x]) pos[x] = i + 1, dfs(G[x][i]);
    st[++top] = x;
}
void getpath(int S){
    dfs(S);
    while(top) printf("%d ", st[top--]);
}

无向图需要每条边只能从一个方向经过，因此要在走每条边之前判断其反边是否被走过。

注意：欧拉回路是经过图中每条边恰好一次后回到起点，有 $\mathcal O(n+m)$ 的判定与构造方法；但是哈密顿回路（经过图中每个点恰好一次后回到起点，不必经过所有边）是 NP-Complete 的，目前没有多项式复杂度的解法。

BEST 定理

设 $t_{G,k}$ 为有向图 $G$ 以 $k$ 为根的内向生成树个数（由于是欧拉图，任意两点为根的生成树个数均相等，所以此处 $k$ 可任取），则图 $G$ 的不去除循环同构的欧拉回路总数为

\[t_{G,k}\prod_{i=1}^n (\deg_i-1) \]

Dilworth 定理

最小链覆盖等于最长反链。对偶命题同样成立。

对于某个偏序关系，整个集合满足任选两个元素之间都存在该偏序关系，称之为“链”。同理，任两个元素间均不存在该偏序关系的集合被称为“反链”。将全集划分为最少的链，称为最小链覆盖。

弱/强偏序关系满足：自反性/非自反性、非对称性、传递性。

网络流

Dinic：先判断能否增广，如果能则多路增广。

费用流一般采用单路增广和多路增广的效率相当。

代码片段：

Dinic+当前弧优化：

bool bfs(){
    std::queue <int> q;
    memset(dep, 0, sizeof dep);
    dep[S] = 1, q.push(S), cur[S] = head[S];
    while(q.size()){
        int x = q.front(); q.pop();
        for(int i = head[x]; i; i = e[i].u){
            int y = e[i].v;
            if(!dep[y] && e[i].w){
                dep[y] = dep[x] + 1, cur[y] = head[y];
                q.push(y);
            }
        }
    }
    return dep[T];
}

int dfs(int x, int lim){
    if(x == T || !lim) return lim;
    int ret = 0;
    for(int i = cur[x], k; i && lim; i = e[i].u){
        int y = e[i].v;
        cur[x] = i;
        if(dep[y] == dep[x] + 1){
            k = dfs(y, std::min(lim, e[i].w));
            ret += k, lim -= k, e[i].w -= k, e[i ^ 1].w += k;
        }
    }
    return ret;
}

int dinic(){
    int mxflow = 0;
    while(bfs()) mxflow += dfs(S, INF);
    return mxflow; 
}

最小费用最大流：

bool spfa(){
    memset(dis, 0x3f, sizeof dis);
    memset(inq, 0, sizeof inq);
    std::queue <int> q;
    dis[S] = 0, q.push(S), fl[S] = INF, inq[S] = 1;
    while(q.size()){
        int x = q.front(); q.pop();
        inq[x] = 0;
        for(int i = head[x]; i; i = e[i].u){
            int y = e[i].v;
            if(dis[y] > dis[x] + e[i].c && e[i].w){
                dis[y] = dis[x] + e[i].c, fl[y] = std::min(fl[x], e[i].w), pre[y] = i;
                if(!inq[y]) inq[y] = 1, q.push(y);
            }
        }
    }
    return dis[T] != INF;
}
void upd(){
    for(int x = T, i; x != S; x = e[i ^ 1].v){
        i = pre[x];
        e[i].w -= fl[T], e[i ^ 1].w += fl[T];
    }
    mxflow += fl[T], mncost += fl[T] * dis[T];
}
ll MCMF(){
    while(spfa()) upd();
    return mncost;
}

一些常见模型：

二分图最大匹配：$S$ 到左部点，左部点到右部点，右部点到 $T$ 之间均连容量为 $1$ 的边。注意 Dinic 算法在二分图上的复杂度为 $\mathcal O(m\sqrt n)$。
最大权闭合子图：$S$ 向所有正权点连边权为 $a_i$ 的边，所有负权点向 $T$ 连边权为 $-a_i$ 的边，原图上的边边权为 $+\infty$。
“切糕”模型：有 $n$ 个整数变量 $x_i\in [1, m]$，$x_i$ 取 $j$ 的代价是 $w_{i.,j}$，同时有若干形如 $x_p\le x_q+k$ 的限制，要求给变量赋值并最小化总代价。先连 $n$ 条链 $S\rightarrow a_{i,1}\rightarrow\cdots\rightarrow a_{i,m+1}\rightarrow T$，其中 $a_{i,j}\rightarrow a_{i,j+1}$ 边权为 $w_{i,j}$；所有的 $a_{q,j+k}\rightarrow a_{p_j}$ 边权为 $+\infty$，这样不合法的方案必须割掉 $+\infty$ 的边。
二元关系限制：假设有两个物品 $x,y$，$x$ 放入 $A,B$ 集合的代价分别为 $a_1,b_1$，$y$ 放入 $A,B$ 集合的代价分别为 $a_2,b_2$，同时 $x$ 放入 $A$，$y$ 放入 $B$ 有 $c_1$ 额外代价，$x$ 放入 $B$，$y$ 放入 $A$ 有 $c_2$ 额外代价，求最小代价。连边 $(S,x,a_1),(S,y,a_2),(x,T,b_1),(y,T,b_2),(x,y,c_2),(y,x,c_1)$。

上下界网络流：

无源汇可行流：即要求每个点流量平衡。假设流量上下界为 $[l,r]$，先让原图每条边流 $l$，并在新图建 $(u,v,r-l)$ 的边，在新图上进行流量的调整。设 $d_i$ 为点 $i$ 初始流入流量与流出流量之差，若 $d>0$ 则添加 $(S',i,d)$，否则添加 $(i,T',-d)$。跑新图 $S'\rightarrow T'$ 的最大流，如果 $S'$ 的所有出边满流则存在可行流。
有源汇可行流：原图上连 $(T,S,[0,+\infty])$，转化为无源汇可行流。
有源汇最大流：先找到任意可行流，然后去掉 $S',T'$，再在残量网络上跑 $S\rightarrow T$ 的最大流。
有源汇最小流：先找到任意可行流，然后去掉 $S',T'$，再在残量网络上跑 $T\rightarrow S$ 的最大流。
有源汇最小/最大费用可行流：新图上 $(u,v,r-l)$ 的边继承原来的费用，其余所有边费用为零，建图同有源汇可行流。

最小割树：

任选两个点作为源汇求出它们的最小割，将这两个点间连树边边权等于最小割的值，然后取两边割集分治下去。注意每次跑任两个点之间最小割都是在原图上跑，而不是在分治的点集中跑。建出最小割树后两点之间的路径上的最小值即为这以两个点为源汇的最小割。

平面图对偶图

图 $G$ 能画在平面上除顶点外所有边两两不交，则 $G$ 是平面图。$K_5$（$5$ 个点的完全图）和 $K_{3,3}$（左右各 $3$ 个点的完全二分图）不是平面图。

$G$ 的边将 $G$ 所在平面划分成若干区域，简单来说，将每个区域视为一个点，如果两个区域被一条边分隔就在对偶图上连一条边。

平面图最小割可以转化为对偶图最短路。

VII. 杂项

xorhash/随机权值

一般在“集合中所有元素同时满足同一条件”（比如，所有某颜色的点均在链上出现）时使用。

为保证正确率一定要用 64 位整数。

模拟退火/随机化

构造题中，如果题目限制较松，可以尝试随机化+搜索求解方案。

多步操作后最优化的问题中，考虑使用模拟退火，即：如果当前状态优于目前最优答案则必然接受新答案，否则以 $\exp(\frac{-\Delta E}{t})$ 的概率接受当前状态。其中 $\Delta E$ 是当前状态得到的答案与目前最优答案之差，$t$ 是温度，开始时设为一个较大的值，逐步减小（也就是退火的名称由来）的过程中逐渐达到最优解。

一般来说有针对性的调整效果要明显优于整体打乱后重新随机。

莫队算法

用于离线处理多组静态区间询问。

将序列分为大小为 $B$ 的块，询问时指针移动次数是 $\mathcal O(\frac{n^2}{B}+mB)$，平衡复杂度得到 $\mathcal O(n\sqrt m)$。

区间询问本质上是二维空间中的指针移动；在更高维也是可以做的，比如加上修改（时间轴），假设每维大小同阶，可以得到 $ \mathcal O(n^{5/3})$ 的复杂度。

回滚莫队：将删除改为撤销。按左端点分块后右端点从小到大排序，询问右端点向右扫的过程中，询问左端点每次都从其所在块的右端点处开始往回扫。

Stern-Brocot Tree

将所有可能的分数放在树形结构上，从 $\frac{0}{1},\frac{1}{0}$ 开始（这里 $\frac{1}{0}$ 认为是正无穷），每次在相邻两个分数 $\frac{a}{b},\frac{c}{d}$ 之间插入一个分数 $\frac{a+b}{c+d}$，得到树的下一层。树上所有分数均为最简分数。

有理数二分可以在 Stern-Brocot Tree 上进行。Stern-Brocot Tree 上可以通过倍增快速找到需要的结点。

分数规划

给定序列 $a,b$，在一些限制下求 $\dfrac{\sum a_iw_i}{\sum b_iw_i}$ 的最值，其中 $w_i\in\{0,1\}$。

二分答案 $mid$ 转化为判定 $\max\sum w_i(a_i-b_i\cdot mid) \ge 0$。

带权二分（wqs 二分）

通过二分附加权值，调整直线的斜率来满足选择次数的限制，最大化/最小化截距。一般用来优化 dp（最后一维是选的个数，满足凸性，这时就可以忽略掉个数进行带权二分）。

注意函数必须是凸的才能用。

计算几何速查

直线：$Ax+By+C=0$，$y=kx+b$，用直线上一点和方向向量表示。

线段：记录两个端点。

正弦定理：$\dfrac{a}{\sin A}=\dfrac{b}{\sin B}=\dfrac{c}{\sin C}=2r$。

余弦定理：$c^2=a^2+b^2-2ab\cos C$。

绕原点随机旋转：$(x,y)\rightarrow (x\cos\theta-y\sin\theta,x\sin\theta+y\cos\theta)$。

向量叉积：$\mathbf{v}_1=(x_1,y_1),\mathbf{v}_2=(x_2,y_2),\mathbf{v}_1\times \mathbf{v}_2=x_1y_2-x_2y_1$。正负分别表示 $\mathbf{v}_2$ 在 $\mathbf{v}_1$ 的上方（逆时针）/下方（顺时针）。

任意多边形面积：将顶点按逆时针排序得到 $p_1,p_2,\dots,p_n$，任选辅助点 $O$，记 $\mathbf{v}_i=p_i-O$，则面积 $S=\dfrac{1}{2}\left |\sum\limits_{i=1}^n \mathbf{v}_i\times \mathbf{v}_{(i\bmod n)+1} \right |$。

判断点在多边形内：向外引一条射线，与边界相交奇数次则在多边形内，否则在多边形外。

极角排序：atan2(y, x) 返回原点到 $(x,y)$ 的方位角，范围 $(-\pi,\pi]$。

曼哈顿距离转切比雪夫距离：$(x,y)\rightarrow(x-y,x+y)$，相当于坐标旋转 45 度后放大。

闵可夫斯基和：两个点集 $A,B$，定义 $A,B$ 的闵可夫斯基和为 $A+B=\{a+b|a\in A,b\in B\}$。两凸包的边极角排序后直接顺次连起来就是它们闵可夫斯基和的凸包。

构造题思考方向

归纳构造，从小到大。

从简单但错误的构造方式开始，通过调整和修改出错的地方，逐步得到正确的解法。

从特殊情况、特殊性质开始考虑，然后再将一般情况归纳到该特殊情况。

分块构造，将诸多小块的构造结果进行拼接。

打表找规律。

VIII. 考前必读

对拍

生成数据时要从小到大，尝试不同的参数，生成边界情况。

朴素算法尽量少使用从题目中推导出的结论，简洁第一。

一定记得改动完代码之后编译。

用 mt19937_64 生成 64 位随机数：std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

Linux 下的对拍代码：

#include <bits/stdc++.h>

#define s system

int main(){
    /*
    s("g++ a.cpp -o a -std=c++14 -O2");
    s("g++ bf.cpp -o bf -std=c++14 -O2");
    s("g++ gen.cpp -o gen -std=c++14 -O2");
    是否需要编译视情况
    */
    int T = 0;
    while(++T){
        s("./gen > a.in");
        s("./a < a.in > a.out");
        s("./bf < a.in > a.ans");
        if(s("diff -w a.out a.ans")) return puts("Wrong Answer"), 0;
        else printf("%d\n", T);
    }
}

最后的一些考场提示

你需要牢记的事情。-Kubic

该开 long long 的时候一定要开。

要特别注意内存消耗。$10^6$ 个 std::deque 需要将近 700MB 的内存。 std::queue 和 std::stack 也是用 std::deque 实现的，因此必须同样注意。结构体会将空间预留到内部占用内存最大的变量类型的整数倍。考场上可以用 /usr/bin/time -f "%es, %MKB" ./a < a.in 来测试程序实际使用的空间。

double 只有 15 位精度，因此需要注意精度误差的叠加。同时，表示 $10^{18}+3$ 等数时，绝对不能写 1e18 + 3，而是要写 (long long)1e18 + 3。

如果不使用 namespace std，那么需要特别注意绝对值函数 abs 是 cmath 库中的绝对值函数，默认范围 int，std::abs 才是任意类型的绝对值函数。

如果使用 namespace std，要特别注意避开各种关键字和 algorithm 库中的函数名，包括但不限于 prev，next，find，copy，fill，merge，rotate，apply，binary_search 等等。

__builtin 函数默认类型是 32 位整数，如果需要更大范围的请使用 __builtin_popcountll __builtin_ctzll 等等。左右移超过 31 位时用 1ll。

考虑边界情况，注意细节，审清题目。例如 $n\le 3,a_i=0$、宏定义可以为空、两个红帅相邻之类。避免因漏判边界+多测挂掉题目的大部分分数。

多测要清空。最好用完之后再把用到的都清空。

代码需要卡常/重构的时候一定要保存一份原来的代码。

快读要读入负数，模板不要打错。

要具体问题具体分析，不要受可能做过的类似题目干扰，适当时候要对现有的模型进行创新性的转化与修改。开始写题之前重新整理一遍思路，模拟一下最小的样例，确认做法没有假再写。

合理分配时间，打满部分分，每个题都要分配时间。

最后祝大家 NOI 2023 一切顺利，超常发挥！

标签：std,知识点,NOI,int,sum,2023,mathcal,可以,dp
From： https://www.cnblogs.com/Ignotus/p/noi-2023-review.html

NOI 2023 考前知识点总复习

NOI 2023 考前知识点总复习

目录

I. 数据结构、树上问题

Hash Table

并查集

单调栈/笛卡尔树

树状数组

线段树

序列分治

扫描线/二维数点

平衡树

ODT

01-Trie

K-D Tree

链剖分

重链剖分

长链剖分

树的直径

树分治

树的重心

点分治/边分治

重构树

树哈希

Huffman 树

II. 数论

线性筛

整除分块

狄利克雷卷积

杜教筛

扩展欧几里得（exgcd）

扩展中国剩余定理

扩展欧拉定理

BSGS

原根

Miller-Rabin

III. 组合数学、计数相关

Lucas 定理

Kummer 定理

二项式反演

组合恒等式

斯特林数

Burnside 引理

无根树的 Prüfer 序列

常见数列

III-i. 线性代数与其它数学相关

拉格朗日插值

行列式

线性相关与线性无关

矩阵树定理

LGV 引理

IV. 动态规划（dp）

背包问题

区间 dp

树上 dp

状态压缩

数位 dp

动态 dp

常见 dp 优化

计数相关

V. 字符串

Hash

KMP 与 border 相关结论

Z 函数（扩展 KMP）

Manacher

Aho-Corasick 自动机

后缀数组

后缀自动机

后缀树

VI. 图论

最短路

差分约束

路径计数

图连通性相关

2-SAT

欧拉回路

BEST 定理

Dilworth 定理

网络流

平面图对偶图