博客版本 参考：hsfzLZH1 的 博客 及代码启示 左偏树 模版题：Luogu3377。 由于朴素堆的合并操作可能会退化到 $O(n)$，所以我们需要通过一些方式维护合并操作，左偏树就是其中之一。 一些定义 该部分改编自 hsfzLZH1 的 博客 外结点 ：左儿子或右儿子是空结点的结点（首先左偏树是一个堆，堆是一棵二叉树）。 距离 ： 一个结…

题目链接 解析 题意就不多阐述了，看原题就够了。个人觉得这是一道练归并排序性质的好题（虽然动规/堆维护等方法似乎也可行，但我认为最朴素的方法才是最美丽的）。 再发觉贪心不可行时，我们考虑分治维护每一轮比赛可能获胜的人。假设我们以及维护好了左区间（即上一轮比赛）哪些人可能能在上一轮获得胜利（也就是能活到当前这轮）以及右区间的这个信息，我们考虑如何合并…

博客参考：学委 的 博客 及 代码启示 暴力最大流 模板题：Luogu3376 在学习 Dinic 之前，必须先要知道暴力最大流的写法。 首先理解何为网络最大流。一张网络就是一张带权有向图，源点可以输出无限的流量，但是每一条边都有一个容量，需要满足这条边上的流量不能超出其容量（可以理解为输水系统），最后所有流量都会被汇点接收。我们需要求出这个网络运…

题目链接 题意 给定一个二分图，二分图上的每个点都有一个权值。如果一个左部点的权值和一个右部点的权值的 $\gcd$ 大于 $1$，则这两点之间有一条边。求二分图最大匹配。 解析 首先我们发现，如果暴力建边的话，我们可能会建 $n^2$ 条边，在 $100$ 组数据的情况下，非常容易 TLE。 我们考虑优化。对于一个左部点的权值和一个右部点的权值的…

题目链接 题意 星球的一天有 $h$ 小时，每小时有 $m$ 分钟。现在给定一个当前时间，询问最近的在镜中对称之后合法的时间。 解析 主要是注意一些细节。首先判断最近的对称过去合法的小时，如果给出的时间的小时本身对称过去就是合法的，那么分钟就要从给出的分钟开始找，一直找到第一个合法的。否则，如果小时与给定的不一致，分钟就一定为 $0$，即输出一定为…

博客参考：CSDN 的 文章, enceladus, yybyyb, hyfhaha 的代码启示，皎月半洒花 的 博客, hyfhaha 的 博客。 前置知识 I - KMP字符串匹配 模版：Luogu3375。 我觉得这玩意儿比 trie 树难理解一点。 给定两个字符串 $s_1$ 和 $s_2$，我们需要求出 $s_2$ 在 $s_1$ 中所有…

文/流凡 我取出一把琴，在雨天的清明；琴声追寻着你的步伐，送来了霖霖。 高山流水，有伯钟的篇章；心之灵犀皆清照的明朗。 我低眉紧蹙，致敬着九重乐礼；你柔声轻起，勾起了三里追忆。 无人的黑山头，诠释铺天的幽寂；捉声的半眼泉，馈予沁人的安谧。 你说我，奏出了一片长安；我说你，吟来了半个江南。

20201215 不是最近的事，但是很想分享一下。一次去理发，那家店并不大，后面就是居民楼。当时正是秋天，不冷不热，因而二楼开了窗子。我在二楼洗头，一股饭菜的香味从窗口飘进来，那个为我洗头的小哥似乎是无意间说了一句，“好想念妈妈的饭菜”。顿时感到一阵直击内心的感动。 20201215 同样是一件以前的事。一次放学回家，已经是九点多了，也显得比较疲惫…

题目链接 @GuidingStar 让我来做这道题目然后我就做了一下，结果因为一个愚蠢的错误调了一个小时代码…… 题意 给定一棵树，维护区间后缀积之和，支持单点修改。 解析 个人觉得没那么难想（嗯，搞死我的是细节）。 我们先考虑线段树上如何维护这个东西。我们可以在维护区间后缀积之和的同时维护一下区间积，然后合并的时候只需要将左区间后缀积之和乘上右区…

题目链接 题意 维护一棵树，支持区间求和，区间最大值，区间最小值，区间取反，单点修改。 解析 这是一道很好的树剖练手题，思维难度不高，代码存在一些细节，本题解主要来说明这一部分，也用来警醒自己做题目时需要注意细节，尽可能避免调代码调半天的情况。 边权转点权 在树剖的两边 dfs 过程中，第一遍可以将边权赋给边端点中深度较大的那一个，即儿子节点。我们…