Q779’s Blog

洛谷P3194 [HNOI2008]水平可见直线 题解 题目链接：P3194 [HNOI2008]水平可见直线 题意：在$ x-y$ 直角坐标平面上有 \(n\) 条直线 \(L_1,L_2,…L_n\)，若在 \(y\) 值为正无穷大处往下看，能见到 \(L_i\) 的某个子线段，则称 \(L_i\) 为可见的，否则 \(L_i\) 为被覆盖的。 例如，对于直线: \(L_1:y=x\); \(L_2:y=-x\); \(L_3:y=0\); 则 \(L_1\) 和 \(L_2\) 是可见的，\(L_3\) 是被覆盖的。给出 \(n\) 条直线，表示成 \(y=Ax+B\) 的形式(\(|A|,|B| \le 500000\))，且 \(n\) 条直线两两不重合，求出所有可见的直线。 一条直线C被另外两条直线A和B所覆盖 它的充分必要条件为直线C在A,B交点处的值更小一些 反之，直线C也可能对答案有贡献 那么交点的坐标是什么呢？ \[ A_1x+B_1=A_2x+B_2\\ x=\dfrac{B_2-B_1}{A_1-A_2} \] 则 \[ A_1\dfrac{B_2-B...

洛谷P3236 [HNOI2014]画框 题解 题目链接：P3236 [HNOI2014]画框 题意：小 T 准备在家里摆放几幅画，为此他买来了 \(N\) 幅画和 \(N\) 个画框。为了体现他的品味，小 T 希望能合理地搭配画与画框，使得其显得既不过于平庸也不太违和。 对于第 \(i\) 幅画与第 \(j\) 个画框的配对，小 T 都给出了这个配对的平凡度 \(A_{i, j}\) 与违和度 \(B_{i, j}\) 。整个搭配方案的总体不和谐度为每对画与画框平凡度之和与每对画与画框违和度的乘积。具体来说，设搭配方案中第 \(i\) 幅画与第 \(P_i\) 个画框配对，则总体不和谐度为 \[ \mathrm{disharmony}=\sum_{i=1}^{N}A_{i,p_i}\times \sum_{i=1}^{N}B_{i,p_i} \] 小 T 希望知道通过搭配能得到的最小的总体不和谐度是多少。 q779在水文章\(🐒\) 这道题和P5540 [BalkanOI2011] timeismoney | 最小乘积生成树 几乎就是一道题 可以先看下这篇题解（ 变化不是...

洛谷P5540 [BalkanOI2011] timeismoney | 最小乘积生成树 题解 题目链接：P5540 [BalkanOI2011] timeismoney | 最小乘积生成树 题意：给出一个 \(n\) 个点 \(m\) 条边的无向图，第 \(i\) 条边有两个权值 \(a_i\) 和 \(b_i\) 。 求该图的一棵生成树 \(T\) ，使得 \[ \left(\sum_{e\in T}a_e\right)\times\left(\sum_{e\in T}b_e\right) \] 最小 注意到对于一棵生成树，式子中的左右两边均为常数 考虑将生成树映射到平面上的点 \((x,y)\) 其中 \(x=\sum\limits_{e\in T}a_e,y=\sum\limits_{e\in T}b_e\) 那么问题就转化为了求一个点 \((x,y)\) 使得 \(x\times y\) 最小 可以发现这些点的分布存在边界 即 \(x\) 特别大 \(y\) 特别小的时候以及 \(y\) 特别大 \(x\) 特别小的时候 这两种情况分别对应点 \(A\) 和 \(B...

洛谷P2491 [SDOI2011] 消防 题解 题目链接：P2491 [SDOI2011] 消防 题意：某个国家有 \(n\) 个城市，这 \(n\) 个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为 \(z_i\) 。 这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。 现在这个国家的经费足以在一条边长度和不超过 \(s\) 的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。 你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。 看到这是一棵树，而且还要求路径的最大值 很容易想到这个枢纽要建在直径上 当 \(s\) 大于等于直径时显然成立 考虑 \(s\) 小于直径的情况，枢纽全部建在直径上仍是最优解 以下为证明： 假设只有一个枢纽结点（在直径上），我们以它为中心扩展出一条路径 离这个点最远的结点一定在直径上，而且是直径的端点 此时的最大值就...

洛谷P3299 [SDOI2013]保护出题人 题解 题目链接：P3299 [SDOI2013]保护出题人 题意：出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。 参加SDOI2012的小朋友们释放出大量的僵尸，企图攻击铭铭的家。而你作为SDOI2013的参赛者，你需要保护出题人铭铭。 僵尸从唯一一条笔直道路接近，你们需要在铭铭的房门前放置植物攻击僵尸，避免僵尸碰到房子。 第一关，一只血量为 \(a_1\) 点的墦尸从距离房子 \(x_1\) 米处速接近，你们放置了攻击力为 \(y_1\) 点/秒的植物进行防御；第二关，在上一关基础上，僵尸队列排头增加一只血量为 \(a_2\) 点的僵尸，与后一只僵尸距离 \(d\) 米，从距离房 \(x_2\) 米处匀速接近，你们重新放置攻击力为 \(y_2\) 点/秒的植物；……；第 \(n\) 关，僵尸队列共有 \(n\) 只僵尸，相邻两只僵尸距离 \(d\) 米，排头僵尸血量 \(a_n\) 点，排第二的 僵尸血量 \(a_{n-1}\) ，以此类推，排头僵尸从距离房子 \(x_n\) 米处...

Dijkstra及其复杂度证明 本文主要围绕易混淆的复杂度分析进行讨论 另外其实这个不叫迪杰斯特拉，这个叫/ˈdɛɪkstra/ qwq 一、前置知识 先放几个简单概念 无向图：图中所有的边都是两端可达的，也就是可以从任意一端通过这条边 有向图：图中所有的边都是单向的，有一个起点和一个终点，方向为起点指向终点 重边：两个结点间多条存在完全一样的边，通常它们可能拥有不同的权重或属性 自环：起点和终点相同的边 简单图：图中不存在自环和重边，显然一定存在两个结点的度数相同 多重图：存在自环或重边 更多内容可以参考这里 ，这里只介绍了一些对本文有用的概念 二、时间复杂度分析 给定一张具有非负权重的图和一个源点 \(s\) （起点），问结点 \(t\) 与 \(s\) 的最短距离是多少 设图中的结点数为 \(n\) ，边数为 \(m\) ，\(n\le m\) 算法流程： \(\text{dis[s]=0} \land \forall u \in V\backslash S , \text{dis[}u\text{]}=+\infty\) 从未确定最短路的点集 \(T\) 中找到...

最小树形图 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]...