零碎知识点整理
w9095
·
·
个人记录
前言
这里是我整理的零碎知识点，方便我以后复习。
持续更新。
图论
$1.2$ 在最小生成树中，最大的边是使图联通的最大边。
例题1-2-1：[P1991 无线通讯网](https://www.luogu.com.cn/problem/P1991)
**扩展**：在最小生成树中，第 $n$ 大的边是使图联通的第 $n$ 大的边。
例题1-2-2：[P4047 [JSOI2010]部落划分](https://www.luogu.com.cn/problem/P4047)
$1.3$ 在SPFA中，每个点最多入队 $n$ 次，可以用于判负环。
例题1-3：[P3385 【模板】负环](https://www.luogu.com.cn/problem/P3385)
$1.4$ 在有向图中，通过反向建边，可以把单源最短路转化成单终点最短路。
例题1-4：[P1821 [USACO07FEB] Cow Party S](https://www.luogu.com.cn/problem/P1821)
$1.5$ 在没有给定起点的图中，可以通过建立一个编号为 $0$ ，与其他所有点的单向连边权值为 $0$ 的“超级源点”解决图不连通的问题。
例题1-5：[P1993 小 K 的农场](https://www.luogu.com.cn/problem/P1993)
**代码**：
```cpp
for(int i=1;i<=n;i++)add_edge(0,i,0);
```
**扩展**：在差分约束系统中，在“超级源点”处开始跑最短路，可以得到各个点之间的差量。此时如果“超级源点”的每条出边边权增加相同数量，差分约束任然成立。
$1.6$ Floyd 算法中可以通过限定 $k$ 的枚举范围来限定只能通过一部分点来中转。这时需要注意枚举顺序。
例题 1-6：[P7516 [省选联考 2021 A/B 卷] 图函数](https://www.luogu.com.cn/problem/P7516)
$1.7$ 与环有关的问题可以通过拓扑序来解决，例如判断加入一条边后是否会形成环，只需要判断边上两点拓扑序的大小关系即可。
例题1-7：[CF1100E Andrew and Taxi](https://www.luogu.com.cn/problem/CF1100E)
$1.8$ 平面图定理：若 $G$ 是平面图，$n$ 为点数，$m$ 为边数，则 $m\le 3n-6$。
证明1-8：[平面图的基本概念及性质](https://www.cnblogs.com/lfri/p/9939463.html)
例题1-8：[P3209 [HNOI2010] 平面图判定](https://www.luogu.com.cn/problem/P3209)
### 树论
$2.1$ 树的多条直径一定交于一点。
$2.2$ 令 $dist(i,j)$ 为 $i$ 到 $j$ 的路径权值之和，$d[i]$ 为点 $i$ 到根节点的权值之和，则有：
$$dist(i,j)=d[i]+d[j]-2\times d[lca(i,j)]$$
例题2-2：[P2680 [NOIP2015 提高组] 运输计划](https://www.luogu.com.cn/problem/P2680)
$2.3$ 如果需要在图中使用 LCA，则需要将图转化为树。可以通过最小/大生成树将图转化为树。
例题 2-3：[P1967 [NOIP2013 提高组] 货车运输](https://www.luogu.com.cn/problem/P1967)
$2.4$ 如果需要在图中使用 LCA，则需要将图转化为树。可以通过支配树将图转化为树，注意此时 LCA 要在支配树上跑。
例题 2-4：[P2597 [ZJOI2012] 灾难](https://www.luogu.com.cn/problem/P2597)
**详细解释**：[题解 P2597 【[ZJOI2012]灾难】](https://llzzxx712.blog.luogu.org/solution-p2597)
$2.5$ 树上差分的方式：若修改操作 $i,j,c$ 为 $i$ 到 $j$ 的路径上的点权值加 $c$，则可以这样操作：（$f[i]$ 表示节点 $i$ 的父节点）
$$q[i]+=c,q[j]+=c,q[lca(i,j)]-=c,q[f[lca(i,j)]]-=c$$
最后将标记从叶节点上传累加即可。
例题 2-5：[P3258 [JLOI2014] 松鼠的新家](https://www.luogu.com.cn/problem/P3258)
**代码**：
```cpp
void query(int now)
{
for(int i=h[now];i;i=e[i].next)
if(e[i].v!=fa[now][0])
{
query(e[i].v);
q[now]+=q[e[i].v];
}
}
q[i]+=c,q[j]+=c,q[lca(i,j)]-=c,q[fa[lca(i,j)][0]]-=c;
```
$2.6$ 点 $d$ 是在路径 $i,j$ 上的条件：$d$ 是 $i$ 或 $j$ 的父节点，且 $lca(i,j)$ 是 $d$ 的父节点。
例题 2-6：[P3398 仓鼠找 sugar](https://www.luogu.com.cn/problem/P3398)
**代码**：
```cpp
bool judge(int x,int y)
{
if(dep[x]>dep[y])return 0;
int c=dep[y]-dep[x];
for(int i=0;i<30;i++)
if((1<<i)&c)y=fa[y][i];
if(x==y)return 1;
else return 0;
}
if(judge(lca(i,j),d)&&(judge(d,i)||judge(d,j)))printf("Y\n");
else printf("N\n");
```
$2.7$ 可以通过把查询 $x$ 是否为 $y$ 的祖先改为查询 $y$ 是否在 $x$ 的子树内，通过欧拉序快速查询。
例题 2-7：[CF466E Information Graph](https://www.luogu.com.cn/problem/CF466E)
### 数据结构
$3.1$ 区间操作的常用维护方法：线段树懒标记和差分数组。遇到线段树懒标记无法维护的问题时，要考虑转化为差分数组维护前缀和。
$3.2$ 异或满足前缀和与差分性质，所以可以使用树状数组维护区间异或和。
例题3-2：[P5556 圣剑护符](https://www.luogu.com.cn/problem/P5556)
$3.3$ 对于查询 $[l,r]$ 所有子区间信息的问题，我们考虑离线后把询问按照右端点升序排序，让 $r$ 从 $1$ 扫到 $n$，使用数据结构动态维护 $s[i]$ 表示 $i\sim r$ 的信息，维护历史版本信息回答询问。
例题3-3：[CF997E Good Subsegments](https://www.luogu.com.cn/problem/CF997E)
$3.4$ 01Trie 支持整体加 $1$ 操作：把整数从低位到高位插，交换左右儿子，在交换后的左儿子继续加 $1$ 表示进位。这可以使用懒标记维护。注意此时对 $2^k$ 取模，其中 $k$ 为插入的最高位。
**扩展**：01Trie 支持整体加 $v$ 操作：对于大于 $1$ 的标记 $v$，我们直接把 $\lfloor\frac{v}{2}\rfloor$ 推到下一位增加。如果 $v$ 是奇数，即还有一个加 $1$ 没有推下去，按照上面加 $1$ 的方法处理。
**代码**：
```cpp
void pushdown(long long x)
{
if(ad[x]&1)swap(trie[x][0],trie[x][1]),ad[trie[x][0]]++;
ad[trie[x][0]]+=(ad[x]>>1),ad[trie[x][1]]+=(ad[x]>>1),ad[x]=0;
}
```
例题 3-4：[P11160 【MX-X6-T6】機械生命体](https://www.luogu.com.cn/problem/P11160)
$3.5$ 对一棵子树进行操作时，如果不方便直接操作或打标记，可以直接把这棵子树分裂出来再合并。
$3.6$ LCT 维护边权的方法是对于每条边再开一个点，连接其两端的点。连边，断边操作改为每条边对应的点与其两端的点的连接或断开。
例题3-6：[P2387 [NOI2014] 魔法森林](https://www.luogu.com.cn/problem/P2387)
### 搜索
$4.1$ 对于需要高精度存储的数字，可以用 $\log$ 的性质和其质因数分解后的结果求出相对大小用于剪枝。
$\log(a)\lt\log(b)(a\lt b)
\log(a\times b)=\log(a)+\log(b)
\log(a^b)=b\times \log(a)
例题4-1：P1128 [HNOI2001] 求正整数
动态规划
例题5-1：[P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880)
**代码**：
```cpp
for(int i=1;i<=n;i++)
add_edge(0,i,0);
```
$5.2$ 记录方案的 DP 题目的处理方法：从最终状态往回逆推，对于每一个状态，记录逆推需要的数据。
例题5-2：[P7685 [CEOI2005] Mobile Service](https://www.luogu.com.cn/problem/P7685)
$5.3$ 区间 DP 简化思路的方法：一个区间内只解决这个区间能解决的问题，涉及其他区间的情况留给更大的区间解决。另外，区间 DP 枚举分界线时较为多样，既可以为单纯的分界线，也可以为特殊值，如最大或最小值。
**扩展**：DP 时一个子问题内只解决这个子问题能解决的问题，涉及其他子问题的情况留给更大的子问题解决。
例题5-3：[P3592 [POI2015] MYJ](https://www.luogu.com.cn/problem/P3592)
$5.4$ 向量($n\times1$ 或 $1\times n$ 的矩阵)和矩阵做矩阵乘法，时间复杂度仅为 $O(n^2)$，可以用来优化矩阵快速幂优化的动态规划。将快速幂二进制拆分预处理，即可每次乘以状态矩阵(是一个向量)。
例题5-4：[P6772 [NOI2020] 美食家](https://www.luogu.com.cn/problem/P6772)
**代码**：
```cpp
struct matrix mul(struct matrix a,struct matrix b)
{
struct matrix c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
c.a[i][j]=-1e18;
for(int k=1;k<=n;k++)
for(int j=1;j<=n;j++)
{
if(b.a[k][j]<0)continue;
for(int i=1;i<=n;i++)
c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);
}
return c;
}
q[0]=a;
for(int i=1;i<=30;i++)q[i]=mul(q[i-1],q[i-1]);
for(int j=30;j>=0;j--)
if((p>>j)&1)ans=mul(q[j],ans);
```
$5.5$ 可以通过 `for` 循环枚举子集，总时间复杂度为 $O(3^n)$。注意需要特判空集，这个循环便历不了空集。
证明5-5：[题解 P5911 【[POI2004]PRZ】](https://www.luogu.com.cn/article/wp2x9z26)(最后有一些显然易见的小问题，但不影响正确性)
例题5-5：[P5911 [POI2004] PRZ](https://www.luogu.com.cn/problem/P5911)
**代码**：
```cpp
for(int t=s&(s-1);t;t=(t-1)&s)
```
### 数学
$6.1$ 枚举 $n$ 的因数的过程有时可以优化到 $\log n$。如果可以只枚举这个数的质因数，那么先使用线性筛筛出每个数的最大质因数，然后每次除以最大质因数即可。期望复杂度 $O(\log n)$。
例题6-1：[P3538 [POI2012] OKR-A Horrible Poem](https://www.luogu.com.cn/problem/P3538)
**代码**：
```cpp
void linear(int mx)
{
a[1]=1;
for(int i=2;i<=mx;i++)
{
if(!a[i])pr[++cnt]=i,g[i]=i;
for(int j=1;j<=cnt&&i*pr[j]<=mx;j++)
{
a[i*pr[j]]=1,g[i*pr[j]]=pr[j];
if(i%pr[j]==0)break;
}
}
}
while(len>1)len/=g[len];
```
$6.2
d(ij)=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]
证明6-2：关于题目结论证明的想法
例题6-2：P3327 [SDOI2015] 约数个数和
例题6-3：[P4449 于神之怒加强版](https://www.luogu.com.cn/problem/P4449)
过程6-3：
$$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d]d^k$$
$6.4$ 记 $F_i$ 为斐波那契数列的第 $i$ 项，有 $\gcd(F_n,F_m)=F_{\gcd(n,m)}$。
证明6-4：[第一篇题解](https://www.luogu.com.cn/problem/solution/P1306)
例题6-4：[P1306 斐波那契公约数](https://www.luogu.com.cn/problem/P4449)
$6.5
\sum_{i=1}^ni[\gcd(n,i)=1]=\frac{\varphi(n)}{2}n
特别的，若 \varphi(n) 为奇数，则改为 \frac{\varphi(n)+1}{2}n。
证明6-5：考虑 \gcd 的性质，若 \gcd(n,i)=1，则有 \gcd(n,n-i)=1。因此，满足 \gcd(n,i)=1 的数成对出现，且和为 i+n-i=n。若 \varphi(n) 为奇数，进行特判即可。
证明6-5：P1891 疯狂 LCM
杂项
$7.2$ 将一个无序序列排成有序所需要的最小交换次数就是该无序序列中的逆序对数。
证明7-2：[题解 P1774 【最接近神的人】](https://www.luogu.com.cn/blog/leolrg/solution-p1774)
例题7-2：[P1774 最接近神的人](https://www.luogu.com.cn/problem/P1774)
$7.3$ 异或(以及其余位运算)和之和的快速求法：对于每一个数位，求出有多少种方式可以使这一位为 $1$，然后计算贡献。
例题7-3：[P9236 [蓝桥杯 2023 省 A] 异或和之和](https://www.luogu.com.cn/problem/P9236)
$7.4$ 与中位数问题一般通过二分解决，在一次二分中，把大于二分中值的数标记为 $1$，小于二分中值的数标记为 $-1$，这样有一些神奇的性质，可以方便做题。
例题 7-4：[P2839 [国家集训队] middle](https://www.luogu.com.cn/problem/P2839)
$7.5$ 与两个状态互相转化有关的题目，可以考虑把两个状态转化为一个相同的中间状态。
例题 7-5：[CF512E Fox And Polygon](https://www.luogu.com.cn/problem/CF512E)
$7.6$：若 $a\le b\le c$，则有 $\min\{a\oplus b,b\oplus c\}\le a\oplus c$。(还不知道有什么用)