Dijkstra及其复杂度证明 本文主要围绕易混淆的复杂度分析进行讨论 另外其实这个不叫迪杰斯特拉，这个叫/ˈdɛɪkstra/ qwq 一、前置知识 先放几个简单概念 无向图：图中所有的边都是两端可达的，也就是可以从任意一端通过这条边

最小树形图 Tarjan的DMST算法 前言 网上怎么都是朱刘算法啊？ 那我来写一篇 Tarjan 的 DMST 算法吧 qwq 注：本文的DMST采用左偏树+并查集实现 时间复杂度为 \(O(E+V\log E)\) 如果采用斐波那契堆则

洛谷P3919 【模板】可持久化线段树 1（可持久化数组） 题解 题目链接：P3919 【模板】可持久化线段树 1（可持久化数组） 题意：如题，你需要维护这样的一个长度为 NN 的数组，支持如下几种操作 在某个历史版本上修改某一个位置上

洛谷P1129 [ZJOI2007] 矩阵游戏 题解 题目链接：P1129 [ZJOI2007] 矩阵游戏 题意：给定一张有黑白棋子的正方形棋盘，问存不存在解法使得经过若干次交换行或列的操作后，左上角至右下角的对角线上所有的点放着黑色棋子

kd-tree(KDT) 时间复杂度证明 kd-tree 是一种可以高效处理 \(k\) 维空间的数据结构 在算法竞赛类的题目中一般有 \(k=2\) 还有个比较有趣的结论，当 \(k=1\) 时其实它就是一棵线段树 下文中的 \(n\)

洛谷P4357 [CQOI2016]K 远点对 题解 题目链接：P4357 [CQOI2016]K 远点对 题意：给定平面内 \(n\) 个点的坐标，求欧几里德距离第 \(k\) 远的点对 本题的正解应该是旋转卡壳、分治等算法，不会 而

CF1200E Compress Words 题解 题目链接：CF1200E Compress Words 题意：给定一堆字符串，依次插入答案串尾部，每次删掉答案串的后缀 与 待插入串的前缀的最大匹配串 解法一 KMP 这个解法常数比较