Q779的博客

洛谷P3829 [SHOI2012]信用卡凸包题解题目链接：P3829 [SHOI2012]信用卡凸包题意：给定若干个“信用卡”，求其“凸包”周长这个题其实看上去很不可做，其实很简单注意到（搬了一张图，来自link，不过这

2022-04-25 OI

算法计算几何

洛谷P3194 [HNOI2008]水平可见直线题解题目链接：P3194 [HNOI2008]水平可见直线题意：在$ x-y$ 直角坐标平面上有 $n$ 条直线 $L_1,L_2,…L_n$，若在 $y$ 值为正无穷大处往下看，能见到

2022-04-23 OI

算法数据结构计算几何

洛谷P3236 [HNOI2014]画框题解题目链接：P3236 [HNOI2014]画框题意：小 T 准备在家里摆放几幅画，为此他买来了 $N$ 幅画和 $N$ 个画框。为了体现他的品味，小 T 希望能合理地搭配画与画框，使得其显得

2022-04-22 OI

洛谷P5540 [BalkanOI2011] timeismoney | 最小乘积生成树题解题目链接：P5540 [BalkanOI2011] timeismoney | 最小乘积生成树题意：给出一个 $n$ 个点 $m$ 条边的无向

2022-04-22 OI

算法数学计算几何

洛谷P2491 [SDOI2011] 消防题解题目链接：P2491 [SDOI2011] 消防题意：某个国家有 $n$ 个城市，这 $n$ 个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为 $z_i$ 。这个国

2022-04-19 OI

算法图论数据结构

洛谷P3299 [SDOI2013]保护出题人题解题目链接：P3299 [SDOI2013]保护出题人题意：出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。参加SDOI2012的小朋友们

2022-04-17 OI

算法计算几何

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

2022-03-28 OI

算法数据结构计算复杂性理论

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

2022-03-27 OI

算法数据结构

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

2022-03-14 OI

算法数据结构

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

2022-03-12 OI

算法

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

2022-03-02 OI

数据结构

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

2022-03-01 OI

算法数据结构玄学