Q779’s Blog

最小树形图 Tarjan的DMST算法 前言 网上怎么都是朱刘算法啊？ 那我来写一篇 Tarjan 的 DMST 算法吧 qwq 注：本文的DMST采用左偏树+并查集实现 时间复杂度为 \(O(E+V\log E)\) 如果采用斐波那契堆则为 \(O(E+V\log V)\) 由于差别不大（其实是q779不会斐波那契堆），因此本文不会提及 如果需要模板题数据的可以私信我（ qwq 最小树形图 模板题：P4716 【模板】最小树形图 题目描述 给定包含 \(n\) 个结点， \(m\) 条有向边的一个图。试求一棵以结点 \(r\) 为根的最小树形图，并输出最小树形图每条边的权值之和，如果没有以 \(r\) 为根的最小树形图，输出 \(-1\)。 1.朱刘算法（Edmonds算法） 有向图上的最小生成树（Directed Minimum Spanning Tree）称为最小树形图。 常用的算法是朱刘算法（也称 Edmonds 算法），可以在 \(O(nm)\) 时间内解决最小树形图问题。 注意到有根最小树形图满足从根结点可以到达任意结点的性质 算法流程： 求出图中的最短弧集合...

洛谷P3919 【模板】可持久化线段树 1（可持久化数组） 题解 题目链接：P3919 【模板】可持久化线段树 1（可持久化数组） 题意：如题，你需要维护这样的一个长度为 NN 的数组，支持如下几种操作 在某个历史版本上修改某一个位置上的值 访问某个历史版本上的某一位置的值 此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组） 解法一、主席树 注意到历史版本+单点修改，容易想到可持久化线段树 和区间 \(k\) 小值稍微有些不同 时间复杂度 \(O(n\log n)\) 本题的数据有点极限，我的写法开 long long会挂 😓 代码如下 #include <bits/stdc++.h> using namespace std; // #define int long long // #define INF 0x3f3f3f3f3f3f3f3f #define gc() readchar() #define pc(a) putchar(a) #defi...

洛谷P1129 [ZJOI2007] 矩阵游戏 题解 题目链接：P1129 [ZJOI2007] 矩阵游戏 题意：给定一张有黑白棋子的正方形棋盘，问存不存在解法使得经过若干次交换行或列的操作后，左上角至右下角的对角线上所有的点放着黑色棋子 说实话第一眼看到这个题我连暴力都不知道咋打 这道题的建模挺有意思的 对于 \(\forall i \in \mathbb{Z}, 1\le i \le n\) ，要求第 \(i\) 行第 \(i\) 列为黑色 不妨可以看作行结点 \(i\) 与列结点 \(i\) 之间有一条无向边（显然没有权重） 则交换行 \(u,v\) 的操作，就可以看作重命名的操作 问题就可以转化为行结点集 \(V_a\) 与列结点集 \(V_b\) 求二分图最大匹配 当最大匹配值为 \(n\) 时，存在解 时间复杂度 \(O(Qn^2)\) ，\(Q\) 为数据的组数 代码如下（忽略那个快读，其实没有什么大用处 qwq） #include <bits/stdc++.h> using namespace std; #define int long long #de...

kd-tree(KDT) 时间复杂度证明 kd-tree 是一种可以高效处理 \(k\) 维空间的数据结构 在算法竞赛类的题目中一般有 \(k=2\) 还有个比较有趣的结论，当 \(k=1\) 时其实它就是一棵线段树 下文中的 \(n\) 为kd-tree中的结点数量， \(k\) 为kd-tree的维度 一、建树 一般建树有三种 随机划分（玄学） 轮换划分：每个维度轮着划分 方差划分：优先划分方差较大的维度 我可不想分析玄学的划分 1. 轮换划分 显然有递推式 \(T(n) = 2T(n/2) + O(n)\) 根据主定理，有 \(a=2,b=2,\log_b{a}=1,f(n)=O(n)\) \(\because \exists \epsilon \ge 0\) 使得 \(f(n) = \Theta(n^{\log_b{a}}\log^{\epsilon}n)\) ，此时 \(\epsilon = 0\) \(\therefore T(n) = \Theta(n\log n)\) 2. 方差划分 注意到 \(T(n) = 2T(n/2) + O(kn)\) 因此时间复杂...

洛谷P4357 [CQOI2016]K 远点对 题解 题目链接：P4357 [CQOI2016]K 远点对 题意：给定平面内 \(n\) 个点的坐标，求欧几里德距离第 \(k\) 远的点对 本题的正解应该是旋转卡壳、分治等算法，不会 而kd-tree上搜索在本题中相当于搜索+天然剪枝 因此假装这就是个kd-tree的模板题 为什么使用方差呢？因为方差很好描述了数据的离散程度 每次选择方差较大的进行划分，是因为选择较小的很可能导致另一维的方差过高 因此这样就很难保证树高 对于本题中的 \(k\) 大值怎么去维护呢？ 我们可以弄一个有 \(k\) 个结点的小根堆，这些结点默认为一个极小值（本题中设为 \(0\) 就可以了） 这样在堆首的就是第 \(k\) 大值了 这样我们只要枚举每个点，分别搜它们所对应的点，统计它们的贡献 容易发现，因为是无序的点，因此这些点之间的距离会被计算 \(2\) 次，那我们只要把 \(k\) 变成 \(2k\) 就好了 时间复杂度 比较玄学，可以分析的是建树 \(O(n\log n)\) 代码如下 #include <bits/stdc++.h>...

CF1200E Compress Words 题解 题目链接：CF1200E Compress Words 题意：给定一堆字符串，依次插入答案串尾部，每次删掉答案串的后缀 与 待插入串的前缀的最大匹配串 解法一 KMP 这个解法常数比较大 可以想到，暂时把待插入串放到答案串前，然后跑一遍KMP 最后一个值就是新串的最长前后缀，也就是我们要求的最大匹配串的长度 由于直接拼接新串会导致某些时候答案超出原长 因此我们要在它们拼接的地方加上一些非字符集的字符或者乱七八糟的字符 注意不能自带border 而这样的算法还是不行的，因为答案串中有很多字符其实用不到 因此我们只要截取答案串后面的拼接即可 时间复杂度 \(O(\sum |s_i|) = O(n)\) 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e6+5) int n,fail[N],len1,len2; char ans[N]...

洛谷P2387 [NOI2014] 魔法森林 题解 题目链接：P2387 [NOI2014] 魔法森林 题意：每条边有边权 \(a,b\) 两个，求 \(1\) 到 \(n\) 的路径使得所经过的边中 \(\max\{a\}+\max\{b\}\) 尽可能小 由于下面写了很多解题思路上的东西，导致有些冗长，因此这里先放简化版题解 如果不理解可以跳过这一段简化版，直接看下面的完整版 简化版 因为不方便同时处理 \(a,b\) 两维，我们可以枚举 \(a\) 然后尽可能的选择较小的 \(b\) 这个 \(b\) 的一定在连接 \(1\) 和 \(n\) 的最小生成树上 因此这道题就是个动态加边的 LCT 裸题了 代码在后面，时间复杂度 \(O(m\log m)\) 完整版 这种“二维”的问题常见的解法就是枚举第一维，然后优化第二维 不知道这个套路也没关系 首先看到这个题意，最大值的和最小，显然我们无法确定这是个多大的值 似乎可以二分？但是再一想，二分 \(a+b\) 肯定是不对的 那先二分 \(a\) 再二分 \(b\) （二分套二分）呢？ 看上去似乎也不行，这个 \(b\)...

洛谷P4234 最小差值生成树 题解 题目链接：P4234 最小差值生成树 题意：给定一个点标号从 \(1\) 到 \(n\) 的、有 \(m\) 条边的无向图，求边权最大值与最小值的差值最小的生成树，图可能存在自环 这个题不太好利用kruskal来维护（其实kruskal来做就是暴力枚举） 考虑使用LCT动态维护生成树 可以先回顾一下如何用LCT来求解最小生成树 link 因为边之间没有什么本质区别，我们可以先把边按大小排序，以保证编号越小的边点，权值越小 然后我们可以从小到大枚举生成树中的最大值（从大到小其实是类似的） 那么我们只要保证生成树中边权的最小值尽可能的大即可 也就是说，在枚举最大边的时候，如果两结点未连通，我们可以直接将这两点连接 如果已经连通，那么就将当前生成树中x,y所成的链中的最小边扔掉，然后用最大边连接这两点 显然这个最小值就是生成树中编号最小的那一个，而且随着枚举会单调不降，那我们可以整个变量记录它，而由于它的单调不降性质，寻找这个最小值是不会影响到复杂度的 对于已经不在生成树的边（包括构成自环和被更新掉的边），我们直接让那个维护最小值的变量跳过它...

LCT求解最小生成树 前言 最小生成树模板： P3366 【模板】最小生成树 朴素的kruskal为主流最小生成树算法 而LCT(link cut tree)也是可以维护最小生成树的 由于LCT动态维护最小生成树，加上常数较大 在实际测试中比kruskal慢了很多倍 最小生成树 维护结点的连通性 可以看看这个 显然我们不是把它和kruskal连用，那样反倒变成了 \(\log^2\) 的劣解了 而LCT它是动态的，因此难以使用树链剖分的做法，将边权映射到点权上 那么我们可以把通过建“边点”将边权转化为点权 所谓的边点指直接将每条边当做点，那么连边的操作就变成了 w[idx+n]=z; // 记录边权 ,idx = 1 to m link(x,idx+n),link(idx+n,y); // 和边所连接的两结点与该边所建结点相连 因为没有对边权排序，那如果 x,y 已经连通怎么办呢？ 由于x,y都在LCT上，因此我们可以维护它们所成的链中最大的那一条边 如果当前处理到的边比那条边边权更小，就可以将那条极大边断掉 如何断边？直接t[t[now].ch[0]].fa=t[t[now]...

洛谷P2147 [SDOI2008] 洞穴勘测 题解 题目链接：P2147 [SDOI2008] 洞穴勘测 题意：给定若干个点，动态连接（无向边），询问连通性 由于它有删边的操作，因此用并查集并不可行 于是想到LCT（？ 由于LCT有 find_root() 操作 说明LCT确实可以动态判定连通性 那么就变成简单的模板题了（ 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e4+5) int n,Q; namespace LCT { struct node { int ch[2],fa,tag; }t[N]; #define isroot(x) ((t[t[x].fa].ch[0]!=x)&&(t[t[x].fa].ch[1]!=x)) void pushr(int x) ...

洛谷P1501 [国家集训队]Tree II 题解 题目链接：P1501 [国家集训队]Tree II 题意：树上区间加&乘&link&cut 显然LCT模板题，因为树链剖分并不能维护动态连边 考虑如何维护区间乘 不知道大家有没有做过洛谷的线段树2，没做过也没关系 对于每个结点，维护一个 \(kx+b\) 的懒标记 每次做乘法就整体（包括两个部分）乘上 \(c\) ，每次做加法就直接加上 \(c\) 就可以维护标记了 由于加法的维护需要知道这条链的长，那我们只要维护每个结点的子树大小即可 那么这题就很容易解决了（就是函数有点多） 时间复杂度 \(O(n\log n)\) #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define gc() getchar() #define pc(a) putchar(a) #define N (int)(1e5+5) const int mod=51061; ...

AT4284 [ABC116C] Grand Garden & 洛谷 P1969 P3078 P5019 题解 题目链接：AT4284 P1969 P3078 P5019 题意：若干次区间减一，使所有数相等，求最小次数 这几道题就是一个std编出来的吧 \(😅\) 对于相邻两数 \(a_i>a_{i-1}\) ，显然在一次操作中将它们同时减去是最优的 对答案的贡献为 \(a_i-a_{i-1}\) 推广一下其实是等价的，故时间复杂度 \(O(n)\) 即可解决 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(1e5+5) int n; int a[MAXN],ans; signed main() { ios::sync_with_stdio(0); cin >> n; for(int i=1; i<=n; i++) { cin >> a[i]; ...