嘘~ 正在从服务器偷取页面 . . .

Welcome
  文章分类
随笔 27 OI 1144 笔记 69 前端 6 后端 3 系统 31 图像设计 5 摘录 7 文化课 52 游戏 7
Dijkstra及其复杂度证明 Dijkstra及其复杂度证明
Dijkstra及其复杂度证明 本文主要围绕易混淆的复杂度分析进行讨论 另外其实这个不叫迪杰斯特拉，这个叫/ˈdɛɪkstra/ qwq 一、前置知识 先放几个简单概念 无向图：图中所有的边都是两端可达的，也就是可以从任意一端通过这条边
2022-03-28 OI
算法 数据结构 计算复杂性理论
最小树形图 Tarjan的DMST算法 最小树形图 Tarjan的DMST算法
最小树形图 Tarjan的DMST算法 前言 网上怎么都是朱刘算法啊？ 那我来写一篇 Tarjan 的 DMST 算法吧 qwq 注：本文的DMST采用左偏树+并查集实现 时间复杂度为 \(O(E+V\log E)\) 如果采用斐波那契堆则
2022-03-27 OI
算法 数据结构
洛谷P3919 【模板】可持久化线段树 1（可持久化数组） 题解 洛谷P3919 【模板】可持久化线段树 1（可持久化数组） 题解
洛谷P3919 【模板】可持久化线段树 1（可持久化数组） 题解 题目链接：P3919 【模板】可持久化线段树 1（可持久化数组） 题意：如题，你需要维护这样的一个长度为 NN 的数组，支持如下几种操作 在某个历史版本上修改某一个位置上
2022-03-14 OI
算法 数据结构
洛谷P1129 [ZJOI2007] 矩阵游戏 题解 洛谷P1129 [ZJOI2007] 矩阵游戏 题解
洛谷P1129 [ZJOI2007] 矩阵游戏 题解 题目链接：P1129 [ZJOI2007] 矩阵游戏 题意：给定一张有黑白棋子的正方形棋盘，问存不存在解法使得经过若干次交换行或列的操作后，左上角至右下角的对角线上所有的点放着黑色棋子
2022-03-12 OI
算法
kd-tree(KDT) 时间复杂度证明 kd-tree(KDT) 时间复杂度证明
kd-tree(KDT) 时间复杂度证明 kd-tree 是一种可以高效处理 \(k\) 维空间的数据结构 在算法竞赛类的题目中一般有 \(k=2\) 还有个比较有趣的结论，当 \(k=1\) 时其实它就是一棵线段树 下文中的 \(n\)
2022-03-02 OI
数据结构
洛谷P4357 [CQOI2016]K 远点对 题解 洛谷P4357 [CQOI2016]K 远点对 题解
洛谷P4357 [CQOI2016]K 远点对 题解 题目链接：P4357 [CQOI2016]K 远点对 题意：给定平面内 \(n\) 个点的坐标，求欧几里德距离第 \(k\) 远的点对 本题的正解应该是旋转卡壳、分治等算法，不会 而
2022-03-01 OI
算法 数据结构 玄学
CF1200E Compress Words 题解 CF1200E Compress Words 题解
CF1200E Compress Words 题解 题目链接：CF1200E Compress Words 题意：给定一堆字符串，依次插入答案串尾部，每次删掉答案串的后缀 与 待插入串的前缀的最大匹配串 解法一 KMP 这个解法常数比较
2022-03-01 OI
算法 字符串
洛谷P2387 [NOI2014] 魔法森林 题解 洛谷P2387 [NOI2014] 魔法森林 题解
洛谷P2387 [NOI2014] 魔法森林 题解 题目链接：P2387 [NOI2014] 魔法森林 题意：每条边有边权 \(a,b\) 两个，求 \(1\) 到 \(n\) 的路径使得所经过的边中 \(\max\{a\}+\max\{
2022-02-25 OI
算法 图论 数据结构
洛谷P4234 最小差值生成树 题解 洛谷P4234 最小差值生成树 题解
洛谷P4234 最小差值生成树 题解 题目链接：P4234 最小差值生成树 题意：给定一个点标号从 \(1\) 到 \(n\) 的、有 \(m\) 条边的无向图，求边权最大值与最小值的差值最小的生成树，图可能存在自环 这个题不太好利用k
2022-02-25 OI
算法 图论 数据结构
LCT求解最小生成树 LCT求解最小生成树
LCT求解最小生成树 前言 最小生成树模板： P3366 【模板】最小生成树 朴素的kruskal为主流最小生成树算法 而LCT(link cut tree)也是可以维护最小生成树的 由于LCT动态维护最小生成树，加上常数较大 在实际测试中
2022-02-25 OI
算法 图论 数据结构
洛谷P2147 [SDOI2008] 洞穴勘测 题解 洛谷P2147 [SDOI2008] 洞穴勘测 题解
洛谷P2147 [SDOI2008] 洞穴勘测 题解 题目链接：P2147 [SDOI2008] 洞穴勘测 题意：给定若干个点，动态连接（无向边），询问连通性 由于它有删边的操作，因此用并查集并不可行 于是想到LCT（？ 由于LCT有
2022-02-24 OI
算法 数据结构
洛谷P1501 [国家集训队]Tree II 题解 洛谷P1501 [国家集训队]Tree II 题解
洛谷P1501 [国家集训队]Tree II 题解 题目链接：P1501 [国家集训队]Tree II 题意：树上区间加&乘&link&cut 显然LCT模板题，因为树链剖分并不能维护动态连边 考虑如何维护区间乘
2022-02-24 OI
算法 数据结构
91 / 96