最近公共祖先(LCA)
最近公共祖先
最近公共祖先(LCA)指的是两个或多个点的公共祖先中离根最远的一个。
对于 LCA 问题,有多种算法可以求解。
倍增
过程
先将树进行一遍 DFS,预处理出 fau,i\textit{fa}_{u,i}fau,i 表示节点 uuu 的 2i2^i2i 级祖先。
接下来对于两个节点 u,vu,vu,v,先根据两个节点的深度之差 ∣depu−depv∣|\textit{dep}_u - \textit{dep}_v|∣depu−depv∣,将较深的节点用 fa\textit{fa}fa 数组,通过 O(logn)O(\log n)O(logn) 次操作跳到一样深。
当两个节点一样深之后,若此时两个节点相同,直接返回。
否则需要找到最小的 ddd,使得 uuu 和 vvv 的 ddd 级祖先相同。为次,我们从最大的 iii 开始,依次递减到 000,每次如果 fau,i≠fav,i\textit{fa}_{u,i}\ne \textit{fa}_{v,i}fau,i=fav,i,就将 u←fau,i,v←fav,iu\gets \textit{fa}_{u,i}, ...
数位 DP
数位 DP
数位 DP 是一种快速求解出在 [1,n][1,n][1,n] 满足条件的数个数的方法。其特点有数据范围一般均为 101810^{18}1018 次方量级(甚至更高)。
对于这种问题,我们是有一套通用的记忆化搜索模板的。
记忆化搜索
数位 DP 有不使用记忆化搜索的递推写法,但是记忆化搜索写法具有好实现的优点,而且一般记忆化搜索是可以做所有数位 DP 的题目的。
我们从一道题目出发来讲解通用的记忆化搜索方法。
示例题目
LOJ#10164. 「一本通 5.3 例 2」数字游戏
给定两个正整数 aaa 和 bbb,求在 [a,b][a,b][a,b] 中的所有整数中,有多少个数满足从左到右各位数字成小于等于的关系。
1≤a≤b≤231−11\le a\le b\le 2^{31}-11≤a≤b≤231−1。
解法
首先我们需要知道,对于区间 [a,b][a,b][a,b] 来说,可以拆分成求 [1,b][1,b][1,b] 和 [1,a−1][1,a-1][1,a−1] 的答案,然后将结果相减,因此后面我们只需考虑求出 [1,n][1,n][1,n] 的所有整数中各数码出现个 ...
最小生成树专题
生成树
定义连通无向连通图 GGG 的生成树是有 GGG 的一个树子图。
最小生成树
相关概念与性质
定义带权无向图的最小生成树是其各边边权和最小的生成树。
定义带权无向图的瓶颈生成树该图生成树中,最大的边权最小的生成树。
最小生成树一定是瓶颈生成树,瓶颈生成树不一定是最小生成树。
边权各不相同的图最小生成树唯一。
一张图所有最小生成树同一权值边数量相同。
一张图上两点之间所有路径最大边的最小值 = 最小生成树上两点路径最大边。
算法
一般有三种算法可以用来求最小生成树,实际做题时应根据题目灵活选用适合的算法。
Kruskal
将边从小到大排序,依次遍历,如果当前边的两个端点之间没有连通就加入这条边,最后加入的边构成的就是最小生成树。
用并查集维护连通性。
复杂度 O(mlogm)O(m\log m)O(mlogm)。
模板代码:
12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;const int N ...
矩阵树定理 & BEST 定理
行列式
定义
对于 n×nn\times nn×n 的方阵 AAA
[a1,1a1,2⋯a1,na2,1a2,2⋯a2,n⋮⋮⋱⋮an,1an,2⋯an,n]\begin{bmatrix}
a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\
a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & \cdots & a_{n, n}
\end{bmatrix}
a1,1a2,1⋮an,1a1,2a2,2⋮an,2⋯⋯⋱⋯a1,na2,n⋮an,n
定义其行列式 det(A)=∑p(−1)π(p)∏i=1nai,pi\det(A) = \displaystyle \sum_{p}(-1)^{\pi(p)}\prod_{i=1}^n a_{i,p_i}det(A)=p∑(−1)π(p ...
CF2086E Zebra-like Numbers 题解
题意
称在二进制下 010101 交替且最高位和最低位都是 111 的数为斑马数,如 (1)2=1,(10101)2=21(1)_2=1,(10101)_2=21(1)2=1,(10101)2=21。
对一个数 nnn 来说,定义它的价值为最小的正整数 ppp,使得 nnn 能表示成 ppp 个斑马数(可以相同也可以不同)。
求 [l,r][l,r][l,r] 中价值为 kkk 的数个数。
l,r,k≤1018l,r,k\le 10^{18}l,r,k≤1018。
题解
考虑一个数的最优分解,即分解成最少个斑马数之和。
设第 iii 个斑马数为 ziz_izi,即 z1=1,z4=85z_1=1,z_4=85z1=1,z4=85,分解中第 iii 个斑马数的次数为 cic_ici。
假设某一个数的最优分解中含有了某个斑马数 zi(i>1)z_i(i>1)zi(i>1) 至少 555 次以上,那么可以发现 5zi=zi+1+4zi−15z_i = z_{i+1} + 4z_{i-1}5zi=zi+1+4zi−1,不会使答案变劣。
若含有了 111 至 ...
Z 函数(扩展 KMP 算法)
约定下标从 0 开始。
Z 函数
定义 z[i]z[i]z[i] 表示字符串 sss 和 s[i..]s[i..]s[i..](即从 iii 开始的部分)的最长公共前缀。
我们可以在 O(n)O(n)O(n) 复杂度内计算出一个字符串的 Z 函数。(当然也可以哈希单 log 完成)
假设我们已经求出了 z[0],z[1],…,z[i−1]z[0],z[1],\ldots,z[i-1]z[0],z[1],…,z[i−1],对于每个 iii,将 [i,i+z[i]−1][i,i+z[i]-1][i,i+z[i]−1] 称为它的 Z-box。
我们找出 1∼i−11\sim i-11∼i−1 中右端点最靠右的 Z-box,记作 [l,r][l,r][l,r]。(初始时 l=r=0l=r=0l=r=0,不计 z[0]z[0]z[0] 的 Z-box)
分类讨论:
i≤ri\le ri≤r:根据 Z 函数定义可知 s[0..r−l]=s[l,r]s[0..r-l]=s[l,r]s[0..r−l]=s[l,r],则 s[i..r]=s[i−l,r−l]s[i..r]=s[i-l,r-l]s[i. ...
动态最短路专题
包括删边,删点,修改边权,加边,查询最短路一类问题。
一般图多源最短路
一般图的多源的删边最短路由于受到 Floyd O(n3)O(n^3)O(n3) 的限制,做法一般比较单一。
删边,多源最短路
题目
ABC375F Road Blocked
给定一个有 nnn 个点,mmm 条边的带权无向图,有 qqq 个查询,类型如下:
1 i:删除第 iii 条边;
2 x y:求 xxx 到 yyy 的最短路长度(无法到达输出 -1)。
数据范围:n≤300,m≤(n2)n\le 300, m\le \binom n 2n≤300,m≤(2n),删边不超过 300300300 次。
解法
看到删边不超过 300300300 次启发我们使用 Floyd O(n3)O(n^3)O(n3) 解决这个问题。Floyd 能处理新加入一条边,但是比较难做删边,所以我们离线之后倒过来处理,就只需要加边和求任意两点最短路。
怎么用 Floyd 更新一条边对多源最短路的贡献?
假设这条边是 (u,v)(u, v)(u,v),长度为 www,di,jd_{i,j}di,j 表示 i,ji,ji,j 之间 ...
Butterfly 魔改 - 在 404 页面添加搜索链接
概述
目标
由于修改过一次 permalink,但没有设定重定向,导致之前的链接会出现 404 问题。
_config.yml12- permalink: :year/:month/:day/:title/+ permalink: posts/:hash/
我们希望能够添加一个搜索链接,让用户搜索找到新的页面。
效果图:
需要修改的文件
themes\butterfly\layout\includes\404.pug(用于修改 404 页面内容)
themes\butterfly\source\js\search\local-search.js(用于自动填入搜索内容)
修改 404 页面
themes\butterfly\layout\includes\404.pug1234567891011121314151617181920212223242526272829303132333435363738394041- var top_img_404 = theme.error_404.background || theme.default_top_img#body-wrap.er ...
CF2066E Tropical Season 题解
提供一个比较好写的 1 log 做法。
题意
有 nnn 个桶,容积无限大,知道每个桶初始有 aia_iai 千克的水。现在有一个桶恰额外含有 0.1790.1790.179 千克的毒药,进行任意次如下两种操作:
选择两个桶 AAA,桶 BBB,比较重量,知道哪边重或一样重;
选择桶 AAA,桶 BBB,从 AAA 桶中倒 xxx 千克水(xxx 不一定是整数)进入 BBB 桶,要求:
※ AAA 桶必须不含毒药;
※ AAA 桶至少要含有 xxx 千克的水。
判断是否能唯一确定哪个桶装着毒药,输出 Yes/No。
现在会进行 qqq 次修改,每次的修改为增加一个初始水量为 bbb 的桶,或删去一个初始水量为 bbb 的桶(保证存在),修改持续。
每次修改后,输出 Yes/No,代表当前情况是否能判断哪个桶装着毒药。
n,q≤2×105,ai,b≤106n,q\le 2\times 10^5, a_i,b\le10^6n,q≤2×105,ai,b≤106。
解法
注意到操作 1 只有两个桶装的水是同样重的才有用(要不然有没有毒药不会影响结果),而且操作 2 选择的桶 AAA 一 ...
LOJ6077 「2017 山东一轮集训 Day7」逆序对
题意
LOJ6077 「2017 山东一轮集训 Day7」逆序对
给定 n,kn,kn,k,求长度为 nnn 的逆序对数恰为 kkk 的排列个数,对 109+710^9+7109+7 取模。
n,k≤105n,k\le 10^5n,k≤105。
生成函数做法
先考虑一个 O(nk)O(nk)O(nk) 的朴素 dp。考虑按照位置一个一个插入数,假设当前插入第 iii 个数,根据插入的数与前面的数的大小,可以构成 [0,i−1][0,i-1][0,i−1] 个逆序对。
设 dpi,jdp_{i,j}dpi,j 表示长度为 iii 的有 jjj 个逆序对的排列数量:
dpi,j=∑max(0,j−i+1)≤k≤jdpi−1,kdp_{i,j} = \sum_{\max(0,j-i+1)\le k\le j}dp_{i-1,k}
dpi,j=max(0,j−i+1)≤k≤j∑dpi−1,k
用前缀和就可以做到 O(nk)O(nk)O(nk) 了。
我们考虑写出这个问题的生成函数,xpx^pxp 的系数表示逆序对个数为 ppp 的排列个数。
一开始 F1=1F_1 = 1F1=1, ...