Algo

 

数学基础运算快速冥/乘高精度加 减 乘 除 模 幂 python高精数学运算sqrtlog除法取整分式运算BigInt初等数论约数公约数最大公约数扩展欧几里得最小公倍数分解只因数筛法求质因数Pollard_Rho约数个数约数之和素数Miller-Rabin素数筛威尔逊定理欧拉函数欧拉筛欧拉定理拓展欧拉定理 (欧拉降幂)模数同余定理线性同余高次同余乘法逆元中国剩余定理数论分块其它组合数学排列组合 杨辉三角逆元求组合数卢卡斯定理高精度排列组合错位排列容斥原理数列等差/等比数列递推斐波那契广义斐波那契数列皮萨诺周期卡特兰数贝尔数 (集合划分)康托展开 (全排列排名)线性代数矩阵矩阵快速幂矩阵封装行列式线性基概率论期望方差数值算法数值积分高斯消元插值博弈论Nim游戏SG函数计算几何距离扫描线面积并周长并二维数点平面几何点线封装其它中位数对顶堆主席树均值不等式约瑟夫环吉姆拉尔森日期公式二维和一维坐标转化基础算法前缀和&差分一维前缀和二维前缀和一维差分二维差分二分二分查找二分答案实数域二分分数规划子段和问题三分双指针排序sort快速排序第k小的数归并排序逆序对分治二进制lowbit状态压缩位运算^ 异或& 与>> 移位离散化搜索DFS剪枝迭代加深BFS双端队列BFS优先队列BFS双向搜索A*IDA*Dancing Links精确覆盖重复覆盖倍增ST表根号分治数据结构基本数据结构链表单链表双链表表达式计算单调栈队列单调队列滑动窗口最大子段和二叉堆左偏树配对堆哈希开放寻址法拉链法并查集边带权并查集拓展域并查集分块树状数组一维树状数组权值树状数组静态区间颜色数线段树单点修改,区间查询区间修改,区间查询,lazy标记权值线段树霍夫曼树字符串字符串哈希双哈希KMP前缀统计循环节最长公共子串exKMPTrie字典树字符串统计前缀统计最大异或对AC自动机回文串Manacher最小表示法后缀数组排序+哈希+二分倍增实现height数组其它图论树和图的存储邻接矩阵邻接表树和图的遍历DFSDFS序列连通块划分BFS拓扑排序最短路单源最短路仅正权边Dijkstra朴素Dijkstra堆优化含负权边Bellman-FordSPFA多源最短路Floyd传递闭包Johnson(LCA)树上问题树的重心树的中心树的直径最近公共祖先树上差分树哈希生成树最小生成树KruskalPrim朴素Boruvka唯一性次小生成树生成树计数最小树形图二分图二分图判定最大匹配匈牙利算法HK 算法转为网络流模型常见问题模型最大权匹配KM算法转为费用流模型最小点覆盖最大独立集最小路径覆盖一般图最大匹配一般图最大权匹配基环树负环SPFA判负环bellman-ford判负环差分约束连通性相关割点和割边双连通分量边双连通分量点双连通分量强连通分量2-SAT网络流最大流Edmondsd-KarpDinic最小割最大权闭合图费用流欧拉图动态规划背包问题01背包完全背包多重背包分组背包二维费用背包求具体方案求方案数有依赖的背包问题线性DP数字三角形最长上升子序列最长公共子序列编辑距离区间DP一维二维计数DP数位DP记忆化搜索试填法状压DPbitset优化重复覆盖问题树形DP树上背包换根DP记忆化搜索DP优化单调队列优化数据结构优化斜率优化其他环形处理滚动数组状态机DP贪心区间问题区间选点区间合并不相交区间区间覆盖区间分组区间包含绝对值不等式排序不等式后悔解法其它字符与数字转换进制转换精度/溢出问题输入输出优化交互题一些语法/标准重载运算符Lambda表达式预编译头文件gcc标准__int128__cplusplus文件读写时间复杂度握手定理分块打表随机数生成.vimrcOI

 

待填坑: 数学:莫比乌斯反演、多项式与生成函数、快速傅里叶变换、快速数论变换、计算几何、原根、Pick定理、线性基、母函数、 基础算法:莫队、倍增、 字符串:exKMP、AC自动机、后缀自动机、可持久化Trie、回文树、 图论:树链剖分、基环树、树分治、圆方树、 数据结构:主席树、平衡树、笛卡尔树、动态树、可持久化数据结构、 动态规划:计数DP、插头DP、期望/概率DP、

数学

 

基础运算

快速冥/乘

 

nk的前三位数

nk=10klgn=10klgn×10klgnklgn 前半部分为整数次幂,后半部分为小数次幂。nk=×10 ,例如220=1.048576×106 我们只需要取小数次幂的三位(乘100再取整即可)

 

 

高精度

大整数在线计算工具 (gptkong.com)

//按住ctrl点击跳转

 

 

image-20231118143232446

 

 

 

 

image-20231118151225445

 

 

 

给两个正整数a,b,输出他们的最大公约数 a<=1e10^6,b <= 1e9

首先有以下性质 1.(a+b)%mod等价于a%mod+b%mod 2.a * b%mod 等价于 a%mod*b%mod(仅当a * b没有溢出时) 该题求解gcd(a,b)a是大数 根据辗转相除法 gcd(a,b)=gcd(b,a%b) 因此我们可以先求a%b把a限制在1e9的范围内,然后做gcd 因为a很大,又可以表示为i=1nai10ni(其中n为字符串的长度,ai为第i个字符) 又由性质1和2,我们就可以对每个ai求mod,同时通过乘和累加求出

 

 

 

 

python高精

 

数学运算

 

sqrt

 

 

log

 

 

除法取整

 

分式运算

源自jiangly分数四则运算 博客园 (cnblogs.com)

Frac a(1,3); 表示13 ,支持分式之间 + - * / 和比较大小

 

 

 

BigInt

 

高精度整数运算,不支持负数运算(待完善),写得一坨,勉强能用只能说是==

操作A op b (高精度op低精度)A op B (高精度op高精度)
加法++=++=
减法(仅限大op小)--=--=
乘法**=**= (O(N*M)模拟),不推荐,建议换FFT)
除法(下取整)//= 
取模%%= 
比较大小> < == != >= <=> < == != >= <=

允许直接A/B、A%B 但需要保证B在整型范围内(B <= 9.2e17)

初始化

 

 

 

初等数论

 

常见符号

  1. 整除符号:xy,表示 x 整除 y,即 xy 的因数。

  2. 取模符号:xmody,表示 x 除以 y 得到的余数。

  3. 互质符号:xy,表示 xy 互质。

  4. 最大公约数:gcd(x,y),在无混淆意义的时侯可以写作 (x,y)

  5. 最小公倍数:lcm(x,y),在无混淆意义的时侯可以写作 [x,y]

 

约数

平凡约数(平凡因数):对于整数 b0±1±bb 的平凡约数。当 b=±1 时,b 只有两个平凡约数。

对于整数 b0b 的其他约数称为真约数(真因数、非平凡约数、非平凡因数)。

 

公约数

求一个数g的所有约数,或两个数x,y的所有公约数 f(30) = {1 2 3 5 6 10 15 30} f(30,5) = {1,5}

 

最大公约数

AcWing 872. 六种方法求最大公约数及其时间复杂度分析 - AcWing

[欧几里得算法][辗转相除法]求最大公约数

 

相邻的两个数gcd(n,n-1) = 1

GCD(a1,a2,a3,,an)=GCD(s1,s2,s3,,sn) 其中s[ ]为a[ ]的前缀和数组(或者差分数组)

 

 

扩展欧几里得

求解形如 ax+by=c 的通解(有解的充要条件: c % gcd(a , b) == 0

裴蜀定理:对于任意整数a,b,一定存在一对整数x,y,满足:ax + by = gcd(a,b)

设d = gcd(a,b)

设x,y为当前层的一组解 ,x1,y1为下一层的一组解

当前层方程为 ax+by=d

下一层方程为 bx1+(a%b)y1=d bx1+(a(a/b)b)y1=d ay1+b(x1a/by1)=d

联立当前层与下一层,则可得到当前层的解x,y,与下一层方程解x1,y1的关系 ax+by=ay1+b(x1a/by1)

下层往上回溯时用下一层的解x1,y1更新当前层的解x,y x=y1y=x1a/by1

ax+by=gcd(a,b)的特解、通解、最小正整数解,x0,y0d=exgcd(a,b,x,y)的一组解 特解x=x0y=y0 ,诺b0,那么必有|x0|b,|y0|a 通解x=x0+bdky=y0adkkZ,由此可知x,y的增减性相反 x的最小非负整数解x=(x0%|bd|+|bd|)%|bd|

ax+by=c的特解、通解、最小正整数解(诺c%gcd(a,b) != 0 则无解)令 x0,y0d=exgcd(a,b,x,y)的一组解 特解x=x0cd,y=y0cd 通解x=x0cd+bdk,y=y0cdadk,kZ x的最小非负整数解x=x0cd%|bd|+|bd|)%|bd|

 

类似的,多元线性丢番图a1x1+a2x2++anxn=c有整数解,当且仅当d=gcd(a1,a2an)整除c。

 

 

最小公倍数

重要推论:gcd(a,b) * lcm(a,b) = a*b

 

 

分解只因数

每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数

如:12=2231

试除法

时间复杂度 O(N)

fac(12) = {(2,2),(3,1)}

 

约数分解

fac(12) = {1,2,3,4,6,12}

 

筛法求质因数

O(N) 预处理,O(p(x)) 查询,p(x)x的因数个数

primes[]存1~N的所有素数,0_idx minp[x]为x的最小质因子 maxp[x]为x的最大质因子,诺maxp[x] == x则x为质数

 

Pollard_Rho

泼辣的肉,期望时间复杂度为 O(p)=O(N14)

 

约数个数

如果N = p1c1p2c2...pkck

约数个数 = (c1+1)(c2+1)...(ck+1)=i=1k(ci+1) 约数之和 = (p10+p11+...p1c1)...(pk0+pk1+...pkck)=i=1k(j=0cipij)

 

 

 

约数之和

如果N = p1c1p2c2...pkck

约数个数 = (c1+1)(c2+1)...(ck+1)=i=1k(ci+1) 约数之和 = (p10+p11+...p1c1)...(pk0+pk1+...pkck)=i=1k(j=0cipij)

 

求a^b约数之和%mod,0 <= a,b <= 5e7

实现一个sum函数,sum(p, k)表示p0+p1++pk1

方法一O(k):递推求p^0 + p^1 + ... + p^k

方法二O(logK):递归求 k为偶数时sum(p,k) => p0+p1+...+pk21+pk2+pk2+1+...+pk1 =>p0+p1+...+pk21+pk2(p0+p1+...+pk21) =>sum(p,k2) + pk2sum(p,k2) =>(pk2+1)sum(p,k2) 当k为奇数时,为了更方便调用我们写的偶数项情况,可以单独拿出最后一项,把剩下的项转化为求偶数项的情况来考虑,再加上最后一项,就是奇数项的情况了,也即sum(p,k1)+pk1

方法三(OlogK):等比求和公式 sum=p0+p1+p2+...+pk ------① sump=p1+p2+p3...+pk+1 ------② ②-①化简得sum = pk+11p1 ,利用快速幂求逆元求解

 

素数

素数的判断方法总结

试除法

时间复杂度O(x)

 

 

Miller-Rabin

快速判断一个数 x 是不是素数,时间复杂度大概为 log(x)log2(x)

 

素数筛

O(N) 预处理, O(1) 查询

 

[l,r]之间的所有质数 1lr<231      rl<=1e6

 

 

威尔逊定理

对于素数p > 1,(p1)!1 (mod p)是 p 为素数的充分必要条件。

(p1)!p1(mod p)1 (mod p)

 

 

欧拉函数

ϕ(𝑁)表示1~N中与N互质的数的个数

诺将N分解质因数:N = p1a1p2a2p3a3...pkak 则欧拉函数计算公式ϕ(𝑁) = N·p11p1·p21p2·p31p3...pk1pk

 

 

欧拉筛

 

欧拉定理

诺正整数a与n互质,则aϕ(n)1(mod n)

欧拉定理推论

诺正整数a与n互质,对于任意正整数b,有abab%ϕ(n)(mod n) 面对乘方算式对质数p取模,可以先把,可以先把底数对p取模、指数对ϕ(p)取模再计算乘方

诺正整数a与n互质,则满足ax1(mod n)的最小正整数x0phi(n)的约数。

d|nϕ(d)=n (n为正整数)

 

i=1nj=1ngcd(i,j)

在结论n=d|nφ(d)中代入n=gcd(a,b),则有gcd(a,b)=d|gcd(a,b)φ(d)=d[d|a][d|b]φ(d)

其中,[] 称为 Iverson 括号,只有当命题 P 为真时 [P] 取值为 1,否则取 0。对上式求和,就可以得到

i=1ngcd(i,n)=di=1n[d|i][d|n]φ(d)=dnd[d|n]φ(d)=d|nndφ(d).

这里关键的观察是 i=1n[d|i]=nd,即在 1n 之间能够被 d 整除的 i 的个数是 nd

利用这个式子,就可以遍历约数求和了。需要多组查询的时候,可以预处理欧拉函数的前缀和,利用数论分块查询。

仿照上文的推导,可以得出

i=1nj=1ngcd(i,j)=d=1nnd2φ(d).

 

 

拓展欧拉定理 (欧拉降幂)

ab{abmodφ(m),gcd(a,m)=1,ab,gcd(a,m)1,b<φ(m),a(bmodφ(m))+φ(m),gcd(a,m)1,bφ(m).(modm)

 

第一个要求a和m互质,第二个和第三个是广义欧拉降幂,不要求a和m互质,但要求b和phi(m)的大小关系。

 

P5091 【模板】扩展欧拉定理 - 洛谷 (luogu.com.cn)

aB%m

 

P4139 上帝与集合的正确用法 - 洛谷 (luogu.com.cn)

给定 p,求2222...%p

a0=1,an=2an1,可以证明bn=an mod p在某一项后都是同一个值,求这个值。

[P10414 蓝桥杯 2023 国 A] 2023 次方 - 洛谷 (luogu.com.cn)

234...2023%2023

 

模数

a%b 也可以表示为 aabb

c++取模运算中 -7%4 = -3 而数学取模中 -7 % 4 = 4 题目往往要求数学取模

 

运算法则

模运算与基本四则运算有些相似,但是[除法例外][详见:乘法逆元]。其规则如下: (a + b) % p = (a % p + b % p) % p (a - b) % p = (a % p - b % p ) % p (a * b) % p = (a % p * b % p) % p (a * b * c)%p=(a%p * b%p * c%p) % p (a ^ b) % p = ((a % p) ^ b) % p

 

同余定理

同余定理:给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,那么就称整数a与b对模m同余,ab0(mod m),记作ab(mod m)。对模m同余是整数的一个等价关系。

 

若数组a[ ]的所有元素对 m 取余相同,则任意两个元素的差都能被 m 整除。m 必须是区间内所有元素两两差值的最大公约数 GCD。即m=GCD(al+1al,al+2al+1,...,arar1)https://codeforces.com/contest/2050/problem/F

 

 

线性同余

扩展欧几里得算法求线性同余方程axb (mod m),因为未知数x的指数为1,所以称作线性同余或一次同余。

给定a,b,m,求出x使得axb (mod m),如果无解则输出impossible。

问题等价于axbm的倍数,假设为y倍,则问题可转化为ax+my=b求解x

 

 

高次同余

BSGS

求解axb(mod p)的最小非负整数解x(或返回无解),其中a,p互质2a,b<p<231

BSGS(baby-step giant-step,大步小步算法)常用于求解离散对数问题,该算法可以在O(N) 的时间内求解(用map则多一个log)。

 

扩展BSGS

求解axb(mod p)的最小非负整数解x(或返回无解),其中a,p不一定互质1a,b,p109a=b=p=0

 

 

乘法逆元

费马小定理:对于任何一个整数a,以及素数p: 1.如果a是p的倍数,apa(mod p) 2.如果a不是p的倍数,ap11(mod p)

将上述公式2变形得到: aap21(mod p) ap2a1(mod p) 所以:a1ap2(mod p) 其中a和p互质(有逆元的充要条件) ab%p=abp2%p=a%pbp2%p

 

1ab%mod=qmi(a,mod2)qmi(b,mod2)%mod

 

 

中国剩余定理

 

 

扩展中国剩余定理(EXCRT):模数不互质

{xm1(moda1)xm2(moda2)xmn(modan)

给定 a[1~n] 和 m[1~n],求一个最小的非负整数 𝑥,满足∀𝑖∈[1,𝑛],𝑥 ≡ 𝑚𝑖(𝑚𝑜𝑑 𝑎𝑖)。 输出最小非负整数解 𝑥,如果 𝑥 不存在,则输出 −1。a1,0m<a,ai之间可以不互质

选第一个式子和第二个式子有: xm1(mod a1)xm2(mod a2) x=k1a1+m1x=k2a2+m2 //即求最小非负整数k1 k1a1+m1=k2a2+m2 k1a1k2a2=m2m1 ----------------①

令d = exgcd(a1,-a2),解为k1,k2 如果m2-m1不能整除d则无解,返回-1 否则一对整数解为k1=(m2m1)/dk1k2=(m2m1)/dk2

对于①式又有性质k1=(k1+ka2d)k2=(k2+ka1d) k1最小非负整数解为k1=k1%|a2d| //不确定d的正负,取绝对值

x=(k1+ka2d)a1+m1 x=k1a1+m1+ka1a2d x=k1a1+m1+klcm(a1,a2) m0=k1a1+m1a0=lcm(a1a2) x=ka0+m0 //再用此式子与其它式子依次递推,x=m即为当前x最小正整数解

 

 

P4777 【模板】扩展中国剩余定理(EXCRT)

给定 n 组非负整数 ai,bi ,求解关于 x 的方程组的最小非负整数解。

{xb1(moda1)xb2(moda2)xbn(modan)

时间复杂度O(N)

 

 

数论分块

快速求解形如i=1nf(i)g(ni) 的和式。当可以在O(1)内计算f(r)f(l)或已经预处理出f的前缀和时,数论分块就可以在O(N)的时间内计算上述和式的值。

 

[P2261 CQOI2007] 余数求和 - 洛谷 (luogu.com.cn)

给定n,k,求i=1nk%i

=i=1n(kiki)=nki=1n(iki)

例如样例 n = 10,k = 5

i12345678910
t=ki5211100000

发现ki分别在一定的区域内相等。 左端点l从1开始枚举,令t=kl,则数值t所在的右端点r=kt,在区间[l,r]t的值相等,于是我们可以快速求出这一段区间的取值,再让l=r+1

 

其它

一些数学常数

圆周率: π = acos(-1) = 3.14159265358979323846264338327950288419716939937510

自然常数: e = 2.7182818284590452353602874713526624977572470936999595749

 

⑨的倍数

如果一个数能整除9,那么它的所有位数之和也能整除9

 

x个k连在一起组成的正整数

可以表示为 k(10x1)9 ,如x = 6,k = 8,f(x,k) = 888888

 

一堆正整数相乘后,末尾0的个数

cnt2统计所有乘数中质因数2的个数 cnt5统计所有乘数中质因数5的个数 则末尾0的个数 =min(cnt2,cnt5)

 

 

组合数学

 

排列组合

排列(nPr):Anm=n!(nm)!=n(n1)(n2)...(nm+1)m

组合(nCr):Cnm=Anmm!=n!m!(nm)!

A[7,3] = 7 * 6 * 5 = 210 C[7,3] = (7 * 6 * 5)/(3 * 2 * 1) = 6

性质

Cnm=Cn1m1+Cn1m

Cn0+Cn1+...+Cnn=2n

Cnm=Cnnm

组合数判定奇偶:对于C(n,m),诺 n&m==m 则为奇数,否则为偶数。

 

多重集

多重集是指包含重复元素的广义集合,设 S = {n1a1,n2a2,...,nkak}

S的全排列个数A=n!n1!n2!···nk!

从S中选 r (r<=nk)个元素组成一个多重集,产生的不同多重集的数量为Ck+r1k1

 

 

二项式定理

(a+b)n=k=0nCnkakbnk

 

一些常见的组合计数

n*m的网格从左上角(1,1)走到右下角(n,m),每次只能往下或右走,不同的路径的总数Cn+m2n1Cn+m2m1

需要的总步数为n+m-2,其中向下走n-1步,向右走m-1步,不同的路径总共有Cn+m2n1Cn+m2m1种。

 

n个相同的物品分成m组,每组至少1个元素的方案数:Cn1m1

考虑拿m-1个板子插到n个元素形成的n-1个空里面,将物品分成m组。答案就是Cn1m1 本质是求x1+x2+...+xm=n的正整数解的组数。其中xi1

 

n个相同的物品分成m组,每组可以有0个元素的方案数:Cn+m1nCn+m1m1

显然此时没法直接插板了,因为可能出现很多块板子插到同一个空里面,不好计算。 先借m个元素过来,在这n+m个形成的n+m-1个空里面插入m-1个板子,方案数为Cn+m1nCn+m1m1 开头借了m个元素用于保证每组至少有一个元素,插完板后将借来的m个元素删除,因为元素是相同的,所以转化过的情况和转化前的情况可以一一对应,答案也就是相等的。 也相当于是求多重集{n个物品,m-1个板子}的全排列数。

本质是求x1+x2+...+xm=n的非负整数解的组数。其中xi0

 

n个物品分成m组,要求对于第i组,至少要分到ai个元素(ain),方案数为Cnai+m1nai

类比上一个问题,我们借ai个元素过来,保证第i组至少能分到ai个,也就是令x=xiai 得到新方程:

(x1+a1)+(x2+a2)++(xk+ak)=nx1+x2++xk=na1a2akx1+x2++xk=nai

其中xi0。然后就转化为了上一个问题,直接用插板法公式得到答案为Cnai+m1nai

本质是求x1+x2+...+xm=n的解的数目,其中xiai

 

从1~n的自然数中选m个,且这m个数中任意两个数差值大于k的方案有Cnk(m1)m种。(其中nk(m1)m,否则为0种。)

例题:Don't be too close(★6) - AtCoder typical90_o - (vjudge.net)

 

 

 

杨辉三角

O(N2) 预处理 O(1)询问

Cnm=Cn1m1+Cn1m

 

逆元求组合数

O(N)预处理 O(1)询问

Cnm=n!m!(nm)! %P=n!(m!P2)(nm)!P2 %P

 

 

卢卡斯定理

MN1018P105,其中P为质数

O(P logN logP)询问

CnmCn/pm/pCn%pm%p(mod p)

 

高精度排列组合

n,m5000

阶乘质因数分解+高精度乘法

博客:阶乘(n!)的素因数分解_正整数 (sohu.com)

算术基本定理:任意一个大于1的正整数n,它都可以分解为以下形式,其中p为质数,a为正整数 n=P1a1P2a2...Pkak m=P1b1P2b2...Pkbk nm=P1c1P2c2...Pkck 其中P[]为n以内的所有素数

Cnm=n!m!(nm)!=piaibici

 

 

 

 

 

错位排列

没有任何元素出现在原有位置的排列。即,对于1~n的排列P,如果满足Pii,则称P是n的错位排列。 如三元错位排列有:{2,3,1}{3,1,2}

递推关系式:

Dn=(n1)(Dn1+Dn2)=n(Dn1+(1)n)

 

其它关系:

错位排列数有一个简单的取整表达式,增长速度与阶乘仅相差常数:Dn={n!e,nn!e,n

随着元素数量的增加,形成错位排列的概率 P 接近:P=limnDnn!=1e

 

 

容斥原理

|ABC|=|A|+|B|+|C||AB||BC||CA|+|ABC|

容斥原理 - venn 图示例 把上述问题推广到一般情况,就是我们熟知的容斥原理

把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复

|i=1nSi|=i|Si|i<j|SiSj|+i<j<k|SiSjSk|+(1)m1ai<ai+1|i=1mSai|++(1)n1|S1Sn|

|i=1nSi|=m=1n(1)m1ai<ai+1|i=1mSai|

 

 

 

数列

 

等差/等比

等差数列

通项公式:an=a1+(n1)d

求和公式:Sn=(a1+an)n2

 

等比数列

通项公式:an=a1qn1

求和公式:{Sn=a1(qn1)q1 (q !=1)Sn=na1(q== 1)

诺无法求逆元可以考虑递归:S(k)={A  k=1S(k1)+Ak kS(k/2)+S(k/2)Ak2k

 

 

x=1nx=n(n+1)2
x=1nx2=n(n+1)(2n+1)6
x=1nx3=(x=1nx)2=(n(n+1)2)2

 

数列递推

求解递推数列 an=an1+kn+b 的第 n 项(其中 k,b 为常数)

an=a1+i=2n(ki+b)=a1+ki=2ni+bi=21

其中 i=2ni=n(n+1)21i=2n1=n1

代入求和得an=k2n2+(b+k2)n+(a1bk)

 

 

 

斐波那契

斐波那契数列相关 - zhoukangyang - 博客园 (cnblogs.com)

f(0) = 0,f(1) = 1,f(n) = f(n-2)+f(n-1)

0 1 1 2 3 5 8 13 21 ....

 

快速倍增法

O(logN) 询问 比矩阵乘法常数更小,返回值为pair<Fib(n),Fib(n+1)>;

F2k=Fk(2Fk+1Fk) F2k+1=Fk+12+Fk2

 

一些性质

  1. 卡西尼性质:Fn1Fn+1Fn2=(1)n

  2. 附加性质:Fn+k=FkFn+1+Fk1Fn

  3. 取上一条性质中 k=n,我们得到 F2n=Fn(Fn+1+Fn1)

  4. 由上一条性质可以归纳证明,kN,Fn|Fnk

  5. 上述性质可逆,即 Fa|Fb,a|b

  6. GCD 性质:GCD(Fn,Fm)=FGCD(n,m)

 

 

广义斐波那契数列

O(logN)询问

例:求 f(n)=pf(n1)+qf(n2)

可以得到矩阵公式: [f(n)f(n1)]=[f(n1)f(n2)]×[p1q0]

ans=[f(2)f(1)00]

base=[p1q0]

利用矩阵快速幂求 ansbasen2,对于n <= 2的情况,直接输出答案即可(因为第一次相乘即得到F[3],所以是n-2次方)

有关base转移矩阵的构造:F[N]=pF[n1]+qF[n2]F[N1]=1F[N1]+0F[N2] 实际是转为了二维:F[i][0]=F[i1][0]p+F[i1][1]qF[i][1]=F[i1][0]1

 F[n]F[n-1]
F[n-1]p1
F[n-2]q0

 

 

 

皮萨诺周期

模p意义下的斐波那契数列最下正周期被称为皮萨诺周期。 皮萨诺周期总是不超过6p,且只有在p=25k形式下才取得等号

当需要计算第 n 项斐波那契数模 m 的值的时候,如果 n 非常大,就需要计算斐波那契数模 m 的周期。当然,只需要计算周期,不一定是最小正周期。

如果 ab 互素,ab 的皮萨诺周期就是 a 的皮萨诺周期与 b 的皮萨诺周期的最小公倍数

 

 

 

 

 

 

卡特兰数

组合数学中一个常出现在各种计数问题中出现的数列

卡特兰数(Catalan)公式、证明、代码、典例._卡特兰数公式

1,1,2,5,14,42,132,429...(从第0项开始)

通项公式:h(n)=1n+1C2nn

递推公式:h[0]=1h[i]=2(2i1)i+1h[i1]

例:n对括号有多少种匹配方式?(诺有k种括号,则答案为h(n)kn) 求n个节点能够构成的不同的二叉树的个数? 一个栈的进栈序列为1,2,3,…,n有多少个不同的出栈序列? 给出一个n,要求一个长度为2n的01序列,使得序列的任意前缀中1的个数不少于0的个数, 有多少个不同的01序列?

 

 

 

贝尔数 (集合划分)

B0=1,B1=1,B2=2,B3=5,B4=15,B5=52,B6=203,

Bn 是基数为 n 的集合的划分方法的数目。集合 S 的一个划分是定义为 S 的两两不相交的非空子集的族,它们的并是 S。例如 B3=5 因为 3 个元素的集合 a,b,c 有 5 种不同的划分方法:

{{a},{b},{c}}{{a},{b,c}}{{b},{a,c}}{{c},{a,b}}{{a,b,c}}

 

 

康托展开 (全排列排名)

康托展开:给定一个长度为N的全排列a[ ],求它是第几个排列。 逆康托展开:给点一个全排列的长度N,求第rk个排列是什么?

重要柿子:rk=i=1nS(i)(ni)!

S(i)表示1 ~ a[i]-1中未出现过的数的个数,它可以看作是一种特殊的进制,也叫做阶乘进制。 如:(463)10=(341010)!=3×5!+4×4!+1×3!+0×2!+1×1!+0×0!

时间复杂度O(NlogN)

假设原排列为a[ ],阶乘进制为s[ ],排名为rk,下面直接给出转换代码(排名从0开始,数组下标均从1开始) a[ ]s[ ]rk

一些例题:a[ ]->s[ ]->rk:P5367 【模板】康托展开 - 洛谷 (luogu.com.cn) s[ ]->a[ ]:UVA11525 Permutation - 洛谷 (luogu.com.cn) a[ ]->s[ ],s[ ]+rk->a[ ] U72177 火星人plus - 洛谷 (luogu.com.cn)

 

 

 

线性代数

矩阵

 

矩阵乘法

矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。

AP×M 的矩阵,BM×Q 的矩阵,设矩阵 C 为矩阵 AB 的乘积,

其中矩阵 C 中的第 i 行第 j 列元素可以表示为矩阵A的第i行与矩阵B的第j列分别相乘再求和:

Ci,j=k=1MAi,kBk,j

矩阵乘法满足结合律,不满足一般的交换律。利用结合律,矩阵乘法可以用快速幂的思想优化。

 

 

 

矩阵快速幂

时间复杂度 O(N3logK)

P3390 【模板】矩阵快速幂 - 洛谷 (luogu.com.cn)

给点一个n*n的矩阵A,求Ak,对1e9+7取模。

 

 

P10502 Matrix Power Series - 洛谷 (luogu.com.cn)

给定一个 n×n 的矩阵 A 和一个正整数 k ,求 S=A+A1+A2++Ak

S(k)={S(k1)+Ak kS(k/2)+S(k/2)Ak2k

 

 

矩阵封装

默认0_idx、N*N的矩阵大小,根据实际需要修改代码。

MatA(n);  
A +* B矩阵加/乘法 
auto B = A.qmi(k)矩阵快速幂 
A.norm()化为单位矩阵 
auto B = inv(A)求逆矩阵诺不存在则B[0][0] == -1
det(A)行列式求值 
add(x,y,w)矩阵树连边注意0_idx
   

 

 

行列式

定义

A=|a11a12a1na21a22a2nan1an2ann|

对于一个矩阵A[1n][1n],其行列式为det(A)=P(1)μ(P)i=1nA[i][pi] (枚举排列P[1n],其中μ(P)为排列P的逆序对数,det(A)又称作|A|

 

一些性质

  • 单位矩阵的行列式为1。

  • 交换两行(列),行列式的值变号。

  • 诺某一行(列)乘以 t,行列式的值也就乘以 t

  • 若行列式某一行(列)的元素是两数之和,则行列式可拆成两个行列式的和。|a+ab+bcd|=|abcd|+|abcd|

  • 行列式某一行(列)元素加上另一行(列)对应元素的k倍,行列式的值不变。

  • 诺有两行(列)一样,则行列式的值为0

 

行列式求值

高斯消元实现,时间复杂度O(N3)

 

 

 

 

 

 

线性基

常用来解决子集异或一类题目

从a[ ]中选任意个整数(可能包含重复元素),使得选出的整数异或和最大,求这个异或和最大值可能是多少

 

应用:

  • 快速查询一个数是否可以被一堆数异或出来

  • 快速查询一堆数可以异或出来的最大/最小值

  • 快速查询一堆数可以异或出来的第k大值

 

 

 

概率论

 

一般情况下,解决概率问题需要顺序循环,而解决期望问题使用逆序循环

 

 

期望

若随机变量 X,Y 的期望存在,则

  • 对任意实数 a,b,有 E(aX+b)=aEX+b

  • E(X+Y)=EX+EY

通常把终止状态作为初值,把起始状态作为目标,倒着进行计算。因为在很多情况下,起始状态是唯一的,而终止状态很多。根据数学期望的定义,诺我们正着计算,则还需求出从起始状态到每个终止状态的概率,与F值相乘求和才能得到答案,增加了难度,也很容易出错

 

 

方差

设随机变量 X 的期望 EX 存在,且期望 E(XEX)2 也存在,则称上式的值为随机变量 X方差,记作 DXVar(x),各个数据与均值的差的平方和。方差的算术平方根称为 标准差,记作 σ(X)=DX

方差的性质

若随机变量 X 的方差存在,则

  • 对任意常数 a,b 都有 D(aX+b)=a2DX

  • DX=E(X2)(EX)2

 

数值算法

 

数值积分

自适应辛普森算法

求定积分lrf(x)dx ,即为f(x)在区间[l,r]上与x轴围成的面积 (其中x轴上方为正值,下方为负值)

 

P4525 【模板】自适应辛普森法 1 - 洛谷 (luogu.com.cn)

试计算积分lrcx+dax+bdx结果保留至小数点后6位。

 

高斯消元

 

高斯消元解线性方程组

{a1,1x1+a1,2x2++a1,nxn=b1a2,1x1+a2,2x2++a2,nxn=b2am,1x1+am,2x2++am,nxn=bm

运用初等行变换,把增广矩阵,变为阶梯型矩阵。最后再把阶梯型矩阵从下到上回代到第一层即可得到方程的解。

时间复杂度O(N3)

枚举每一列c

找到当前列绝对值最大的一行,放到上面 将该行该列第一个数变成1 再将下面其他所有行该列变成0

 

高斯消元解异或方程组

{a1,1x1a1,2x2a1,nxn=b1a2,1x1a2,2x2a2,nxn=b2am,1x1am,2x2am,nxn=b1

在消元的时候使用「异或消元」而非「加减消元」,且不需要进行乘除改变系数(因为系数均为0和 1)

异或可以看做不进位的加法

 

 

插值

插值是一种通过已知的、离散的数据点推算一定范围内的新数据点的方法。插值法常用于函数拟合中。

拉格朗日插值

f(x)=i=1n(yijixxjxixj)

 

P4781 【模板】拉格朗日插值 - 洛谷 (luogu.com.cn)

对于 n 个点 (xi,yi),如果满足 ij,xixj,那么经过这 n 个点可以唯一地确定一个 n1 次多项式 y=f(x)

现在,给定这样 n 个点,请你确定这个 n1 次多项式,并求出 f(k)mod998244353 的值。

 

 

 

博弈论

博弈论简介 - OI Wiki (oi-wiki.org)

Nim游戏

n堆物品,每堆有ai个,两个玩家轮流取走任意一堆的任意一个物品(不能不取),取走最后一个物品的人获胜

博弈图和状态

如果将每个状态视为一个节点,再从每个状态向它的后继状态连边,我们就可以得到一个博弈状态图。 例如,如果节点 (i,j,k) 表示局面为 i,j,k 时的状态,则我们可以画出下面的博弈图

博弈图的例子

定义 必胜状态 为 先手必胜的状态,必败状态 为 先手必败的状态。 通过推理,我们可以得出下面三条定理:

  • 定理 1:没有后继状态的状态是必败状态。

  • 定理 2:一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。

  • 定理 3:一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

对于定理 1,如果游戏进行不下去了,那么这个玩家就输掉了游戏。

对于定理 2,如果该状态至少有一个后继状态为必败状态,那么玩家可以通过操作到该必败状态;此时对手的状态为必败状态——对手必定是失败的,而相反地,自己就获得了胜利。

对于定理 3,如果不存在一个后继状态为必败状态,那么无论如何,玩家只能操作到必胜状态;此时对手的状态为必胜状态——对手必定是胜利的,自己就输掉了游戏。

如果博弈图是一个有向无环图,则通过这三个定理,我们可以在绘出博弈图的情况下用O(N+M)的时间(其中N为状态种数,M为边数)得出每个状态是必胜状态还是必败状态。

Nim和

通过绘画博弈图,我们可以在 O(i=1nai) 的时间里求出该局面是否先手必赢。 但是,这样的时间复杂度实在太高。有没有什么巧妙而快速的方法呢? 定义 Nim 和 =a1a2an 当且仅当 Nim和为 0 时,该状态为必败状态;否则该状态为必胜状态。

 

SG函数

有向图游戏是一个经典的博弈游戏——实际上,大部分的公平组合游戏都可以转换为有向图游戏。 在一个有向无环图中,只有一个起点,上面有一个棋子,两个玩家轮流沿着有向边推动棋子,不能走的玩家判负。 定义 mex 函数的值为不属于集合 S 中的最小非负整数,即:

mex(S)=min{x}(xS,xN)

例如 mex({0,2,4})=1mex({1,2})=0

对于状态 x 和它的所有 k 个后继状态 y1,y2,,yk,定义 SG 函数:

SG(x)=mex{SG(y1),SG(y2),,SG(yk)}

而对于由 n 个有向图游戏组成的组合游戏,设它们的起点分别为 s1,s2,,sn,则有定理:当且仅当 SG(s1)SG(s2)SG(sn)0 时,这个游戏是先手必胜的。同时,这是这一个组合游戏的游戏状态 x 的 SG 值。

这一定理被称作 Sprague–Grundy 定理(Sprague–Grundy Theorem), 简称 SG 定理,适用于任何公平的两人游戏, 它常被用于决定游戏的输赢结果。

 

计算给定状态的 Grundy 值的步骤一般包括:

  • 获取从此状态所有可能的转换;

  • 每个转换都可以导致 一系列独立的博弈(退化情况下只有一个)。计算每个独立博弈的 Grundy 值并对它们进行 异或求和

  • 在为每个转换计算了 Grundy 值之后,状态的值是这些数字的 mex

  • 如果该值为零,则当前状态为输,否则为赢。

 

将 Nim 游戏转换为有向图游戏

我们可以将一个有 x 个物品的堆视为节点 x,则当且仅当 y<x 时,节点 x 可以到达 y 那么,由 n 个堆组成的 Nim 游戏,就可以视为 n 个有向图游戏了。 根据上面的推论,可以得出 SG(x)=x。再根据 SG 定理,就可以得出 Nim 和的结论了。

 

893. 集合-Nim游戏 - AcWing题库

给定n堆石子和一个由m个不同正整数构成的数字集合S。两位玩家轮流操作,每次可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合S,判断先手是否必胜?

 

VS AtCoder(★6) - AtCoder typical90_ae - Virtual Judge (vjudge.net)

给定n堆石子,每堆石子由w[i]颗白石和b[i]颗蓝石。两人轮流进行以下操作之一:

  • 选择一堆白石w >= 1的石子,向选择的石子中加入w颗蓝石,然后移除1颗白石。

  • 选择一堆蓝石b >= 2的石子,移除k颗蓝石子,其中1kb2

最后无法操作的输掉比赛。

 

 

计算几何

 

距离

距离二维计算多维计算
欧氏距离|AB|=(x2x1)2+(y2y1)2三维:|AB|=(x2x1)2+(y2y1)2+(z2z1)2
曼哈顿距离d(A,B)=|x1x2|+|y1y2|n维:d(A,B)=i=1n|xiyi|
切比雪夫距离d(A,B)=max(|x1x2|,|y1y2|)n维:d(A,B)=max{|xiyi|}(i[1,n])

 

曼哈顿距离与切比雪夫距离转换

曼哈顿->切比雪夫 : (x,y)(x+y,xy)

切比雪夫->曼哈顿 : (x,y)(x+y2,xy2),一般为了避免小数,我们可以横纵坐标同时乘2(即转换时不除以2),最后答案除以2。

曼哈顿坐标系是通过切比雪夫坐标系旋转 45 后,再缩小到原来的一半得到的。碰到求切比雪夫距离或曼哈顿距离的题目时,我们往往可以相互转化来求解。两种距离在不同的题目中有不同的优缺点,应该灵活运用。

 

[P5098 USACO04OPEN] Cave Cows 3 - 洛谷 (luogu.com.cn)

求平面内任意一点到其它点的最大距离

直接曼哈顿转切比雪夫坐标,答案就是max(当前的点的 x 和 x的极值做差的绝对值 , 当前的点的 y 和 y 的极值做差的绝对值的)

 

扫描线

扫描线的思路就是数据结构维护一维,暴力模拟另一维。

 

面积并

img

 

P5490 【模板】扫描线 & 矩形面积并 - 洛谷 (luogu.com.cn)

给每一个矩形的上下边进行标记,下面的边标记为 1,上面的边标记为 -1。每遇到一个水平边时,让这条边(在横轴投影区间)的权值加上这条边的标记。当前的宽度就是整个数轴上权值大于 0 的区间总长度,总面积即为(线)

 

 

周长并

P1856 [IOI 1998][USACO5.5] 矩形周长 Picture - 洛谷 (luogu.com.cn)

image875b5bc59b29c404.pngimaged3ade113f8ed97a4.png

横边的总长度 = || 竖边的总长度 = (2×线×)

 

 

二维数点

U245713 【模板】 二维数点 - 洛谷 (luogu.com.cn)

给定一个长度为n的序列a[],然后进行m次询问:求区间[l,r]内大小在[x,y]范围内的数的个数。

image-20250707030246376 a[i]看作平面上的一个点(i,a[i]),询问即为求矩形内包含多少个点。 我们将询问离线,用一条线从左往右扫描,每遇到一个点就把它加入一个集合,表示当前所有扫过的点,用权值树状数组维护集合。每个询问的答案即为1~r内位于[x,y]的数的个数减去1~l-1内位于[x,y]的数的个数。

类似的,诺给定二维平面上的点集[x,y],然后给出诺干个询问求矩形[x1,y1,x2,y2]内有多少个点,则需要分别将所有横纵坐标都离散化。例题[P2163 SHOI2007] 园丁的烦恼 - 洛谷 (luogu.com.cn)

 

平面几何

 

点线封装

点、向量 Pointp1(x1,y1);  
p1 +- p2向量加减p1+p2=(x1+x2,y1+y2)
p */ x向量乘除标量v p1=(x1×v,y1×v)
dot(p1,p2)点积p1p2=x1x2+y1y2=|p1p2|cosθ
cross(p1,p2)叉积p1×p2=x1y2x2y1=|p1||p2|sinθn
length(p)向量的模|p1|=x12+y12
normalize(p)单位向量p1^=p1|p1|
distance(p1,p2)两点之间距离(欧几里得距离) 
rotate(p)向量逆时针旋转90度 
sgn(p)判断向量所在象限(一/四:1,二/三:-1) 
pointInPolygon(p,vec<Point>)判断是否在内部或多边形边上(射线法,0_idx)多边形的点需要按顺/逆时针顺序排列,仅支持简单多边形(不自交)
线 Linel1({x1,y1},{x2,y2});  
length(l)线长度 
distancePS(p,l)线Segment距离 
pointOnSegment(p,l)判断是否在线 
distanceSS(l1,l2)线最短距离 
segmentIntersection(l1,l2)线相交判定
返回值:tuple(类型,交点1,交点2)
0:不相交
1:严格相交(交点在两线段内部)
2:重叠(返回重叠部分的两个端点)
3:端点相交(交点为线段端点)
segmentInPolygon(l,vec<Point>)线是否在内部(需满足:端点在内且不与任何边)。多变形的点需要按顺/逆时针顺序排列
distancePL(p,l)线Line距离 
parallel(l1,l2)判断两线是否平行或共线(叉积为0)1:共线 2:平行 0:相交
lineIntersection(l1,l2)求两线交点 (需要保证不平行/共线) 
pointOnLineLeft(p,l)是否在线ab)左侧(叉积为正)以直线的方向向量ab方向为基准
hp(vec<Line>)返回顶点集(半平面交S&I算法,并按逆时针排列)传入的参数不需要预先排列

 

 

 

其它

 

中位数

一般要求最大化中位数之类的题目,可以二分一个数x,诺a[i] >= x则赋权值w[i]为1,否则为-1,判断某一区间中位数是否大于等于x,即求该区间和是否大于0。

 

对顶堆

动态维护中位数,插入/删除O(log),查找O(1)

se1的末尾元素即为中位数

image-20240924013344229

 

例题:

题意:定义一个数组的连续子数组(a[l] ~ a[r])每一项满足 ai+1=ai+1 为一个彩虹子数组,可以至多进行 k 次操作使任意ai+1ai1,求能构造出的最长彩虹子数组

思路:考虑ai+1=ai+1可以转化为ai+1(i+1)=aii,所以先预处理把所有的ai减去自己下标,问题就变成了:把一个区间的所有数字全部变成一个相同的数字,很容易知道,最小代价就是把所有数变成中位数即可,所以接下来就用一个双指针滑动窗口来维护,求最大的区间长度,这里动态维护滑动窗口的中位数用两个multiset

 

第k小数求中位数

查找O(N)

快排 或STL函数nth_element()

 

 

 

主席树

可持久化权值线段树

求区间第k小,不支持修改

 

 

均值不等式

a1+a2+...+ann>=a1a2...ann
21a+1b<=ab<=a+b2<=a2+b22

 

 

约瑟夫环

n 个人标号 0,1,,n1。逆时针站一圈,从 0 号开始,每一次从当前的人逆时针数 k 个,然后让这个人出局。问最后剩下的人是谁。

 

 

吉姆拉尔森日期公式

给定具体日期,推当天是星期几。也可以求两个日期的天数之差等等。

 

二维和一维坐标转化

下标从0开始

n行m列

idx = i*m + j

(i,j) = (idx/m,idx%m)

01234
56789
1011121314
1516171819

 

下标从1开始

n行m列

idx = (i-1)*m + j

(i,j) = ((idx+m-1)/m,(idx%m)? idx%m : m)

12345
678910
1112131415
1617181920

 

 


 

基础算法

前缀和&差分

在头文件中也包含了一维前缀和/差分函数 int a[6] = {1,2,3,4,5,6},s[6]; partial_sum(a,a+6,s); //s = {1,3,6,10,15,21} adjacent_difference(a,a+6,s); //s = {1,1,1,1,1,1}

一维前缀和

pre[i] = a[1]+a[2] +...+a[i] = pre[i-1]+a[i] 前缀和数组一般下标从1开始,方便写

 

二维前缀和

子矩阵的和:

image-20231118215947288

 

       
       
  x1,y1    
       
    x2,y2  
       
       
       

 

一维差分

dif[1] + dif[2] + ... + dif[i] = a[i]; 往往与前缀和联系

dif[i] = arr[i] - arr[i-1];

 

 

二维差分

 

 

 

 

 

二分

二分查找

目标数组需要为非降序排列

 

 

二分答案

单调区间中,每次查找去掉不符合条件的一半区间,直到找到答案(整数二分)或者和答案十分接近

 

 

 

实数域二分

 

 

分数规划

分数规划 - OI Wiki (oi-wiki.org)

分数规划用来求一个分式的极值。 每种物品有两个权值ai和bi,求一组w{0,1},选出若干个物品使得i=1naiwii=1nbiwi最小/最大。 一般分数规划问题还会有一些奇怪的限制,比如『分母至少为k』。

假如我们要求最大值,二分check一个mid,然后推柿子 aiwibiwi>mid ==>aiwimidbiwi>0 ==>wi(aimidbi)>0 //诺不等式大于0说明mid可行

主要难点在于如何求wi(aimidbi)的最大值/最小值

 

子段和问题

 

无长度限制

求一个子段,它的和最大,没有“长度大于等于F”这个限制 无长度限制的最大子段和问题是一个经典问题,只需要O(n)扫描该序列,不断 地把新数加入子段,当子段和变为负数的时候,就把当前整个子段清空。扫描过程 中出现过的最大的子段和即为所求

 

区间[l,r]的最大子段和:详见线段树

 

 

有长度限制

 

求一个子段,他的和最大,长度不超过k135. 最大子段和

详见 单调队列优化

 

 

求一个子段,他的和最大,长度不小于k

子段可以转化为前缀和相减的形式,则有

maxij>=k{Aj+1+Aj+2+...+Ai}=maxk<=i<=n{sumimin0<=j<=ik{sumj}}

 

 

 

三分

如果需要求出单峰函数的极值点,通常使用二分法衍生出的三分法求单峰函数的极值点

三分法每次操作会舍去两侧区间中的其中一个。为减少三分法的操作次数,应使两侧区间尽可能大。因此,每一次操作时的 lmidrmid 分别取 midεmid+ε 是一个不错的选择。

 

 

 

双指针

for(int i = 0,j = 0;i < n;i++){ while(j < i && check[i] [j]) { j++; //每道题的逻辑 } } 可以将O(n^2)优化到O(n);

 

 

 

排序

sort

需包含头文件

平均复杂度为O(NlogN),不保证稳定性

语法:sort(begin, end, cmp);

其中begin为指向待sort()的数组的第一个元素的指针,end为指向待sort()的数组的最后一个元素的下一个位置的指针,cmp参数为排序准则(不写默认从小到大进行排序);

 

stable_sort()

stable_sort() 也是一种O(n log n)时间复杂度的排序算法,但它保证稳定性,即相等的元素将保持其原始顺序。这使得它在需要保持相等元素顺序的场景中很有用。注意,稳定排序的代价是额外的空间复杂度。

 

 

 

快速排序

不稳定

快速排序的最优时间复杂度和平均时间复杂度为 O(nlogn),最坏时间复杂度为 O(n2)

 

第k小的数

 

归并排序

稳定

时间复杂度在最优、最坏与平均情况下均为 Θ(nlogn),空间复杂度为 Θ(n)

先排左半边,再排右半边,最后合并。

 

逆序对

对于一个排列,交换任意两个元素的位置,必然改变逆序对奇偶性。

 

分治

就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

大概的流程可以分为三步:分解 -> 解决 -> 合并。

  1. 分解原问题为结构相同的子问题。

  2. 分解到某个容易求解的边界之后,进行递归求解。

  3. 将子问题的解合并成原问题的解。

分治法能解决的问题一般有如下特征:

  • 该问题的规模缩小到一定的程度就可以容易地解决。

  • 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质,利用该问题分解出的子问题的解可以合并为该问题的解。

  • 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

 

 

P7883 平面最近点对(加强加强版) - 洛谷 (luogu.com.cn)

给定平面内n个点对p(x,y),求距离最近的两个点的距离(的平方)。由于输入的点为整点,因此这个值一定是整数。

将所有点排序后,将整个区间一分为二,分别递归处理,d=min(sol(S1),sol(S2)),再处理两个区间交界范围的点,假设当前交界点x坐标为midx,我们只需要处理x[midxd,midx+d]范围内的点即可。将这个区域的点按照y坐标升序排列,然后二重循环枚举(pi,pj)d=min(d,dist(pi,pj)),如果当前两个点之间的Δy >= d,则可以停止枚举第二个点。

 

 

二进制

 

lowbit

求n的二进制 第一次出现的1对应的值:

368: n = 101110000 -n = 010001111 -n+1 = 010010000 //以补码形式储存 n&-n = 10000 = 16

 

lowbit的应用:

 

 

求正整数n的二进制长度

(100101)2=6

 

求正整数n的二进制第k位代表的十进制数(2k或0)

 

状态压缩

用二进制表示状态 例如,a[ ] = {1,2,3,4,5,6,7,8}; 则v[22]表示10110 = a[5]+a[3]+a[2]

 

 

 

 

位运算

 

a+b = a|b + a&b = a^b + (a&b)*2

 

^ 异或

相同为0,不同为1,可以看做不进位加法 0^0 = 0 1^0 = 1 0^1 = 1 1^1 = 0

A ^ A = 0 A ^ 0 = A a ^ b ^ b = a 自反性 a ^ b ^ c ^ d = b ^ d ^ a ^ c 无序性 a^b = c 可移项为 a = b^c,移项时无需改变符号

如果i为偶数,则有 i^(i+1) = 1

比较两数值是否同号,a^b > 0 替换掉 a*b > 0

a ^= b ^= a ^= b 相当于 swap(a,b)

 

 

判断成对的数中只出现一次的数

 

异或前缀和

如果(n-1)%4 == 0,则0~n-1的异或前缀和为0S[0,3,7,11,15...] = 0

 

 

 

 

& 与

判断奇偶

 

 

 

>> 移位

n >> k 相当于 n/2k

n << k 相当于 n×2k

 

 

 

离散化

数组下标跨度长,但只用到了部分下标

 

部分涉及区间染色的题目,对于区间[l,r]离散化时,需要将[l-1,r-1]也一起加入离散化数组并去重,否则可能出现以下情况:例如用区间[1,3][6,10]覆盖区间[1,10]时,常规离散化会导致[1,10]整个区间被覆盖。例题:[P3740 HAOI2014] 贴海报 - 洛谷 (luogu.com.cn)

 

 

搜索

DFS

深度优先搜索,递归实现

在深度优先搜索中,对于最新发现的顶点,如果它还有以此为顶点而未探测到的边,就沿此边继续探测下去,当顶点v的所有边都已被探寻过后,搜索将回溯到发现顶点v有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点为止。如果还存在未被发现的顶点,则选择其中一个作为源顶点,并重复上述过程。整个过程反复进行,直到所有的顶点都被发现时为止。

括号序列

全排列

 

 

 

剪枝

优化搜索顺序

搜索前排序,减小搜索规模、优先搜索分支较少的节点

排除等效冗余

如果沿着几条不同分支到达的子树是等效的,那么只需要对其中一条分支进行搜索

可行性剪枝 (上下界剪枝)

对当前状态进行检查,如果当前分支已经无法到达递归的边界,就进行回溯

最优化剪枝

在最优化问题的搜索过程中,如果当前花费的代价超过了已经搜到的最优解,此时可以停止搜索,直接回溯

记忆化

记录每个状态的搜索结果,在重复遍历一个状态时直接检索并返回

其它优化

使用数据结构、状态压缩、位运算等优化

 

 

 

 

迭代加深

每次限制搜索深度的深度优先搜索。

迭代加深搜索的本质还是深度优先搜索,只不过在搜索的同时带上了一个深度 d,当 d 达到设定的深度时就返回,一般用于找最优解。如果一次搜索没有找到合法的解,就让设定的深度加一,重新从根开始。

当状态随着深度增加比较多时,BFS队列的空间复杂度会很大。当BFS在空间上不够优秀,而且问题要找最优解时,应该考虑迭代加深搜索,迭代加深也可以近似看做BFS。

 

过程

首先设定一个较小的深度作为全局变量,进行 DFS。每进入一次 DFS,将当前深度加一,当发现 d 大于设定的深度 limit 就返回。如果在搜索的途中发现了答案就可以回溯,同时在回溯的过程中可以记录路径。如果没有发现答案,就返回到函数入口,增加设定深度,继续搜索。

 

 

BFS

广度优先搜索,队列实现,求最短路径

每次都尝试访问同一层的节点。 如果同一层都访问完了,再访问下一层。

 

 

 

双端队列BFS

时间复杂度为严格的O(N+M)

对于一张边权为0或1的无向图。搜索时如果边权为0则将该新节点从队头入队,如果为1则从队尾入队

 

[P1948 USACO08JAN] Telephone Lines S - 洛谷 (luogu.com.cn)

求出一条路径,使点1到n中第k+1长的边最短,输出这条边的长度。 二分一个答案x,搜索时诺当前w > x则权值看作1,代表由通信公司免费报销。 诺最终需要报销的边数 <= k 则说明当前 x 符合条件。

 

Maze Challenge with Lack of Sleep(★4) - AtCoder typical90_aq - Virtual Judge (vjudge.net)

给定一个N*M的网格,#代表障碍,.代表路径,求从起点(rs,cs)到终点(rt,ct),最少转向次数。

设定状态(x,y,dir)表示当前位置为(x,y),方向为dir,拓展到下一个节点(nx,ny,i)时,如果dir与i方向一致,则入队首,否则入队尾。

 

 

优先队列BFS

每次从队列中取出当前代价状态最小的进行扩展,当每个状态第一次从队列中被取出时,就得到了起点到该状态的最小状态,之后再被取出时则可直接忽略。

UVA11367 Full Tank? - 洛谷 (luogu.com.cn)

有N个城市M条无向边,每个城市都有一个加油站,加每单位油花费p[i]。 回答q次询问,每次给定油箱容量为c,起始点为st,终点为ed。求st到ed的最小花费?

 

 

双向搜索

诺问题有明确的“初态”和“终态”,可以从两端同时进行BFS或DFS,在中间交汇,组成最终答案。

双向BFS

P10487 Nightmare II - 洛谷 (luogu.com.cn)

给定一个N*M的网格,“M”代表男孩每秒可以走3格,“G”代表女孩每秒可以走1格,“Z”代表鬼每秒拓展2格,“X”代表墙,求在不进入鬼的占领区的前提下,男孩和女孩能否会合,诺能则输出最短会合时间。

从起始状态和目标状态分别开始,两边轮流进行,每次各扩展一整层,当两边各自有一个状态发生重复时,就说明这两个搜索过程相遇了,就可以合并出起点到终点的最少步数。

 

 

 

双向DFS

P10484 送礼物 - 洛谷 (luogu.com.cn)

给定N个物品,每个物品体积为a[i],和一个容量为M背包,请问最多能装多少体积的物品? 其中N45,1a[i],M2311

本题使用背包求解的话体积过大,指数型枚举的话复杂度过高245

我们可以把礼物分成两半,对每一半分别搜索,将其能达到的体积分别存放于两个数组A,B中,对B数组进行排序,然后遍历A数组中的每一个元素x1,在B数组中二分找到x2,使得x1+x2 <= m,用二者之和更新答案。时间复杂度为O(2n2+1)

 

 

 

A*

为了提高搜索效率,我们设计一个“估价函数”,将“当前代价+未来估价”的最小状态作为堆顶进行拓展。 为了保证第一次从堆中取出目标状态时得到的就是最优解,我们设计的估价函数f(state)不能大于未来的实际代价g(state)。 这种带有估价函数的优先队列BFS就称为A*算法。

 

178. 第K短路 - AcWing题库

给定N个点,M条边的有向图,求从起点st到终点ed的第k短路(允许经过重复点或边)。

在优先队列BFS中,当节点x第k次被取出时,当前代价即为第k小代价。考虑A*优化。

  1. 我们以点x到终点ed的最短距离作为估价函数f(x),建反图以ed为起点求单源最短路即可求得f(x)。

  2. 建立二叉堆,存储二元组(x,dist + f(x)),x表示当前节点,dist代表当前实际代价,f(x)表示预估代价。最初堆中只有(st,0+f(st))

  3. 从堆顶取出dist + f(x)的最小二元组进行拓展,如果节点y被取出的次数尚未达到k次,就把新的二元组(y,(dist+w[i])+f(y))插入堆中。

  4. 重复3操作,直到终点ed被取出了k次,此时的dist即为从st到ed的第k短路。

A*算法的时间复杂度上界仍与优先队列BFS相同O(K(N+M)log(N+M)),不过由于估价函数的作用,图中很多节点访问的次数都远小于k,对于大多数数据,能比较快地求出结果,但能构造出数据,使得算法超时/超空间,正解应为可持久化可并堆做法。

 

IDA*

IDA* 为采用了迭代加深算法的 A* 算法。

 

 

时间复杂度与矩阵中1的个数有关,与矩阵r,c等参数无关,时间复杂度是指数级的O(cn),其中c为某个非常接近1的常数,n为矩阵中1的个数,尤其擅长处理稀疏矩阵。

dlx-2.svg

精确覆盖

P4929 【模板】舞蹈链(DLX) - 洛谷 (luogu.com.cn)

给定N行M列的矩阵,每个元素要么是1,要么是0。请从中挑选诺干行,使得每列有且仅有一行有1。输出任意一个方案即可,顺序随意。N,M500,保证1的个数不超过5000。

 

P1784 数独 - 洛谷 (luogu.com.cn)

求解大小为w*w的数独

 

重复覆盖

remove、recover、dance操作略有不同。 调用dlx.dance2()即可。

因为重复覆盖问题方案一般比精确覆盖多,搜索基于IDA*优化,加入了估价函数f()。

Luogu 蓝桥杯2019省A 糖果)

 

 

倍增

倍增法(英语:binary lifting),顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理,大大地优化时间复杂度。

这个方法在很多算法中均有应用,其中最常用的是 RMQ 问题和求 LCA(最近公共祖先)。

 

 

ST表

ST表(Sparse Table,稀疏表)基于倍增思想,用于解决[可重复贡献问题][区间重合区域不影响结果,如「RMQ 」、「区间按位与」、「区间按位或」、「区间 GCD」]的数据结构,不支持修改 O(NlogN)预处理 O(1)查询

image-20240814143114839

st(i,j)表示区间[i,i+2j1]的最大值,显然st(i,0)=ai 根据定义式,第二维就相当于倍增的时候「跳了 2j1 步」,依据倍增的思路,写出状态转移方程:st(i,j)=max(st(i,j1),st(i+2j1,j1))

对于每个询问 [l,r],我们把它分成两部分:[l,l+2s1][r2s+1,r],其中 s=log2(rl+1)。两部分的结果的最大值就是回答。

 

 

 

根号分治

根号分治,是一种对数据进行点分治的分治方式,它的作用是优化暴力算法,类似与分块,但应用范围比分块更广。

具体来说,对于所进行的操作,按照某个点B划分,分为大于B以及小于B两个部分,两部分使用不同的方式处理。(一般以根号为分界B=N,这样复杂度最平衡)。将两个暴力算法“拼接在一起”,实现优化复杂度的作用。

 

Colorful Graph(★6) - AtCoder typical90_ce - Virtual Judge (vjudge.net)

给定N个点M条边的无向图,初始时每个点颜色为1。再给定Q次查询,每次查询给定两个整数{x,c},输出当前点x的颜色,然后将点x及其所有相邻的点颜色改为c。1N,M,Q2e5

ans[x]={time,color}表示当前点最后被更新时的时间戳和颜色,flag[x]={time,color}flag状态标记,表示当前节点在time时更新应周围节点为color。 以度数是否大于N为分界,将点划分为重点和轻点。轻点直接枚举,重点打标记。 查询当前点:对于轻点,直接枚举所有邻接点更新自身。对于重点,本身已经被其它点更新。 更新邻接点:只需要更新周围的重点。

 


 

数据结构

基本数据结构

链表

单链表

 

 

双链表

 

APIO/CTSC2007(数据备份)

问题转化为差分数组 a1 ~ an1 中选则各不相邻的k个数

 

 

 

先进后出

 

 

表达式计算

中缀表达式:A op B 前缀表达式:op A B (波兰式) 后缀表达式:A B op (逆波兰式)

后缀表达式求值

后缀表达式对于计算机来讲容易实现

建立一个用于存储数的栈,逐一扫描该后缀表达式中的元素

  1. 如果遇到一个数,则把该数入栈。

  2. 如果遇到运算符,则取出栈顶两个数进行计算,把结果入栈。

扫描完成后,栈中恰好剩下一个数,即为该后缀表达式的答案

 

 

 

单调栈

 

 

直方图中最大的矩形

 

队列

qlqr
hh    tt

 

先进先出

 

单调队列

滑动窗口

窗口位置最小值最大值
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

此处的 "队列" 跟普通队列的一大不同就在于可以从队尾进行操作,STL 中有类似的数据结构 deque

 

最大子段和

给定一个长度为 n 的整数序列,从中找出一段长度不超过 m 的连续子序列,使得子序列中所有数的和最大。

最优策略是,下标递增,对应前缀和也递增

 

 

堆是一棵树,其每个节点都有一个键值,且每个节点的键值都大于等于/小于等于其父亲的键值。

堆主要支持的操作有:插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。

一些功能强大的堆(可并堆)还能(高效地)支持 merge 等操作。

一些功能更强大的堆还支持可持久化,也就是对任意历史版本进行查询或者操作,产生新的版本。

 

 

 

 

二叉堆

//下标从1开始比较方便:第k个数,左儿子为2k,右儿子为2k+1

操作实现
1.插入一个数heap[++size] = x; up(size);
2.求集合当中最小值heap[1];
3.[删除最小值][将第一个数等于最后一个数,删掉最后一个数,再下沉第一个数]heap[1] = heap[size]; size--; down[1];
4.[删除任意一个元素][将第k个数等于最后一个数,删掉最后一个数,再上下这个数]heap[k] = heap[size]; size--; down[k]; up[k];
5.修改任意一个元素heap[k] = x; down[k]; up[k];

 

146. 序列

给定 m 个序列,每个包含 n 个非负整数。 现在我们可以从每个序列中选择一个数字以形成具有 m 个整数的序列。 很明显,我们一共可以得到 n^m 个这种序列,然后我们可以计算每个序列中的数字之和,并得到 n^m 个值。 求出这些序列和之中最小的 n 个值。

思路:第一个数组a[]依次与其他数组合并,每次将a[]更新最小的n个数

 

左偏树

左偏树(leftist tree)是一种可并堆,具有堆的性质,可以快速合并,支持可持久化。

插入查询最小值删除最小值合并 
O(logN)O(1)O(logN)O(logN) 

 

 

 

配对堆

配对堆是一个支持插入,查询/删除最小值,合并,修改元素等操作的数据结构,是一种可并堆。有速度快和结构简单的优势,但由于其为基于势能分析的均摊复杂度,不支持可持久化。

插入查询最小值删除最小值合并 
O(1)O(1)O(logN)O(1) 

配对堆是一棵满足堆性质的带权多叉树,即每个节点的权值都小于或等于他的所有儿子。每个节点储存第一个儿子的指针,即链表的头节点;和他的右兄弟的指针。

img

查询最小值:根节点即为最小值。

合并:令两个根节点较小的作为一个新的根节点,然后将较大的作为它的儿子插进去。

插入:新建一个节点然后与原堆合并即可。

删除:删除操作较为麻烦,为了保证总的均摊复杂度,需要使用一个两步走的合并方法

  1. 把儿子们两两配成一对,在把配成一对的儿子合并到一起。

  2. 将新产生的堆从右往左(即老儿子到新儿子的方向)挨个合并到一起。 img img

 

 

哈希

开放寻址法

 

拉链法

 

雪花匹配

定义Hash函数H(a1...a6)=(i=16ai+i=16ai)%mod

 

 

 

 

并查集

并查集(DSU)是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素

i == p[i] 父节点等于自身的数量即为连通块的数量How Many Tables - HDU 1213 - Virtual Judge (vjudge.net)

 

 

 

边带权并查集

并查集实际上是由诺干棵树构成的森林,我们可以在树中的每条边上记录一个权值,即维护一个数组d[ ],用d[x]保存节点x到父亲节点p[x]之间的边权。在每次路径压缩后,每个访问过的节点都会直接指向树根,如果我们同时更新这些节点的d值,就可以利用路径压缩过程来统计每个节点到树根之间的路径上的一些信息。

image-20250703094151359

关系的传递可以看做向量。 如果pa == pb那么我们可以检查d[a] + s是否等于d[b]来判断是否矛盾,或者求出相对关系大小s 否则可以合并两者:p[pb] = pb, d[pb] = d[a] + s - d[b]

 

[P1196 NOI2002] 银河英雄传说 - 洛谷 (luogu.com.cn)

有N只飞船,M条指令,每条指令为以下之一:

1.M i j ,表示让i号飞船所在的队列全部飞船保持原有顺序,接在第j号飞船所在队列的尾部 2.C i j ,表示询问第i号飞船与第j号飞船当前是否处于同一列中,如果在,输出他们之间间隔了多少飞船

 

 

拓展域并查集

用于解决具有多个相互关系集合的问题。它是传统并查集的扩展,能够处理集合间的不同关系,如相互排斥或相互独立的关系。

 

[P1525 NOIP 2010 提高组] 关押罪犯 - 洛谷 (luogu.com.cn)

n 个点有 m 对关系,把 n 个节点放入两个集合里,要求每对存在关系的两个节点不能放在同一个集合。问能否成功完成?

我们使用拓展域并查集,将u和u+n分别表示u的两个相反状态,将(u,v+n)连边表示(u,v)不应在一个集合里(也可以看作u和v的反状态在一个集合里)。相应的(v,u+n)也应该连边。诺(u,u+n)在同一个集合里则说明发生了矛盾。

 

[P2024 NOI2001] 食物链 - 洛谷 (luogu.com.cn)

每个动物都是A,B,C的一种,三者形成环形食物链,依次给出m个句话,为以下两种形式之一 1 x y表示xy是同类 2 x y表示xy 诺当前话与前面的话产生矛盾,则当前话为假话。求有多少假话。

我们用(x)表示同类域,(x+n)表示捕食域,(x+2n)表示天敌域

 

 

分块

分块思想 - OI Wiki (oi-wiki.org)

例题:分块入门 (loj.ac)

O(N)预处理,O(N)修改/查询,支持区间修改,单点插入,区间查询等操作,较为灵活

元素个数n (1~n) 
每一块的最长长度mm = sqrt(n)
块的个数numnum = (n/m)+bool(n%m)
第i个元素所在的块id[i]id[i] = (i-1)/m + 1
第i个元素所在块的左端点b[id[i]].lif(b[id[i]].l == 0) b[id[i]].l = i
第i个元素所在块的右端点b[id[i]].rb[id[i]].r = max( b[id[i]].r , i )

 

 

 

 

 

 

 

树状数组

 

树状数组是(Fenwick Tree)一种支持单点修改区间查询,代码量小的数据结构,树状数组能解决的问题是线段树能解决的问题的子集

普通树状数组维护的信息及运算要满足 结合律可差分,如加法、乘法、异或等。

一维树状数组

image-20241118121146793

 

 

 

区间修改,单点查询

 

 

权值树状数组

诺题目允许离线,则离散化后空间复杂度为O(N),否则需要开到O(值域)的大小。

 

单点修改,全局第k小

 

P3369 【模板】普通平衡树 - 洛谷 (luogu.com.cn)

您需要动态地维护一个可重集合 M,并且提供以下操作:

  1. M 中插入一个数 x

  2. M 中删除一个数 x(若有多个相同的数,应只删除一个)。

  3. 查询 M 中有多少个数比 x 小,并且将得到的答案加一。

  4. 查询如果将 M 从小到大排列后,排名位于第 x 位的数。

  5. 查询 Mx 的前驱(前驱定义为小于 x,且最大的数)。

  6. 查询 Mx 的后继(后继定义为大于 x,且最小的数)。

对于操作 3,5,6,不保证当前可重集中存在数 x

本题中我们只需要关心的是每个数之间的相对关系,且允许离线,因此可以离散化处理。

 

 

静态区间颜色数

给点一个长度为n的数组a[ ],q个询问:区间[l,r]不同元素的个数。

思路:对于询问多个区间 [L,R] 中出现不同数字个数,当 R 相同时,如果区间出现了重复数字,那么我们只需要关心最右端的这个数字就可以了。换言之,重复出现的数字在左端将无任何贡献。例如 {1 2 3 1 4},在询问 区间[1,4] 时,第一个 1 无任何贡献,并且当询问的 R 不断右移的过程中,第一个 1 都无任何意义,被第四位置的替代掉。

于是把询问离线下来,按照询问的右端点排序。

当出现一个数字时,如果这个数字曾经出现,则 add(lst[pos[i]],-1),把这个数在上一个位置的标记清掉,add(pos[i],1) 来更新这个数字的新位置。只需要维护第i个位置上有没有数,求区间[l,r]内有多少个数。

用树状数组单点修改、区间查询。用前缀和 query(R)-query(L-1) 把区间[L,R]的数的个数出来。

 

 

线段树

线段树是常用的用来维护 区间信息 的数据结构。

可以在 O(logN) 的时间复杂度内实现单点/区间修改、区间查询(sum、max、min)等操作。

image-20241118222217276

 

建树

 

单点修改,区间查询

单点修改:从根节点开始遍历,递归找到需要修改的叶子节点,然后修改,然后向上传递信息。

区间查询: 1.若当前节点所表示的区间已经被询问区间所完全覆盖,则立即回溯,并传回该点的信息。 2.若当前节点的左儿子所表示的区间已经被询问区间所完全覆盖,就递归访问它的左儿子。 3.若当前节点的右儿子所表示的区间已经被询问区间所完全覆盖,就递归访问它的右儿子。

 

 

F - Palindrome Query (atcoder.jp)

单点修改,查询区间是否为回文串(字符串哈希)

h(abcd)=s[0]p3+s[1]p2+s[2]p1+s[3]

我们只需要单点修改,求区间和即可得到子串哈希值。比较正反串的哈希值是否一致判断回文串。

 

 

区间修改,区间查询,lazy标记

通过延迟对节点信息的更改,从而减少可能不必要的操作次数。每次执行修改时,我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改,但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。叶子结点无需下放标记。

Transformation - HDU 4578 - Virtual Judge (vjudge.net)

对数组a[]实现以下操作 1 x y z将区间[x,y]之间的每个元素增加z1z10000 2 x y z将区间[x,y]之间的每个元素乘以z1z10000 3 x y z将区间[x,y]之间的每个元素变为z1z10000 4 x y z输出axz+ax+1z++ayz对10007取模后的结果。1z3

 

SP2713 GSS4 - Can you answer these queries IV - 洛谷 (luogu.com.cn)

区间开平方,求区间和

对于区间开平方,由于我们无法在不更新叶子节点时更新区间,因此无法使用lazy标记优化区间修改。考虑到每个数最多被开平方有限次之后就会变为1,于是我们在修改时,一直修改到 叶子节点 或者 当前区间所有数都为1。

 

权值线段树

对权值作为维护对象而开的线段树,每个点存的是区间内对应数字的某种值(如出现次数等),操作跟线段树类似。

诺题目允许离线,则离散化后空间复杂度为O(N),否则需要开到O(max_val)的大小。

 

P3369 【模板】普通平衡树 - 洛谷 (luogu.com.cn)

与权值树状数组实现类似。

 

 

 

 

霍夫曼树

从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为 树的带权路径长度(Weighted Path Length of Tree,WPL)

wi 为二叉树第 i 个叶结点的权值,li 为从根结点到第 i 个叶结点的路径长度,则 WPL 计算公式如下:

WPL=i=1nwili

(也等于所有非叶子节点之和)对于给定一组具有确定权值的叶结点,可以构造出不同的树,其中,WPL 最小的树 称为 霍夫曼树(Huffman Tree)。霍夫曼树不唯一

如果每个字符的 使用频率相等,那么等长编码无疑是空间效率最高的编码方法,而如果字符出现的频率不同,则可以让频率高的字符采用尽可能短的编码,频率低的字符采用尽可能长的编码,来构造出一种 不等长编码,从而获得更好的空间效率。

在设计不等长编码时,要考虑解码的唯一性,如果一组编码中任一编码都不是其他任何一个编码的前缀,那么称这组编码为 前缀编码,其保证了编码被解码时的唯一性。

霍夫曼树可用于构造 最短的前缀编码,即 霍夫曼编码(Huffman Code)

 

 

不建树直接求n个节点k叉树的最小WPL

让n满足(n-1)%(k-1) == 0,否则不断填0,n++ 建立小根堆,每次取堆顶的k个求和s,再将s入堆,直到小根堆只剩一个元素

 

 

NOI2015 荷马史诗

求最短WPL,并且要让最长的霍夫曼编码最短

只需在合并时,对于权值相同的节点,优先考虑当前深度最小(已合并次数最少)的进行合并即可

image-20241010130102837 两种霍夫曼树WPL均为12,但右图最长编码更小

 

 

 

 

 


 

字符串

string s = “ABCDE”

子串(substring):s[i]~s[j] 连续的一段,如:BCD 子序列(subsequence):s[i]~s[j] 将若干元素提取出来并不改变相对位置形成的序列,如:ACD

前缀s[0~i]:A、AB、ABC、ABCD、ABCDE 真前缀:不包括本身的前缀 A、AB、ABC、ABCD

后缀s[i~n-1]:E、DE、CDE、BCDE、ABCDE 真后缀:不包括本身的后缀 E、DE、CDE、BCDE

回文串 :是正着写和倒着写相同的字符串,如aba、aa、abcba

字典序:以第i个字符作为第i关键字进行大小比较,空字符小于字符集内任何字符 如:abc < adc、a < aa、abcd < adcd

border:字符串中真前缀和真后缀相等的一段: 如f[a] = 0、f[aba] = a、f[abab] = ab、f[ababa] = a,aba、f[aaaa] = a,aa,aaa

 

字符串哈希

字符串哈希 - OI Wiki (oi-wiki.org)

只能匹配子串,不能匹配子序列

全称字符串前缀哈希法,把字符串变成一个p进制数字(哈希值),实现不同的字符串映射到不同的数字。 对形如 X1X2X3···Xn1Xn的字符串, 采用字符的ascii码乘上 P 的次方来计算哈希值。 映射公式: (X1×Pn1+X2×Pn2+...+Xn1×P1+Xn×P0)mod Q

h(S):=(i=0n1Pni1s[i]) mod Q

注意点: 1.任意字符不可以映射成0,否则会出现不同的字符串都映射成0的情况,比如A, AA, AAA皆为0 2.冲突问题:通过巧妙设置底数P(131或 13331),模数[Q(2^64)][ull,自然溢出]的值,减少冲突

问题是比较不同区间的子串是否相同,就转化为对应的哈希值是否相同。 求一个字符串的哈希值就相当于求前缀和,求一个字符串的子串哈希值就相当于求部分和。

前缀和公式 h[i+1]=h[i]×Ps[i]0<=i<=n1,h为前缀和数组,s为字符串数组 区间和公式h[l,r]=h[r+1]h[l]×Prl+1

区间和公式的理解:ABCDE 与 ABC 的前三个字符值是一样,只差两位, 乘上 P² 把 ABC 变为 ABC00,再用 ABCDE-ABC00得到 DE 的哈希值。

 

 

 

双哈希

单哈希如大模数哈希/自然溢出哈希仍然可能会被hack 使用两个模数进行哈希得出两个不同哈希值,减少冲突概率

 

 

KMP

一个模式串匹配一个/多个文本串

能够在线性时间内判定字符串 A[1~N] 是否为字符串 B[1~M] 的子串,并求出字符串A在字符串B中各次出现的位置。能比字符串哈希更高效准确地处理这个问题,并且能提供一些额外的信息

next[i]数组求的是子串s[1~i]的最长border(真前缀==真后缀)

 

前缀统计

统计每个前缀的出现次数

string s = abab; f(s) = a* 2 + ab*2 + aba + abab = 6

 

 

循环节

字符串的循环节

诺字符串S可以由子串A循环而成,则子串A是S的周期,如S = “abababab”,则周期=ababab

如果(ne[i] > 0 && i%[i-ne[i]] == 0),则前缀s[1~i]的最小循环节k = i-ne[i]

 

最长公共子串

求多个字符串的最长公共子串

二分+KMP

 

 

exKMP

也被称之为 ZAlgorithmKMP

对于一个长度为n的字符串s(1_idx),定义z[i]表示ss[i,n](即以s[i]开头的后缀)的最长公共前缀,我们将z称之为sz函数。考虑到z[1]的特殊性质,一般将其设置为z[1]=0。 例如z("aaaba") = {0,2,1,0,1}

时间复杂度O(N)

 

Trie字典树

高效地存储和查找字符串集合的数据结构

trie1

字符串统计

 

前缀统计

给定 N 个字符串 S1,S2SN,接下来进行 M 次询问,每次询问给定一个字符串 T,求 S1SN 中多少个字符串是 T 的前缀。

 

给定 N 个字符串 S1,S2SN,接下来进行 M 次询问,每次询问给定一个字符串 T,求 S1SN 中 T 是多少个字符串的前缀

 

 

最大异或对

在给定的 𝑁 个整数 𝐴1,𝐴2……𝐴𝑁 中选出两个进行 𝑥𝑜𝑟(异或)运算,得到的结果最大是多少?

 

P4551 最长异或路径

给定一棵 n 个点的带边权树,求树中最大的异或路径值。

思路:设d[x]表示根节点到x的路径异或值,则有d[x] = d[father[x]] ^ weight(x,father[x]),DFS一遍可以求出所有d[i],x到y的路径异或值就等于d[x]^d[y] (x到根 和 y到根,重叠部分异或抵消了,就相当于x到y),问题就变为d[N]中求最大异或对

 

AC自动机

多个模式串匹配一个/多个文本串

image-20250809122848561

  • 构建Trie前缀树

  • 构建失配指针:状态 u 的 faile指针 指向另一个状态 v ,其中 vTrie ,且 vu 的最长后缀(即在诺干个后缀状态中取最长的一个作为 fail指针)。

  • 查询文本串:例如,当前要匹配的文本串为shers,在字典树上找到状态9:she时,此时无后续节点,失配,直接跳转到状态9:she的最长后缀状态2:he,然后继续匹配。

 

 

 

拓扑排序优化

fail 指针的一个性质:一个 AC 自动机中,如果只保留 fail 边,那么剩余的图一定是一棵树。这样 AC 自动机的匹配就可以转化为在 fail 树上的链求和问题

观察到时间主要浪费在在每次都要跳 fail。如果我们可以预先记录,最后一并求和,那么效率就会优化。

于是我们按照 fail 树,做一次内向树上的拓扑排序,就能一次性求出所有模式串的出现次数。

 

 

回文串

Manacher

O(N)求得对于每个i的最长回文长度,这里下标从0开始

t = "abbba" 则对应s = " #a#b#b#b#a#",可以同时处理奇偶回文串,而不必分开讨论,对s求得d1[ ] d1[i]为以s[i]为中心的最长回文串长度。 对于t[i]来说,d1[i*2]-1 即为以i为中心,最长的奇数长度回文串 d1[i*2+1]-1即为以(i,i+1)中点为中心最长的偶数长度回文串

 

 

 

 

最小表示法

求s的循环同构中字典序最小,且下标最小的一个

时间复杂度O(N)

 

 

后缀数组

这里假定字符串长度为n,下标从1开始。“后缀i”表示以第i个字符开头的后缀,储存时用i表示字符串s的后缀s[i...n]。

后缀数组sa[i]表示将所有后缀排序后,第i小的后缀的编号 排名数组rk[i]表示后缀i的排名,重要的辅助数组。 这两个数组满足性质:sa[rk[i]] = rk[sa[i]] = i height数组height[i],即lcp(sa[i],sa[i-1])

img 后缀数组示例

 

P10469 后缀数组 - 洛谷 (luogu.com.cn)

排序+哈希+二分

时间复杂度O(nlog2n)

 

倍增实现

时间复杂度O(NlogN)

 

 

height数组

lcp为最长公共前缀,下文以lcp(i,j)表示后缀i和后缀j的最长公共前缀。

height[ ]数组的定义:height[i] = lcp(sa[i],sa[i-1]),即第i名的后缀与它前一名的后缀的最长公共前缀。height[1]可以视作0

 

一些应用

两子串最长公共前缀 lcp(sa[i],sa[j]) = min({height[i+1...j]})

如果height一直大于某个数,前这么多位就一直没变过;反之,由于后缀已经排好序了,不可能之后变回来。 求两子串的最长公共前缀就转化为了RMQ问题。

比较两子串的大小关系 假设比较的子串为A = s[a,b]B = s[c,d]

lcp(a,c)min(|A|,|B|)A<B|A|<|B| 否则,A<Brk[a]<rk[c]

求字符串循环同构的字典序排名
[P4051 JSOI2007] 字符加密 - 洛谷 (luogu.com.cn) 将s复制一遍后,求sa[ ]

求不同子串的数目
P2408 不同子串个数 - 洛谷 (luogu.com.cn) 每个子串一定是某个后缀的前缀,所以可以计算子串总数,枚举每个后缀,减掉重复。

n(n+1)2i=2nheight[i]

求至少出现k次的子串(可重叠)的最大长度
[P2852 USACO06DEC] Milk Patterns G - 洛谷 (luogu.com.cn) 出现至少k次意味着后排序后,有至少连续k个后缀以这个子串作为公共前缀。 所以求出每相邻k-1个height的最小值,这些最小值的最大值即为答案,这里可以用单调队列O(n)解决

结合并查集/线段树/单调栈等数据结构

 

 

其它

 

求字符串S中长度为k的子序列中,字典序最小的一个。1KN105

贪心实现,依次考虑子序列的每一位,从合法区间[l,r]中选择字典序最小的一个字母,选择该字母后,该字母前面的字母都不能选,于是我们可以不断缩小合法区间。

 

 

给定一个长度为N的字符串S,求有多少个的子序列 = 字符串T。

设dp[i]为T的前i个前缀出现的次数,时间复杂度O(NM)

 


 

图论

 

图论部分简介 - OI Wiki (oi-wiki.org)

作图工具Graph Editor (csacademy.com)

树和图的存储

邻接矩阵

空间复杂度n^2,适合存储稠密图,可以快速查询一条边是否存在

 

邻接表

适合存稀疏图,不支持随机访问

初始 h[u] -> -1 add(u,1) h[u] -> 1 -> -1 add(u,2) h[u] -> 2 -> 1 -> -1 add(u,3) h[u] -> 3 -> 2 -> 1 -> -1

 

 

树和图的遍历

二叉树的遍历 
前序遍历根-左-右
中序遍历左-根-右
后序遍历左-右-根

 

DFS

 

 

DFS序列

 

每个节点x的编号在dfs序中恰好出现两次,假设这两次的位置为L[x]和R[x],则闭区间 L[x] ~ R[x] 就是以x为根的子树的dfs序。可以通过dfs序把子树统计转化为序列上的区间统计。例题:线段树维护子树信息Assign the task - HDU 3974 - Virtual Judge (vjudge.net)

image-20241011010913743 DFS序:1 2 8 8 5 5 2 7 7 4 3 9 9 3 6 6 4 1

 

 

连通块划分

image-20241014131037652 对一个森林多次dfs/bfs可以划分出每一棵树,并查集可以达到类似效果

 

 

BFS

 

拓扑排序

在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:

  1. 每个顶点出现且只出现一次。

  2. 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。

image-20240116000247366

所有入度为0的点都可以作为起点,一个有向无环图至少存在一个入度为0的点,答案一般不唯一

image-20240116002301548

 

 

最短路

image-20240116111717099

 

记录路径

邻接表用pre[a] = b 表示a是由b过来的,邻接矩阵用pre[i][j] = k

 

最短路条数

求最短路有多少条

 

诺要求最多同时划分成多少条最短路,他们之间不含公共边。则可以将所有最短路径上的边保留下来,(如何确定一条边是否为最短路:正反图各跑一次,诺起点->a + a->b + b->终点 == 最短路,则边(a,b)为最短路上的一条边),跑最大流即为答案。4264. 规划最短路 - AcWing题库

 

 

单源最短路

仅正权边

Dijkstra朴素

适合稠密图,邻接矩阵存 O(n^2)

 

 

Dijkstra堆优化

适合稀疏图 ,优先队列小根堆实现 O(mlogn)

 

 

 

含负权边

在图中如果存在负环,则从该环上任意一点出发,沿着环重复行走可以使路径总权值无限减小,因此通常意义上的“最短路”在这种情况下是没有定义的(路径长度可以无限小)。然而,根据具体问题的需求,我们仍然可以通过一些方法处理含有负环的最短路问题。

 

Bellman-Ford

可以解决有边数限制的问题(诺问题允许忽略负环,如限制路径边数时,可以处理负权环)

时间复杂度O(mn) 结构体存边

 

 

SPFA

也称为 队列优化的Bellman-Ford

一般O(m),最坏O(mn),邻接表存,队列实现

如果不被卡(SPFA已经死了.jpg),可以用来替代Dijkstra堆优化版

 

 

 

 

多源最短路

Floyd

可以有负权边,不能有负权环 O(n^3)

邻接矩阵存储

 

传递闭包

在一张点数为 n 的有向图的邻接矩阵中,给出任意两点间是否有直接连边的关系,让你求出任意两点之间是否有直接连边或间接连边的关系。 如果i能到达k,且k能到达j,则i也能到达j

 

Johnson

可以有负权边,不能有负权环

时间复杂度O(NMlogM)

  • 新建一个虚拟的0号节点,从这个点向其它点连一条边权为0的边。然后用Bellman-Ford求出0号节点到其它所有点的最短路,记为h[ ]

  • 假设存在一条从x到y边权为w的边,则我们重新设置边权为w+p[x]-p[y](类似于物理学中的势能概念),消除负权边的影响。

  • 接下来以每个点为起点跑n轮Dijkstra算法,再消除势能差,即可求出任意两点间的最短路。

 

 

(LCA)

无向树上任意两点的距离

O(NlogN)预处理,O(logN)查询

设两个节点分别为x,y,dist[i]为根节点到点i的距离,lca(x,y)表示两点的最近公共祖先。 则 ans = dist[x] + dist[y] - 2*dist[lca(x,y)]

 

 

 

树上问题

树的重心

重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。

  1. 树的重心如果不唯一,则至多有两个且相邻

  2. 以树的重心为根时,所有子树的大小都不超过整棵树大小的一半。

  3. 树中所有点到某个点的距离和中,到重心的距离和最小;如果有两个重心,那么到它们的距离和一样。

  4. 把两棵树通过一条边相连得到一棵新的树,那么新的树的重心在连接原来两棵树的重心的路径上。

  5. 在一棵树上添加或删除一个叶子,那么它的重心最多只移动一条边的距离。

 

 

树的中心

在树中,如果节点 x 作为根节点时,从 x 出发的最长链最短,那么称 x 为这棵树的中心。

性质:

  • 树的中心不一定唯一,但最多有 2 个,且这两个中心是相邻的。

  • 树的中心一定位于树的直径上。

  • 树上所有点到其最远点的路径一定交会于树的中心。

  • 当树的中心为根节点时,其到达直径端点的两条链分别为最长链和次长链。

  • 当通过在两棵树间连一条边以合并为一棵树时,连接两棵树的中心可以使新树的直径最小。

  • 树的中心到其他任意节点的距离不超过树直径的一半。

 

 

树的直径

树上任意两节点之间最长的简单路径即为「树的直径」。(可能有多条,所有直径经过相同的中点)

树形DP实现:我们记录当 1 为树的根时,每个节点作为子树的根向下,所能延伸的最长路径长度 d1 与次长路径(与最长路径无公共边)长度 d2,那么直径就是对于每一个点,该点 d1+d2 能取到的值中的最大值。

 

两次DFS/BFS实现(边权必须非负):首先从任意节点 y 开始进行第一次 DFS,到达距离其最远的节点,记为 z,然后再从 z 开始做第二次 DFS,到达距离 z 最远的节点,记为 z,则 dist(z,z) 即为树的直径。

定理:在一棵树上,从任意节点y开始进行一次 DFS,到达的距离其最远的节点z必为直径的一端。

 

 

 

 

最近公共祖先

性质

  1. LCA({u})=u

  2. uv 的祖先,当且仅当 LCA(u,v)=u

  3. 如果 u 不为 v 的祖先并且 v 不为 u 的祖先,那么 u,v 分别处于 LCA(u,v) 的两棵不同子树中;

  4. 前序遍历中,LCA(S) 出现在所有 S 中元素之前,后序遍历中 LCA(S) 则出现在所有 S 中元素之后;

  5. 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先,即 LCA(AB)=LCA(LCA(A),LCA(B))

  6. 两点的最近公共祖先必定处在树上两点间的最短路上;

  7. d(u,v)=h(u)+h(v)2h(LCA(u,v)),其中 d 是树上两点间的距离,h 代表某点到树根的距离。

 

倍增求LCA

O(NlogN)预处理,O(logN)查询,空间复杂度O(NlogN)

dfs预处理fa[i,j],表示节点i的第2j个祖先

求lca时,让深度最小的节点跳到与另一个节点同一个深度,诺此时两个节点相同直接返回当前节点。 再让两个节点同时往上跳到最后一个非公共祖先节点,该点的父亲节点即为LCA节点

 

Tarjan求LCA

离线算法,使用DFS+并查集实现

时间复杂度O(N+Q),常数较大

 

 

树上差分

树上差分可以理解为对树上的某一段路径进行差分操作,这里的路径可以类比一维数组的区间进行理解。适合多次修改(O(logN)),单次查询(需要O(N)dfs统计信息)。

 

点差分

[P3128 USACO15DEC] Max Flow P - 洛谷 (luogu.com.cn)

每次将a到b简单路径上的点权加上x,则val[a] += x,val[b] += x, val[lca] -= x,val[fa[lca]] -= x。因为回溯统计时lca会被加上2x,所以我们需要让lca减去x,再让lca的父节点减去x。

 

 

边差分

与点差分略有不同。

诺要将a到b上简单路径的边权加x,则dist[a] += x,dist[b] += x,dist[lca] -= 2x

 

 

 

树哈希

判断一些树是否同构的时,我们常常把这些树转成哈希值储存起来,以降低复杂度。

这里介绍一个实现简单且不容易被卡的做法,这类方法需要一个多重集的哈希函数。以某个结点为根的子树的哈希值,就是以它的所有儿子为根的子树的哈希值构成的多重集的哈希值,即:

hx=f({hiison(x)})

其中 hx 表示以 x 为根的子树的哈希值,f 是多重集的哈希函数。

以代码中使用的哈希函数为例:

f(S)=(c+xSg(x))modm

其中 c 为常数,一般使用 1 即可。m 为模数,一般使用 232264 进行自然溢出,也可使用大素数。g 为整数到整数的映射,代码中使用 xor shift,也可以选用其他的函数,但是不建议使用多项式。为了预防出题人对着 xor hash 卡,还可以在映射前后异或一个随机常数。

这种哈希十分好写,比每次使用mt19937_64(hs[k])( )生成随机数要快。如果需要换根,第二次 DP 时只需把子树哈希减掉即可。

 

 

生成树

最小生成树

无向连通图的 最小生成树(Minimum Spanning Tree,MST)为边权和最小的生成树。

从图(一般为无向有环图 )中生成一棵树(n-1条边)时,这棵树每条边的权重相加之和最小。

只有连通图才有生成树,而对于非连通图,只存在生成森林。

Kruskal

适合稀疏图 O(MlogM) 结构体存边 并查集实现

将边权从小到大排序,遍历边,诺当前边的两个端点属于不同的树,则合并这两颗树

kurskal重构树的一些性质

  • 是一棵二叉树。

  • 如果是按最小生成树建立的话是一个大根堆。

  • 原图中两个点间所有路径上的边最大权值的最小值 = 最小生成树上两点简单路径的边最大权值 = Kruskal 重构树上两点 LCA 的点权。

 

 

Prim朴素

适合稠密图 O(N2)

诺prim要输出具体选择的边,可以开一个辅助数组last[],更新dist[]时记录当前点从哪个点转移的,ans+=dist[t]时即选择了边(t,last)

 

 

Prim堆优化

比较复杂不常用,直接用Kruskal算法

 

 

Boruvka

Kruskal和Prim的结合,在边具有较多特殊性质的问题中,Boruvka算法具有优势。

 

唯一性

考虑最小生成树的唯一性。如果一条边 不在最小生成树的边集中,并且可以替换与其 权值相同、并且在最小生成树边集 的另一条边。那么,这个最小生成树就是不唯一的。

对于 Kruskal 算法,只要计算为当前权值的边可以放几条,实际放了几条,如果这两个值不一样,那么就说明这几条边与之前的边产生了一个环(这个环中至少有两条当前权值的边,否则根据并查集,这条边是不能放的),即最小生成树不唯一。

寻找权值与当前边相同的边,我们只需要记录头尾指针,用单调队列即可在 O(α(m))(m 为边数)的时间复杂度里优秀解决这个问题(基本与原算法时间相同)。

 

 

 

次小生成树

非严格次小生成树

求解方法

  • 求出无向图的最小生成树 T,设其权值和为 M

  • 遍历每条未被选中的边e=(u,v,w),找到 Tuv 的路径上边权最大的一条边e=(s,t,w),在 T 中用 e 替换 e,即可得到一颗生成树 T,其权值为 M=M+ww

  • 对所有的 M 取最小值即为答案。

其中求 u,v 路径上边权最大的值可以在倍增求 LCA 的过程中求得。

 

 

 

严格次小生成树

在用未选择的边 e=(u,v,w) 替换最小生成树 T 上的边时,找出 T(u,v) 路径中边权严格小于 w 的最大的一条边进行替换。

同时维护节点到祖先路径上的最大边权和严格次大边权即可。

 

 

生成树计数

 

无向图的生成树计数

UVA10766 Organising the Organisation - 洛谷 (luogu.com.cn)

给定n个点,两两之间有一条无向边,现在切断m条边,求剩下的图中有多少种不同的生成树

矩阵树定理,时间复杂度O(N3)

权值设为1求得的是不同生成树的个数。权值设为原边权求得的是不同生成树的权值之和。

 

 

有向图的生成树计数

[P4455 CQOI2018] 社交网络 - 洛谷 (luogu.com.cn)

给定n个点m条边的有向图,求以1为根节点的生成树个数。

如果要是给定root,不一定为1,将第root行和第n行交换,第root列和第n列交换,然后删除第n行n列再计算即可。

 

 

 

最小树形图

有向图上的最小生成树(Directed Minimum Spanning Tree)称为最小树形图。 所有从图中生成一颗 根节点能到达其它节点的树,边权和最小的一颗树

常用的算法是朱刘算法(也称 Edmonds 算法),可以在 O(nm) 时间内解决最小树形图问题

img

算法流程,对于每一次循环:

  • 初始化

  • 对于每个点,选择指向它的边权最小的一条边

  • 将选出的边累加到答案里,如果出现孤立点则无解

  • 如果没有环,算法完成,退出循环

  • 把所有不是环上的点全部设置为自己是一个独立的环(大小为1的新环)

  • 进行缩环并更新其它点到环的距离

  • 重新设置n和root

 

不定根的最小树形图

Ice_cream’s world II - HDU 2121 - Virtual Judge (vjudge.net)

输出 最小树形图权值 和 选定的根,诺根不唯一,输出编号最小的。

我们建立一个虚拟的超级源点,并向其它所有点连边,边权为大于原图所有边权之和和一个数(假设为sum),诺最后ans - sum >= sum说明虚拟源点建的边用了超过一次,则图不连通无解。否则最终答案就是ans-sum

主要在于如何找编号最小的根。如果有多个根,则他们最终会成一个环,这个环缩点后会与虚根相连,找出节点编号最小的一个根即可,因为我们从虚根向节点建边时是从m+1到m+n建边的,所以在下一次循环时,第一次访问到连向该环的边时,其编号(减去m)即为编号最小的根。

 

 

 

二分图

image-20240128162924921

性质:

  • 不存在边数为奇数的环

  • 如果两个集合中的点分别染成黑色和白色,可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。

 

二分图判定

染色法判二分图

判断是否是二分图(不存在奇环)

image-20240729102404459

 

 

 

最大匹配

“任意两条边都没有公共端点”的边的集合被称为图的一组匹配。在二分图中,包含边数最多的一组匹配被称为二分图的最大匹配

image-20250422194240838 例如图中红边集合为一种最大匹配方案。

匈牙利算法

又称增广路算法,二分图的一组匹配S是最大匹配,当且仅当图中不存在S的增广路。

时间复杂度 O(NM),实际效率较高。

结果match[vi]=ui表示集合v中的点和集合u中的点完成配对。

 

无向图的最大匹配

只能求最二分图大匹配(即没有奇环),诺为一般图,则应换用带花树算法

 

多重匹配

 

HK 算法

Hopcroft–Karp算法,时间复杂度为O(MN),实际表现较好

 

转为网络流模型

边权设为1,源点向左边集合所有点连边,右边集合所有点向汇点连边。求最大流即可。

时间复杂度 O(MN)

 

 

常见问题模型

二分图匹配的模型有两个要素:

  1. 节点能分成独立的两个集合,每个集合内部有0条边。

  2. 每个节点只能与1条匹配边相连。

 

372. 棋盘覆盖 - AcWing题库

给定一个 N 行 N列的棋盘,已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌,并且任意两张骨牌都不重叠。

将骨牌看作无向边,在相邻的两个格子连边。如果把棋盘黑白染色(行号加列号为偶数染成白色,否则染成黑色)。那么相邻的两个格子颜色不同,有连边。同色的两个格子不相邻,没有边相连。该图是一张二分图,二分图的最大匹配即为最多能放骨牌的个数。

 

P10937 車的放置 - 洛谷 (luogu.com.cn)

给定一个 NM 列的棋盘,已知某些格子禁止放置。问棋盘上最多能放多少个不能互相攻击的車(同行或同列只能有一个车)。

 

 

 

最大权匹配

KM算法

时间复杂度O(N3)

 

转为费用流模型

  • 新建源点s1和汇点s2。

  • 源点向每个左部节点连一条流量为1,费用为0的边。

  • 每个右部节点汇点连一条流量为1,费用为0的边。

  • 对于二分图中每条左部到右部的边,连一条流量为1,费用为边权的边。

  • 另外如果考虑非完美匹配,对于每个左部节点还需要向汇点连一条流量为1,费用为0的边。最大费用的前提是最大流。

  • 求这个网络的最大费用最大流即可,此时网络的最大流量一定为左部节点的数量,而最大流量下的最大费用即对应一个最大权匹配方案。

时间复杂度较高,比KM算法慢了大概一个数量级,如果数据范围较大建议换KM算法。

 

 

 

 

 

 

最小点覆盖

求出一个最小的点集S,使得任意一条边都至少有一个端点属于S

König定理:最小点覆盖=最大匹配

二分图最小覆盖的模型特点是:每条边有2个端点,二者至少选择一个。

 

[P6062 USACO05JAN] Muddy Fields G - 洛谷 (luogu.com.cn)

给定一个N*M的网格,其中一些地面时泥泞的,你需要用一些宽度为1,长度任意的木板将所有泥地盖住,同时不能盖住干净的地面,木板可以重叠。N,M <= 50。

每块泥地要么被第i行的一个横着的木板盖住,要么被第j列的一个竖着的木板盖住,二者至少选择一个,满足二分图最小覆盖特点。把行木板作为左边,列木板作为右边,对于每块泥地,在它所属的行木板与列木板之间连边,求出二分图的最小覆盖,即为最少得木板覆盖所有泥地的答案。

 

 

最大独立集

选最多的点,满足两两之间没有边相连。

定理:设G是有N个点的二分图,则G的最大独立集等于顶点数N-最大匹配数

求解一个图中的最大独立集等价于求解其反图的最大团(即两两之间都有连边)。

 

P10939 骑士放置 - 洛谷 (luogu.com.cn)

给点N*M的棋盘,其中有一些格子禁止放旗子,问棋盘上最多能放多少个互不攻击的骑士(与象棋的马类似,攻击‘日’字)。N,M <= 100。

将棋盘黑白染色后,可以发现,一匹马可以跳到的格子的颜色一定与当前所在格子颜色相反。于是我们可以将每个位置与能跳到的位置连边,这样就构成了一个二分图(所有白色格子是一部分,所有黑色格子是一部分)。如果想让所有的马都不能互相吃,那么这个二分图里一条边的两个点最多只能选一个点放马,所以这题就是让我们在一个二分图里相邻的两个点只能选一个,问最多能选多少个点。

image-20250423003607638

 

 

最小路径覆盖

在一个有无环向图中,找出最少得路径,使得这些路径经过了所有点。特别的,每个点自己也可以称为是路径覆盖,只不过路径的长度是0。

 

最小不相交路径覆盖

每一条路径经过的顶点各不相同。

原图G中每个点如果a能直接到达b,就加边a->b这样就得到了一个G的拆点二分图G2。

定理:DAG图G的最小不相交路径覆盖包含的路径条数 = n - 拆点二分图G2的最大匹配数

一开始每个点都是独立的为一条路径,总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径,也就相当于路径数减少了1。所以找到了几条匹配边,路径数就减少了多少。所以最小路径覆盖=原图的结点数-新图的最大匹配数

 

最小可相交路径覆盖

每一条路径经过的顶点可以相同。

思路:先用floyd求出原图的传递闭包,即如果a能直接/间接到达b,那么就加边a->b。得到有向无环图G2,再在G2上求最小不相交路径覆盖即可。

 

一般图最大匹配

一般图匹配和二分图匹配不同的是,图可能存在奇环。一般图的最大匹配可以用带花树算法(blossom alogrithm)解决。

时间复杂度在O(NM)O(N3)左右

 

一般图最大权匹配

时间复杂度O(N3)

 

 

基环树

n个点n条边组成的无向连通图。若不保证连通,也有可能是内/外向树/森林。

找环

可以以拓扑排序或者dfs实现: P8655 发现环 - 洛谷

基环树的直径

直径有两种情况,二者取最大值即为答案:

  1. 直径处于以环上某一点为根节点,且不经过环边的子树中。对每一颗子树进行树形DP求直径,取最大值。

  2. 经过环边,链接两个根节点x,y的子树。ans = max{d1[x]+d1[y]+dis(x,y)}。d1[i]表式以i为根节点向下能达到的最大距离,dis(i,j)表示环上两点之间的最远距离,断链成环,复制拼接,再用前缀和+单调队列优化即可O(N)求得答案。

 

一般处理方法

  1. 找到唯一的环;

  2. 对环之外的部分按照若干棵树处理;

  3. 考虑与环一起计算。

 

 

负环

SPFA判负环

如果某点的最短路所包含的边数大于等于n,则说明存在负环

 

 

bellman-ford判负环

bellman-ford判负环,据bellman-ford的性质最后得出的是通过不超过n-1条边的从起点到其他点的最短距离

但是如果在n-1次循环之后仍然存在边可以被松弛,那么就存在负环(因为如果没有负环n-1次就已经确定了最短距离,具体可参考bellman-ford证明,已经是最短距离了还能被松弛,必然是存在负环)

 

 

差分约束

求解差分约束系统,有 m 条约束条件,每条都为形如 xaxbckxaxbckxa=xb 的形式,判断该差分约束系统有没有解。

题意转化连边
xaxbcxbxacadd(a, b, -c);
xaxbcxaxbcadd(b, a, c);
xa=xbxaxb0, xbxa0add(b, a, 0), add(a, b, 0);

判断负环,如果存在负环,则无解。

建立一个虚拟的源点0,设 dist[0]=0 并向每一个点连一条权重为 0 边,跑单源最短路,若图中存在负环,则给定的差分约束系统无解,否则,xi=dist[i] 为该差分约束系统的一组解。 注意到,如果 {x1,x2,,xn} 是该差分约束系统的一组解,那么对于任意的常数 d{x1+d,x2+d,,xn+d} 显然也是该差分约束系统的一组解,因为这样做差后 d 刚好被消掉。

一般使用 SPFA 判断图中是否存在负环,最坏时间复杂度为 O(nm)

 

 

连通性相关

 

割点和割边

dfn[x]为每个点dfs第一次被访问的时间戳

low[x]为以下节点的时间戳的最小值 1.x的子树中的节点 2.通过一条不在搜索树上的边,能够到达x的子树的节点

从根开始的一条路径上的 dfn 严格递增,low 非严格递增

 

割点

对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。

诺x不是搜索树的根节点root(dfs的起点),则x是割点当且仅当搜索树上存在一个x的子节点满足dfn[x] <= low[y] 诺x是搜索树的根节点,则x是割点当且仅当搜索树上存在至少两个子节点y1,y2满足上式

 

 

割边

对于一个无向图,如果删掉一条边后图中的连通分量数增加了,则称这条边为桥或者割边。

无向边(x,y)是割边,当且仅当搜索树上存在x的一个子节点y满足dfn[x] < low[y]

 

 

双连通分量

 

在一张连通的无向图中,对于两个点 uv,如果无论删去哪条边(只能删去一条)都不能使它们不连通,我们就说 uv 边双连通

在一张连通的无向图中,对于两个点 uv,如果无论删去哪个点(只能删去一个,且不能删 uv 自己)都不能使它们不连通,我们就说 uv 点双连通

边双连通具有传递性,即,若 x,y 边双连通,y,z 边双连通,则 x,z 边双连通。

点双连通具有传递性,反例如下图,A,B 点双连通,B,C 点双连通,而 A,C 点双连通。

bcc-counterexample.png

对于一个无向图中的 极大 边双连通的子图,我们称这个子图为一个 边双连通分量

对于一个无向图中的 极大 点双连通的子图,我们称这个子图为一个 点双连通分量

 

 

边双连通分量

不存在割边。

e-DCC的求法比较简单,先求出无向图中的所有割边,把割边删除后,剩下的图会分成若干个连通块,每一个连通块就是一个“边双连通分量”。

 

 

点双连通分量

不存在割点

一张无向图是点双连通图,当且仅当满足下列两个条件之一

  1. 图的顶点数不超过 2。

  2. 图中任意两点都同时包含在至少一个简单环中。其中“简单环”指的是不自交的环,也就是我们通常画出的环。

 

 

强连通分量

有向图强连通分量的Tarjan算法 (byvoid.com)

给点一张有向图,诺对于图中任意两个节点相互可达,则称该有向图是“强连通图” 有向图的极大强连通子图被称为“强连通分量”,简记为SCC。

一个环一定是强连通图。Tarjan算法基本思路就是对于每个点,尽可能找到与它一起能构成环的所有节点。每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量

 

 

常应用缩点消除环的影响,转化为DAG图解决

在缩点后的DAG中,强连通分量的标号顺序是其拓扑序的逆序,出度为0的点标号标号越小,即反图的拓扑序。

 

 

2-SAT

有N个变量,每个变量只有两种可能得取值。再给点M个条件,每个条件都是对两个变量的取值限制。求是否存在对N个变量的合法赋值,使得M个条件均得到满足。

设一个变量Ai的两种取值分别是Ai,0Ai,1 。每个条件可以转化为统一的形式: “诺Ai的赋值为Ai,p,则Aj的赋值必须为Aj,q”,其中p,q{0,1}

 

2-SAT问题的判断方法如下(时间复杂度O(N+M)):

  1. 建立2N个节点的有向图,每个变量Ai对应两个节点ii+n

  2. 考虑每个条件,形如“诺Ai的赋值为Ai,p,则Aj的赋值必须为Aj,q”,p,q{0,1},从i+p*nj+q*n连一条有向边。 注意上述条件蕴含着它的逆否命题“诺Aj的赋值为Aj,1q,则Ai的赋值必须为Ai,1p”。如果在给点的M个限制条件中,原命题和逆否命题不一定成对出现,应该从j+(1-q)*ni+(1-p)*n也连一条有向边。

  3. Tarjan算法求出有向图中所有的强连通分量。

  4. 诺存在i[1,n]满足ii+n属于同一个强连通分量,则出现了矛盾:诺变量Ai赋值为Ai,p,则变量Ai必须赋值为Ai,1p,说明问题无解。

  5. 诺问题还要求具体解,Tarjan后同一元素拆点强连通分量编号小的点即为合法点,如果一个元素拆成的两个点之间没有任何路径相连,即使是有向路径,那么这两点都可以成为合法点,这两点的分量编号不同,选小的即可

 

P4782 【模板】2-SAT - 洛谷 (luogu.com.cn)

N个变量,M个条件:xiaxjb(a,b0,1) 条件可转化为 xi1axjbxj1bxia。以此建边

P10969 Katu Puzzle - 洛谷 (luogu.com.cn)

 

 

网络流

网络流与线性规划24题 (luogu.com.cn)

一个网络G=(V,E),是一张有向图,图中每条边 (x,y)E 都有一个给定的权值c(x,y) ,称为边的容量,特别的诺(x,y)E,则c(x,y) = 0 。图中还有两个指定的特殊节点 源点S汇点T (S != T)。

f(x,y) 是定义在节点二元组(xV,yV)三的实数函数,且满足:

  1. 容量限制:f(x,y) <= c(x,y)

  2. 斜对称:f(x,y) = -f(y,x)

  3. 流量守恒:c

f()称为网络的流量函数,对于(x,y)Ef(x,y)称为边的流量c(x,y) - f(x,y)称为边的剩余容量

(S,v)Ef(S,v),为整个网络的流量(其中S表示源点)

 

最大流

对于一个给定的网络,合法流函数f()有很多。其中使得整个网络的流量最大的流函数被称为网络的最大流

建边时反边容量全为0

 

Edmondsd-Karp

时间复杂度O(NM2),实际效率较高,一般能处理10^3 ~ 10^4 规模的网络

每次bfs遍历整个残量网络,找出任意一条增广路,同时计算路径上各边剩余流量的最小值minf,显然可以让一股流沿着增广路从S流向T,网络的流量就可以增加minf。直到网络上不存在增广路为止。

 

 

Dinic

时间复杂度O(N2M),实际效率较高,能处理 10^4~10^5 规模的网络。特别地,在求解二分图最大匹配时间复杂度为O(MN),边权设为1,源点向A集合连边,B集合向汇点连边。

EK算法每次只找出一条增广路,而Dinic可以一次找出多条。

  1. 在[残量网络]上bfs求出节点的层次,构造[分层图]。

  2. 在分层图上dfs寻找增广路,回溯时更新边权。

 

 

 

最小割

诺删除一个边集EE后,S与T将不再连通, 则E为该网络的一个割。容量之和最小的割称为网络的最小割

最大流最小割定理:任何一个网络的最大流量等于最小割中边的容量之和,即“最大流=最小割”

 

 

求具体方案

在求完最大流后,从源点S出发,BFS遍历残量网络中还能到达的点,这些点属于S集合,剩下无法到达的点属于T集合。所有连接S和T的边即为属于最小割的边。

 

求割边数量

如果要在最小割的前提下最小化个边数量,那么先求出最小割,然后把没有满流的边容量改为INF,满流的边容量改为1,再跑一边最小割就可以求出最小割边数量; 如果没有最小割的前提,直接把所有边的容量设为1,求一遍最小割即可。

 

 

常见问题模型

有n个物品和两个集合A,B,每个物品必须且只能放入一个集合里,如果一个物品没有放入A集合会花费ai,如果没有放入B集合会花费bi,还有诺干个条件如(ui,vi,wi)表示如果uivi不在同一个集合里会花费wi,求最小代价。

这是一个经典的二者选一的最小割题目。我们设立一个超级源点s和超级汇点t,对每个点i连边add(s,i,a[i])add(i,t,b[i]),反边容量均为0。对每个限制条件连双向边add(u,v,w),add(v,u,w) 注意到,但源点和汇点不相连时,代表这些点都选择了一个其中集合,最小割就是最小花费。如果要求最大花费,将所有花费减去最小割即可。

例题:P1361 小M的作物 - 洛谷 (luogu.com.cn)

 

 

 

最大权闭合图

给定一张有向图,每个点都有一个权值a[i](可能 <= 0),你需要选择权值和最大的一组点集,满足:每个点的后继节点都必须包含在点集中。

结论:建立超级源点s和超级汇点t,诺节点u权值为正,则连边(s,u,a[i]);诺节点u权值为负,则连边(u,t,-a[i]);权值为0不用连,原图上所有边权改为。所有反边边权全为0,跑最大流,答案即为所有正权点之和减去最小割

 

例题:Get More Money(★7) - AtCoder typical90_an - Virtual Judge (vjudge.net)

也可用于处理不连通的有向森林

 

费用流

给定一个网络G=(V,E),每条边除了有容量限制c(x,y)外,还有一个单位流量的费用w(x,y),当(x,y)的流量为f(x,y)时,需要花费f(x,y) * w(x,y)的费用。w也满足斜对称性质,即w(x,y) = -w(y,x)

使该网络中花费最小的最大流称为最小费用最大流。注意:费用流的前提是最大流。

 

SSP算法(Successive Shortest Path):每次寻找单位费用最小的增广路进行增广,直到图上不存在增广路为止。时间复杂度最坏为O(nmf),其中f表示网络的最大流。实现时,只需将 EK 算法或 Dinic 算法中找增广路的过程,替换为用最短路算法寻找单位费用最小的增广路即可。需要保证网络没有负环。

 

P3381 【模板】最小费用最大流 - 洛谷 (luogu.com.cn)

 

 

 

欧拉图

欧拉路:给定一张无向图,诺存在一条从节点S到节点T的路径,恰好不重不漏地经过每条边一次,则称该路径为S到T的欧拉路

欧拉回路:特别地,诺存在一条从节点S出发,恰好不重不漏地经过每一条边一次(可以重复经过图中的节点),最终回到起点S,则称该路径为欧拉回路。存在欧拉回路的图被称为欧拉图。

欧拉路的存在性判断:一张无向图中存在欧拉路,当且仅当无向图连通,且起点和终点的度数为奇数,其它节点的度数为偶数。

使用DFS寻找欧拉路的基本思想如下:

DFS寻找到第一个无边可走的节点,则这个节点必定为终点。

接下来由于DFS的递归回溯,会退回终点的上一个节点,继续往下搜索,直到寻找到第二个无边可走的节点,则这个节点必定为欧拉路中终点前最后访问的节点。

于是当通过DFS遍历完整张图后,就可以倒序储存下整个欧拉路。该算法时间复杂度为O(NM),因为一个节点会被遍历多次,且递归层数为O(M)级别,容易栈溢出。可以使用栈模拟递归,且每次访问一条边后删除该边(修改表头,令其指向下一条边)

 

 


动态规划

「笔记」DP从入土到入门 - Luckyblock - 博客园 (cnblogs.com)

【题单】动态规划(入门/背包/状态机/划分/区间/状压/数位/树形/数据结构优化) - 力扣(LeetCode)

 

  1. 构造问题

  2. 拆解子问题

  3. 求解最简单子问题

  4. 通过子问题推当前问题,构建状态转移方程

  5. 判断复杂度

 

 

背包问题

01背包

每个物品最多只能用一次

 

 

 

 

完全背包

每个物品可以使用无数次

 

多重背包

每个物品使用有限次

 

 

 

分组背包

每组有若干个物品,同一组内的物品最多只能选一个。

 

二维费用背包

 

 

求具体方案

求具体方案,空间一般不能优化成二维

 

 

 

求方案数

 

 

 

 

有依赖的背包问题

有 N 个物品和一个容量是 V 的背包。物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。

 

 

 

线性DP

 

数字三角形

 

 

 

最长上升子序列

LIS Longest Increasing Subsequence,最长递增子序列

 

 

最长公共子序列

LCS Longest Common Subsequence,最长公共子序列

 

最长公共上升子序列LCIS

 

 

编辑距离

将字符串a通过以下操作变为字符串b的最小操作次数

  1. 删除一个字符

  2. 插入一个字符

  3. 修改一个字符

 

 

区间DP

定义

区间类动态规划是线性动态规划的扩展,它在分阶段地划分问题时,与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

令状态 f(i,j) 表示将下标位置 ij 的所有元素合并能获得的价值的最大值,那么 f(i,j)=max{f(i,k)+f(k+1,j)+cost}cost 为将这两组元素合并起来的价值。

性质

区间 DP 有以下特点:

合并:即将两个或多个部分进行整合,当然也可以反过来;

特征:能将问题分解为能两两合并的形式;

求解:对整个问题设最优值,枚举合并点,将问题分解为左右两个部分,最后合并两个部分的最优值得到原问题的最优值。

 

一维

石子合并

n个数a[1]~a[n]排成一排,进行n-1次合并操作,每次操作将相邻的两堆合并成一堆,并获得新的一堆中的石子数量的和的得分。你需要最小化你的得分。

诺要求环形的,只需将两个a[ ]接在一起。枚举所有长度为n的区间取最值

 

当n很大时,用Garsia–Wachs 算法求解

每次找到第一个a[i-1] < a[i+1]的位置,把a[i-1]和a[i]合并为now,再将now插入到从i开始左边第一个a[k] > now的a[k]后面

 

二维

棋盘分割

将一个 8×8 的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的两部分中的任意一块继续如此分割,这样割了 (n1) 次后,连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)。原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 n 块矩形棋盘,并使各矩形棋盘总分的平方和最小,给定n求最小值时多少?

 

 

 

 

计数DP

整数划分

一个正整数 n 可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中 n1≥n2≥…≥nk,k≥1。现在给定一个正整数 n(1<=n<=1000),请你求出 n共有多少种不同的划分方法。

完全背包解法:把1,2,3, … n分别看做n个物体的体积,这n个物体均无使用次数限制,问恰好能装满总体积为n的背包的总方案数

 

另一种解法:dp[i] [j]表示为总和为i,总个数为j的方案数

 

https://codeforces.com/contest/560/problem/E

给定一个H*W的棋盘,其中有n个黑格子不能走,每次只能向下或右走,问从左上走到右下角共有多少种走法? 排序后,令dp[i]表示从左上走到排序后的第i个格子且不经过其他黑格子的走法,则有:

dp[i]=Cxi+yi2xi1j=0i1dp[j]Cxi+yixjyjxixjxi>=xjyi>=yj

 

 

数位DP

数位 DP - OI Wiki (oi-wiki.org)

求区间[l,r]中答案的个数,可以转化为求 F(r) - F(l-1),其中F(x)为区间[1,x]中答案的个数

 

 

[P2602 ZJOI2010] 数字计数 - 洛谷 (luogu.com.cn)

题目大意:给定两个正整数a,b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。

 

 

 

记忆化搜索

建议数位DP使用记忆化搜索做,大部分情况下比递推简单一点。

update(state): 12300->12340

 

XHXJ's LIS - HDU 4352 - Virtual Judge (vjudge.net)

T组询问,每次求区间[L,R]内有多少整数的最长上升子序列长度为K?

考虑到最长上升子序列值域为不会超过9,可以用一个二进制状态压缩表示当前LIS的状态。前导0不能算入LIS,所以参数要传入前导0状态。多开一维K可以节省初始化DP数组的时间

 

试填法

P10958 启示录 - 洛谷 (luogu.com.cn)

只要某数字的十进制表示中有三个连续的 6,即认为这是个魔鬼的数,比如 666,1666,6663,16666,6660666 等等。

给定n,求第n个魔鬼数是多少。

当然也可以使用二分+记忆化搜索:记录详情 (luogu.com.cn)

 

状压DP

状压 DP - OI Wiki (oi-wiki.org)

长方形摆放

求把 N×M的棋盘分割成若干个 1×2 的长方形,有多少种方案。

2411_1.jpg

image-20240521160644123

用二进制j表示第i列状态,如第1列状态为10010,第2列状态为01001,st[1|2] = 11011

 

 

最短Hamilton路径

给定一张 n(n≤20) 个点的带权无向图,点从0∼n−1标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

 

bitset优化

Many Graph Queries(★7) - AtCoder typical90_bg - Virtual Judge (vjudge.net)

给定N个点,M条边的有向图。回答Q个询问:从点a能否到达点b?N,M,Q105

将询问分成Q组,依次处理每组询问。

 

重复覆盖问题

给定n个集合,和一个目标集合,选择最少的集合,使得所选集合的并集=目标集合

时间复杂度O(N2M),诺复杂度过高,可以考虑Dancing Links解决

 

 

树形DP

 

洛谷 P1352 没有上司的舞会

求解一颗有向树的最大权独立集,每条边最多选一个点

我们设 f(i,0/1) 代表以 i 为根的子树的最优解(第二维的值为 0 代表 i 不参加舞会的情况,1 代表 i 参加舞会的情况)。

对于每个状态,都存在两种决策(其中下面的 x 都是 i 的儿子):

  • 上司不参加舞会时,下属可以参加,也可以不参加,此时有 f(i,0)=max{f(x,1),f(x,0)}

  • 上司参加舞会时,下属都不会参加,此时有 f(i,1)=f(x,0)+ai

我们可以通过 DFS,在返回上一层时更新当前结点的最优解。

 

皇宫看守

每个节点至少要连接一个被选择的点,并使所有选择的点总花费最小

dp[i,0] 表示未选择当前点,且选择了其父节点。 dp[i,1] 表示未选择当前点,且选择了至少一个子节点。 dp[i,2] 表示选择了当前点。

 

 

 

树上背包

 

 

 

 

换根DP

树形 DP 中的换根 DP 问题又被称为二次扫描,通常不会指定根结点,并且根结点的变化会对一些值,例如子结点深度和、点权和等产生影响。

通常需要两次 DFS,第一次 DFS 自底向上预处理诸如深度,子树大小,点权和之类的信息,在第二次 DFS 自顶向下开始运行换根动态规划。

 

 

 

 

 

记忆化搜索

记忆化搜索是一种通过记录已经遍历过的状态的信息,从而避免对同一状态重复遍历的搜索实现方式。

因为记忆化搜索确保了每个状态只访问一次,它也是一种常见的动态规划实现方式。

 

滑雪

 

 

DP优化

单调队列优化

  • 加入所需元素:向单调队列重复加入元素直到当前元素达到所求区间的右边界,这样就能保证所需元素都在单调队列中。

  • 弹出越界队首:单调队列本质上是维护的是所有已插入元素的最值,但我们想要的往往是一个区间最值。于是我们弹出在左边界外的元素,以保证单调队列中的元素都在所求区间中。

  • 获取最值:直接取队首作为答案即可。

 

 

数据结构优化

 

线段树优化 P4644 (luogu.com.cn)

给定n个区间以及其花费{ [ l , r ] , c },选择合理的区间使其能够完全覆盖区间[st,ed],并使得总花费最小

将所有区间按右端点排序后,遍历n个区间,对于当前区间l,r,c

dp[r] = min(dp[r] , dp[l-1~r-1] + c)

考虑线段树优化,单点修改,求区间最小值

 

 

树状数组优化 UVA12983 (luogu.com.cn)

在长度为n的数列a[ ]中,求长度为m的严格上升子序列的个数

dp[i,j]表示以a[i]结尾,且长度为j的上升子序列个数

dp[i,j] = dp[k,j1] 其中1 <= k < i && a[k] < a[i]

考虑将a[ ]离散化后建立树状数组,query(id(a[i])-1) 为1~id(a[i])中的dp[k,j1],插入的先后顺序保证了不会重复计算到后面的值

 

 

斜率优化

【学习笔记】动态规划—斜率优化DP(超详细)——辰星凌的博客QAQ

先写出DP方程,例如:dp[i]=min{dp[j]+(s[i]s[j])2+m} 去掉min,对齐进行移项变换为y=kx+b的点斜式。 把含有function(i)funciton(j)的表达式看做斜率k乘以未知数x,含有dp[i]或常数项在b的表达式中,含有function(j)的项在y的表达式中。 dp[j]+s[j]2=2s[i]s[j]+dp[i]s[i]2m 此处 y=dp[j]+s[j]2k=2s[i]x=s[j]b=dp[i]s[i]2m 即找出一个点(s[j],dp[j]+s[j]2),使得b也即dp[i]最大

写出DP方程后,判断能否使用斜率优化,即是否存在 function(i)function(j) 的项,或者 Y(j)Y(j)X(j)X(j)

通过大小于符号或者换bdp[i]的符号结合题目要求(min/max)判断是上凸包还是下凸包。

 

P10979 任务安排 2 - 洛谷 (luogu.com.cn)

dp[i]=min0j<i{dp[j](s+st[i])sc[j]}+st[i]sc[i]+ssc[n]

min函数去掉,把关于j的值dp[j]sc[j]看作变量,其余部分看作常数得到:

dp[j]=(s+st[i])sc[j]+dp[i]st[i]sc[i]ssc[n]

sc[j]为横坐标,dp[j]为纵坐标建立平面直角坐标系,当前点i斜率k为固定值s+st[i],决策候选集合是坐标系中的一个点集,每个决策j都对应着坐标系中的一个点(sc[j],dp[j]),要使dp[i]最小,也就是在前i1个点中选择一个点,使得在k一定的情况下,截距最小,不难发现,答案必然在原点集的一个右下凸包上:

image-20250321162203462

由于本题中t为正整数,st递增也即斜率k递增,每次决策时将队首斜率小于k的弹出,队头即为目标 j 将点i插入前,诺队尾两点和点i形成凹包,则不断将队尾弹出,直到满足凸包。

 

[P5785 SDOI2012] 任务安排 - 洛谷 (luogu.com.cn)

本题,诺k不满足单调性,则需要维护整个凸包,每次决策时只需要在队列中用二分/CDQ/平衡树找到点 j 满足:点j左边的斜率都小于k,右边的斜率都大于k。

 

 

303. 运输小猫 - AcWing题库

对于每只小猫所需要的早出发时间为a[i]=t[i]d[i],排序后对a[ ]建立前缀和数组s[ ]

dp[i][j]表示前i个人运输前j只小猫所需要的最小等待次数。第i个人运输第k+1~j只猫。则有:

dp[i][j]=min{dp[i1][k]+a[j](jk)(s[j]s[k])}

去掉min,移项得:

dp[i1][k]+s[k]=a[j]k+dp[i][j]a[j]j+s[j]

斜率优化O(1)求出k,以k为横轴,dp[i-1][k]+s[k]为纵轴建立坐标系,当前斜率为a[j],坐标轴上每个点为(k,dp[i-1][k]+s[k])

 

其他

环形处理

断环成链,复制拼接

P10957 环路运输 - 洛谷 (luogu.com.cn)

 

二次DP

一次选择N和1断开,另一次选择N和1连接。答案取两次DP的最值

[P6064 USACO05JAN] Naptime G - 洛谷 (luogu.com.cn)

 

滚动数组

简要来说就是通过观察dp方程来判断需要使用哪些数据,可以抛弃哪些数据,一旦找到关系,就可以用新的数据不断覆盖旧的没用的数据来减少空间的使用。还要注意根据数据是否可以直接继承考虑是否需要情况数组

 

利用对自然数取模的周期性

 

 

 

 

状态机DP

4747. DNA序列 - AcWing题库

给定m个DNA序列片段,计算有多少长度为n的DNA序列不包含上述m个片段 0m10,1n2109

 


贪心

贪心 - OI Wiki (oi-wiki.org)

区间问题

区间选点

给定 N 个闭区间 [ai,bi] ,请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。(位于区间端点上的点也算作区间内)

 

区间合并

现给定 𝑛个闭区间 𝑎𝑖,𝑏𝑖(1≤𝑖≤𝑛)。这些区间的并可以表示为一些不相交的闭区间的并。在这些表示方式中找出包含最少区间的方案。

 

 

不相交区间

给定 𝑁 个闭区间 [𝑎𝑖,𝑏𝑖],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。 输出可选取区间的最大数量。

 

 

区间覆盖

给定 N 个闭区间 [𝑎𝑖,𝑏𝑖] 以及一个线段区间 [𝑠,𝑡],请你选择尽量少的区间,将指定线段区间完全覆盖。 输出最少区间数,如果无法完全覆盖则输出 −1。

核心思想:在左端点l都小于a的情况下,取右端点最大的小区间

 

 

区间分组

(某个点)最多同时重叠区间个数

给定 𝑁 个闭区间 [𝑎𝑖,𝑏𝑖],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。输出最小组数。

我们可以把所有开始时间和结束时间排序,遇到开始时间就把需要的教室数cnt加1,遇到结束时间就把需要的教室数cnt减1,在一系列需要的教室个数cnt变化的过程中,cnt的峰值就是多同时进行的活动数,也是我们至少需要的教室数。

如果值域较小,可以写差分

 

(任意长度为d的区间)最多/最少包含不同区间个数(重叠区间的长短并不重要)

 

区间包含

 

 

 

绝对值不等式

货仓选址

在一条数轴上有 𝑁 家商店,它们的坐标分别为 𝐴1∼𝐴𝑁。 现在需要在数轴上(任意一点)建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。 为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

在中位数处建点可以使得答案最小

 

均分纸牌

n个人坐在一排,每人有a[i]张纸牌,每次可将任意数量纸牌给相邻的一个人,求使所有人纸牌数相等的最小操作次数

 

环形均分纸牌

n个人围在一圈,每人有a[i]张纸牌,每次可将1张纸牌给相邻的一个人,求使所有人纸牌数相等的最小操作次数

 

 

 

排序不等式

邻项交换法 证明在任意局面下,任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以“排序”为贪心策略的证明。

诺交换相邻两项不会影响其他项的值,单独分析这两项,找出排序策略cmp

 

耍杂技的牛

奶牛们站在彼此的身上,形成一个高高的垂直堆叠。 这 𝑁 头奶牛中的每一头都有着自己的重量 𝑊𝑖 以及自己的强壮程度 𝑆𝑖。 一头牛支撑不住的可能性取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值,现在称该数值为风险值,风险值越大,这只牛撑不住的可能性越高。 确定奶牛的排序,使得所有奶牛的风险值中的最大值尽可能的小,求出该值。

将所有牛按w+s值从小到大排序时,最大的风险值一定最小

相邻两牛交换不会影响其它牛的风险值,所以只需要分析这两头牛即可

风险值i牛i+1牛
交换前:w[1]+....w[i-1]-s[i]w[1]+...+w[i-1]+w[i]-s[i+1]
交换后:w[1]+...+w[i-1]-s[i+1]w[1]+...+w[i-1]+w[i+1]-s[i]
交换前(化简):s[i+1]w[i]+s[i]
交换后(化简):s[i]w[i+1]+s[i+1]

i牛风险值 -= s, i+1牛风险值 += s+w

 

 

 

 

后悔解法

无论当前的选项是否最优都接受,然后进行比较,如果选择之后不是最优了,则反悔,舍弃掉这个选项;否则,正式接受。如此往复。

 

Luogu P2949 工作调度

给定N个工作,每个工作截止日期为Di,如果能在截止日期前完成则会获得Pi的报酬,每天只能完成一项工作。1N1051Di,Pi109

 

 

 

 


其它

字符与数字转换

ASCII码范围为0~127,注意不要越界,否则会乱码

字符串 <=> 数字

 

 

字符c <=> 数字n

 

大小写转换

 

 

进制转换

stoi k进制转十进制

  • stoi(字符串, 0, k进制) :将一串k进制的字符串转换为 int 型数字。

  • stoll,stoull,stod,stold 同理。

 

十进制转k进制

建议直接手写进制转换函数

 

 

itoa

【注意】 不建议使用 itoa并不是一个标准的C函数,它是Windows特有的,如果要写跨平台的程序,需要用spraint。

【函数原型】char *itoa(int value, char *string, int radix);

【参数说明】 value:要转换的数据。 string:目标字符串的地址。 radix:转换后的进制数,可以是10进制、16进制等,范围必须在 2-36。

 

 

 

 

精度/溢出问题

double等浮点数比较问题,eps_double eps 值-CSDN博客

现在考虑一种情况,题目要求输出保留两位小数。有个case的正确答案的精确值是0.005,按理应该输出0.01,但你的结果可能是0.005000000001(恭喜),也有可能是0.004999999999(悲剧),如果按照printf(“%.2lf”, a)输出,那你的遭遇将和括号里的字相同。

解决办法是,如果a为正,则输出a+eps, 否则输出a-eps

 

两个浮点数之间的比较,eps缩写自epsilon,表示一个小量,但这个小量又要确保远大于浮点运算结果的不确定量。eps最常见的取值是1e-8左右。引入eps后,我们判断两浮点数a、b相等的方式如下:

定义三出口函数如下: int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;}

则各种判断大小的运算都应做如下修正:

传统意义修正写法1修正写法2
a == bsgn(a - b) == 0fabs(a – b) < eps
a != bsgn(a - b) != 0fabs(a – b) > eps
a < bsgn(a - b) < 0a – b < -eps
a <= bsgn(a - b) <= 0a – b < eps
a > bsgn(a - b) > 0a – b > eps
a >= bsgn(a - b) >= 0a – b > -eps

 

 

除法之间比较尽量转换为乘法之间比较,如ab<cd判断改为ad<bc

或者利用乘法逆元判断

 

sqrt

sqrtl返回值为long double类型,精度更高。Yet Another Simple Math Problem - Problem - QOJ.ac

 

 

pow/ceil/floor/round参数类型和返回值类型均为浮点型,可能会导致输出与预期不符而wrong answer

 

有符号整型 - 无符号整型

 

输入输出优化

使用cin/cout会比scanf/printf慢

 

 

 

 

 

 

 

 

交互题

输入由评测机输入,根据输入的内容输出询问,直到确定正确答案,这一类题目,往往限制你交流(或询问)的次数,让你猜出一个东西来,此类问题比较经典的技巧有二分答案、随机化

需要注意的是,如果输出了一些数据,这些数据可能被放置于内部缓存区里,而且或许没有被直接传输给interactor,出现Idleness limit exceeded。为了避免这种情况的发生,需要每次输出时用一种特殊的清除缓存操作。

 

一些语法/标准

 

重载运算符

 

一些可重载运算符的列举

  • 一元运算:+(正号);-(负号);~(按位取反);++--!(逻辑非);*(取指针对应值);&(取地址);->(类成员访问运算符)等。

  • 二元运算:+-&(按位与);[](取下标);=(赋值);> < >= <= == += &=等。

  • 其它:()(函数调用);""(后缀标识符,C++11 起);new(内存分配);,(逗号运算符);<=>(三路比较(C++20 起)等。

实现

重载运算符分为两种情况,重载为成员函数或非成员函数。

当重载为成员函数时,因为隐含一个指向当前成员的 this 指针作为参数,此时函数的参数个数与运算操作数相比少一个。

而当重载为非成员函数时,函数的参数个数与运算操作数相同。

其基本格式为(假设需要被重载的运算符为 @):

 

 

 

Lambda表达式

  • capture list 是捕获列表,用于指定 Lambda表达式可以访问的外部变量,以及是按值还是按引用的方式访问。捕获列表可以为空,表示不访问任何外部变量,也可以使用默认捕获模式 &= 来表示按引用或按值捕获所有外部变量,还可以混合使用具体的变量名和默认捕获模式来指定不同的捕获方式。

  • parameter list 是参数列表,用于表示 Lambda表达式的参数,可以为空,表示没有参数,也可以和普通函数一样指定参数的类型和名称,还可以在 c++14 中使用 auto 关键字来实现泛型参数。

  • return type 是返回值类型,用于指定 Lambda表达式的返回值类型,可以省略,表示由编译器根据函数体推导,也可以使用 -> 符号显式指定,还可以在 c++14 中使用 auto 关键字来实现泛型返回值。

  • function body 是函数体,用于表示 Lambda表达式的具体逻辑,可以是一条语句,也可以是多条语句,还可以在 c++14 中使用 constexpr 来实现编译期计算。

 

 

递归写法

 

值捕获

值捕获的变量在 Lambda 表达式定义时就已经确定,不会随着外部变量的变化而变化。值捕获的变量默认不能在 Lambda 表达式中修改

 

引用捕获

在捕获列表中使用 & 加变量名,表示将该变量的引用传递到 Lambda 表达式中,作为一个数据成员。引用捕获的变量在 Lambda 表达式调用时才确定,会随着外部变量的变化而变化。引用捕获的变量可以在 Lambda 表达式中被修改

 

隐式捕获

在捕获列表中使用 =&,表示按值或按引用捕获 Lambda 表达式中使用的所有外部变量。这种方式可以简化捕获列表的书写,避免过长或遗漏。隐式捕获可以和显式捕获混合使用,但不能和同类型的显式捕获一起使用

 

初始化捕获(init capture):C++14 引入的一种新的捕获方式,它允许在捕获列表中使用初始化表达式,从而在捕获列表中创建并初始化一个新的变量,而不是捕获一个已存在的变量。这种方式可以使用 auto 关键字来推导类型,也可以显式指定类型。这种方式可以用来捕获只移动的变量,或者捕获 this 指针的值。

 

使用例子

作为函数参数,自定义排序准则

 

 

预编译头文件

通过预编译头文件<bits/stdc++.h>,加快编译万能头的时间,以windows下的gcc14.2.0编译器为例

 

 

gcc标准

__int128

__int128 仅仅是 GCC 编译器内的东西,不在 C++标准内,且仅 GCC4.6 以上64位版本支持

数据范围

__int128数据范围 : 212721271 大于1.7e38

unsigned __int128 数据范围 : 02128

输入输出

由于不在 C++ 标准内,没有配套的 printf scanf cin cout 等输入输出,只能手写,请不要与ios::sync_with_stdio(false) 同时使用,否则会造成输入输出混乱。

使用方法

与int、long long 等整型类似,支持各种运算,如+ - * / %、移位<< >>& | ^== > < 等多种操作,可以直接与int进行运算

初始化

可以使用整型范围内的值直接赋初值 如 __int128 a = 114514;

可以使用浮点数赋值,但超出浮点数有效精度的部分赋值不准确, __int128 a = 1e30 结果为 1000000000000000019884624838656 __int128 a = 1e40 诺超出__int128数据范围,则会赋值为最大值,即 21271

如果要自定义赋值为一个很大的数,可以用 __int128 a = (__int128(1) << 126) 的方式 也可以写一个函数,将字符串转为 __int128

 

__cplusplus

不同参数对应的默认c++标准 
1C++ pre-C++98
199711LC++98
201103LC++11
201402LC++14
201703LC++17
202002LC++20
202302LC++23

 

编译时如果存在类似 -std=c++17 的选项,则显式指定了标准;如果未指定,则使用 g++ 默认的标准(取决于版本)。

不同版本的 g++ 默认使用不同的 C++ 标准:使用bash指令gcc --version可以查看g++版本

所有Gcc版本对C和C++的支持情况(超详细版本)-CSDN博客

 

 

文件读写

 

时间复杂度

数据范围  
20指数级别dfs+剪枝、状压dp
100O(n^3)floyd、dp、高斯消元、矩阵
1000O(n^2) ~ O(n^2logn)dp、二分,朴素版Dijkstra、Bellman-Ford、二分图
1e4O(nn)块状链表、分块、莫队、双指针
1e5nlognsort、线段树、树状数组、set/map、heap、拓扑排序、dijkstra、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
1e6O(n)~O(nlogn)单调队列、hash、双指针扫描、并查集,kmp、AC自动机,常数比较小的O(nlogn)的做法:sort、树状数组、heap、dijkstra、spfa
1e7O(n)双指针扫描、kmp、AC自动机、线性筛素数
1e9O(n)判断质数、求欧拉函数
1e18O(logn)最大公约数、快速幂、数位DP
1e1000O((logn)^2)高精度加减乘除
1e100000O(logk*loglogk)高精度加减、FFT/NTT

 

i=1nj=1n(aiaj)  [ij]=i=1n(2aisumi1)

i=1nj=i+1n(aiaj)=(sum2i=1nai2)/2

i=1nj=1n(ai+aj)=sumn2 ,诺有k求和,则答案为sumnk1k

i=1nj=i+1n(ai+aj)=sum(n1)

i=1nj=1ngcd(i,j)=d=1nnd2φ(d)ϕ()为欧拉函数,可以用整除分块进一步优化为O(n)

 

 

握手定理

n个人握手,每人握手m次,握手总次数S=nm2 给定无向图G=(V,E),有deg(V)=2E,图中所有结点的度数之和等于边数的两倍

 

分块打表

image-20250802183956804

Harmonic Number - LightOJ 1234 - Virtual Judge (vjudge.net)

i=1n1i1n108,最多104组测试样例。

如果直接用前缀和预处理,数组需要开到10^8但空间不允许

我们可以每 len 块为一组,每一块预处理。查询时,对于在表中的整块部分直接计算,其它部分暴力枚举

 

随机数生成

 

 

 

.vimrc

 

OI

OIer