Thy's Blog

差分约束系统与 2-SAT 将两者放在一起的原因是两者本质十分相像： 差分约束用于解多个二元不等式，其中要求变量为实数，不等式表示两个变量之差。 2-SAT 则用来解决布尔类型方程，每个方程同样只涉及两个变量。 差分约束系统 以模板题 P5960 【模板】差分约束 - 洛谷 为例，差分约束本质上是由多个形如： {xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} ⎩⎨⎧​xc1​​−xc1′​​≤y1​xc2​​−xc2′​​≤y2​⋯xcm​​−xcm′​​≤ym​​ 组成的不等式组，对这个不等式进行求解或判断是否无解（或无穷解）。 问题转化 既然知道差分约束与最短路有关，我们考虑转化问题，我们在不等式组中单独拎出一个式子： xi−xj≤kx_i - x_j \le k xi​−xj​≤k 钦定 xix_ ...

前缀函数 前缀函数通常称为 border，一个字符串 SSS 的 border 定义为它的一个前缀子串 t(t≠S)t(t \ne S)t(t=S)，满足 ttt 既是 SSS 的前缀，也是 SSS 的后缀。下文的 border 均为 SSS 的最长 border 长度。 简单来说，对于一个字符串 S=abcabcdS = \texttt{abcabcd}S=abcabcd（下标从 111 开始），它的前缀函数为 [0,1,0,1,2,2,3][0, 1, 0, 1, 2, 2, 3][0,1,0,1,2,2,3]。 计算方法 单纯暴力 从左向右遍历一遍，每次循环一次长度，每次检查遍历一遍子串，复杂度为 O(n3)O(n^3)O(n3)。 边界优化 从左向右遍历的过程中，子串的大小每次只会增加 111，而原先的前缀不会改变，因此 borderiborder_iborderi​ 的长度最多只会比 borderi−1border_{i - 1}borderi−1​ 大 111，在这种情况下： S[i]=S[borderi−1+1]⇒S[1…borderi−1]=S[i−1−borderi ...

Manacher 算法 例题：P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 给出一个只由小写英文字符 a,b,c,…y,z\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt za,b,c,…y,z 组成的字符串 SSS ,求 SSS 中最长回文串的长度 。 Manacher 算法是一种快速找到字符串中所有回文串长度的线性算法。 奇偶回文长度统一处理 回文串存在两种形式：形如 abba\texttt {abba}abba 的偶数回文串以及形如 abbcbba\texttt {abbcbba}abbcbba 的奇数回文串。 我们令 fi(1≤i≤∣S∣)f_i (1 \le i \le |S|)fi​(1≤i≤∣S∣) 表示以第 iii 个字符串为中心形成的最长回文串，显然偶数回文串就不好处理了。 我们将每个字符之间用一个无关字符代替，例如 abba←!a!b!b!a!\texttt{abba} \leftarrow \texttt{!a!b!b!a!}abba←!a!b! ...

线段树 线段树是 OI 竞赛中最强大的数据结构之一，可以用来维护和、积以及最值等具有合并性质的信息。 一般线段树 P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 以模板一为例： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667class Segment_Tree{ #define lc u << 1 #define rc u << 1 | 1private: struct Tree { int l, r, sum, tag; inline int len() { return r - l + 1; } inli ...

Statement 给定一个 H×WH \times WH×W 的网格以及 NNN 个硬币的位置，从 (1,1)(1, 1)(1,1) 开始每次往下或往右移动一个单元格，求到达 (H,W)(H, W)(H,W) 单元格能拾取的最多硬币以及该路径。 Solution 考虑如何转化问题：由于每次只能向下或者向右走，则运动路径在二维平面上看来必然是在横纵坐标上分别非严格单调递增的。换句话说，第 iii 个硬币可以被捡到当且仅当上一个捡到的硬币 jjj 满足 Xj≤XiX_j \le X_iXj​≤Xi​ 且 Yj≤YiY_j \le Y_iYj​≤Yi​，很显然的二维偏序求最长上升子序列问题。 题目中的 H,W≤2×105H,W \le 2 \times 10^5H,W≤2×105，朴素的 O(n2)O(n^2)O(n2) 求法无法通过，我们采取更为优秀的二分查找法，定义 fif_ifi​ 表示满足长度为 iii 的非严格上升子序列的末尾的最小值，遍历序列时找到 fff 数组中最后一个小于等于当前数的下一个数（即大于待选数的第一个数），将这个数替换进去（因为它满足可以构成长度为 iii 的子 ...

网络流简介 基本定义 网络（Network）在图论中指一个有向图 G=(V,E)G=(V,E)G=(V,E)，图上的每一条边都有一个值，叫做容量（Capacity），也有两个特殊点：源点（Source）和汇点（Sink）。 而对于一张网络 GGG，流（Flow）指的是一个函数 fff，f(u,v)f(u, v)f(u,v) 表示边 u→vu \to vu→v 经过的流量，一个点 uuu 的净流量可以表示为 F(u)=∑x∈Vf(u,x)−∑x∈Vf(x,u)F(u) = \textstyle{\sum_{x \in V}} f(u, x) - \textstyle{\sum_{x \in V}} f(x, u)F(u)=∑x∈V​f(u,x)−∑x∈V​f(x,u) 。 每一张网络的流从源点 ststst 出发，流向汇点 ededed，对于流经的每一条边，都满足以下性质： 对于一条边 u→vu \to vu→v 的容量 c(u,v)c(u, v)c(u,v)，始终有：0≤f(u,v)≤c(u,v)0 \le f(u, v) \le c(u, v)0≤f(u,v)≤c(u,v)。 ...

边双连通分量 定义 在一张联通的无向图中，对于任意两点 uuu 和 vvv​，删去两点之间任意一条边，都无法使其不连通（即连通数不变），我们就说这两点是边双连通。 对于一个无向图中的 极大 边双连通的子图，我们称这个子图为一个 边双连通分量。 根据 【笔记 / 模板】割点和桥 中可知，如果一张图是一个边双连通分量，那么这张图中必然不存在桥（割边），我们可以使用 Tarjan 求解割边的方法得到一张图的所有边双连通分量。 解法一 先用 Tarjan 预处理出图中所有的桥，再用 DFS 跑一边即可。 12345678910111213141516171819202122232425262728293031int id[N], dcc_cnt;vector<vector<int>> vec;void tarjan(int ver, int edge){ dfn[ver] = low[ver] = ++ timestamp; for (int i = h[ver]; ~i; i = ne[i]) { int to ...

割点 对于一张无向图 G=(V,E)G=(V,E)G=(V,E)，使得 H 是 G 的连通子图，且不存在 FFF 满足 H⊊F∈GH \subsetneq F \in GH⊊F∈G 且 FFF 为连通图，则称 HHH 是 GGG 的一个连通块/连通分量（connected component），又叫极大连通子图。 由此，我们可以对割点做出如下定义： 对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。 Tarjan 处理过程 与有向图的强连通分量相似，我们定义如下两个重要数组： dfn[]：表示深度优先遍历图时节点 uuu 被遍历到的次序，即时间戳。 low[]：节点 uuu 在不通过父亲走过的路的情况下可以到达节点的最小时间戳。 根据割点的定义可知，如果一个节点 ververver 是割点，那么必然有一个处于其 DFS 序子树内的节点 tototo 使得： lowto≥dfnverlow_{to} \ge dfn_{ver} lowto​≥dfnver​ 这个意思指的是无论如何走，tototo 都无法到达 ververver ...

Description 给定一个 n×mn \times mn×m 的矩阵，一共 kkk 次操作，在相应的行或者列上乘上一个数，求这 kkk 次操作后的和，答案对 109+710^9 + 7109+7 取模。 这里给出一种复杂度仅为 O(k)O(k)O(k) 的做法。 Solution 我们令 rowirow_irowi​ 表示矩阵第 iii 行被乘上的系数，colicol_icoli​ 表示矩阵第 iii 列被乘上的系数，显然一开始均为 111。 根据题意不难发现，矩阵中的权值 Ai,jA_{i, j}Ai,j​ 最后的值将为这一行被乘的总积再乘上这一列被乘的总积。由此可以得出答案： ans=∑i=1n∑j=1mAi,j×rowi×colj\begin{align*} ans &= \sum_{i = 1}^{n}\sum_{j = 1}^{m} A_{i, j} \times row_i \times col_j \end{align*} ans​=i=1∑n​j=1∑m​Ai,j​×rowi​×colj​​ 由于 Ai,jA_{i, j}Ai,j​ 的初值与其位置有关， ...

树链剖分 树链剖分的基本思想 通过将树分割成链的形式，从而把树形变为线性结构，减少处理难度。 树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作「实链剖分」），大多数情况下（没有特别说明时），「树链剖分」都指「重链剖分」。 树链有如下几个特征： 一棵树上的任意一条链的长度不超过 log⁡2n\log_2 nlog2​n，且一条链上的各个节点深度互不相同（相对于根节点而言）。 通过特殊的遍历方式，树链剖分可以保证一条链上的 DFS 序连续，从而更加方便地使用线段树或树状数组维护树上的区间信息。 重链剖分 重链剖分的基本定义 重链剖分，顾名思义，是一种通过子节点大小进行剖分的形式，我们给出以下定义： 重子节点：一个非叶子节点中子树最大的子节点，如果存在多个则取其一。 轻子节点：除了重子节点以外的所有子节点。 重边：连接任意两个重儿子的边。 轻边：除了重边的其他所有树边。 重链：若干条重边首尾相连而成的一条链。 我们将落单的叶子节点本身看做重子节点，不难发现，整棵树就被剖分成了一条条重链。 需要注意 ...