您已获得最佳的阅读体验！ 题目地址：CF1404E - Bricks 初做这道题时，我发现它和 P6062 - Muddy Fields G 神似。于是冲动交了一发，吃了 WA。仔细审题发现，这道题要求所用木板不能重叠。因此寻找其他的解题方法。 现在我们的当务之急是找出一个处理木板重叠的好方法，从黑色格子的分布入手——木板重叠放置的唯一可能就是当前黑色方格位于一个交叉的位置，如下图： 位于...

二分图基础 二分图，又称二部图。顾名思义，在一个二分图中，所有的节点可以分成两部分（分别用黑白染色），并且满足相同颜色的点之间无边。如下图： 我们发现，集合 内部的点间都没有连边，每条边必定连接两个不同集合的点。二分图有一个性质，那就是不存在奇数环。因为每条边都连接了不同的集合，必须过偶数条边才能回到出发点所在的集合，因此长度为奇数的环是一定不可能出现在二分图里的。 染色法判定二分图 基...

该知识点考频极低，请读者自行安排选学内容 双连通分量 双连通分量Double Connected Components，简称 （电磁场）。是连通分量在无向图中的体现。分为点双连通分量 和边双连通分量 。在一张连通无向图中，任意删去一条边，如果无论如何都不能使点 不连通，那么就称 边双连通；同样在一张连通无向图中，任意删去一个点（ 除外），如果无论如何都不能使 不连通，则称 点双连通...

连通分量与缩点 在说 之前，先涉及最基本的概念：连通分量。如果一张有向图中，任意两个节点都能互相到达，则称它是一个连通分量，特殊地，一个点也算一个连通分量。强连通分量Strongly Connected Component，简称 （四川菜），是原图的极大连通分量。这里的“极大”是一个文艺复兴时期提出的概念——若一个事物，没有比它更大的事物存在，就称这个事物是极大的/最大的（例如：导数的极大...

LCA 树上倍增法 实质是把节点每次向上暴力移动一步变成更加高明的按 步向上移动，借用的是每个数都可进行二进制分解的定理。期间维护一个父节点数组 fa，fa[i][k] 代表 向上移动 步的父节点。那我们该如何更新这个父节点呢？显然有 ，就是两次向上移动 步，因此可以用 fa[fa[i][k - 1]][k - 1] 来递归更新。 初始化时使用宽搜，把所有点的深度更新一遍。注意要设置...

小星野战力那么强一个人一组就够了ᕕ(◠ڼ◠)ᕗ 您已获得最佳的阅读体验！以及上面的小彩蛋…… 我们会发现这道题和 P5785 任务安排 长得神似。两道题都是把一个连续的序列分成若干块（块数没有特殊限制）。这启发我们把状态设置为 dp[i]，含义是：“把前 个士兵全部分好的最大修正战斗力”。 现在我们着手设计一个暴力 DP 程序，分析如下图： 因为 部分已知，就是我们的 dp[j]；我...

受限于在线编辑器的性能瓶颈（省流：写太多了会很卡），在此决定把另外的（不在算法提高课中）DP斜率优化题目单独拎出来写一篇做题笔记。旨在记录算式消元换元的原则与技巧、凸包维护的方法。题目大致由易到难。 洛谷 P3195 [HNOI2008] 玩具装箱 题目地址：P3195 题目难度：省选/NOI- P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进...

前情提要：Day1 单调队列优化 斜率优化 引 洛谷 P2365 任务安排 题目地址：P2365 题目难度：提高+/省选- 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 个任务被分成若干批，每批包含相邻的若干任务。 从零时刻开始，这些任务被分批加工，第 个任务单独完成所需的时间为 。在每批任务开始前，机器需要启动时间 ，而完成这批任务所需的时间是各个任务需要时间的总和（...

有人私信我，说能不能不要在博客里写那么多“显然”。我的回答是：“好的，全部换成‘Apparently’”。我寻思我也没写那么多显然啊 单调队列优化 简介 我们都知道单调队列是用来 维护一个序列的单调性的，在一个定长区间内，单调队列可以做到输出当前扫描区间内的最值元素。通过维护区间最值，在动态规划问题中，可以有效节省状态枚举带来的效率浪费，有时还可以用来对数组降维，是非常实用且简单的优化方法...

并查集 并查集，或称DSUDisjoint Set Union，是一种管理元素所属集合的数据结构。每次查询时把沿途的节点的父节点一并设置成全局父节点，从而达到均摊复杂度 的超高效率（其中 为 的反阿克曼函数，可以看作为常数复杂度）。基于并查集的许多特性（包括好写），人们开发出了许多不同种类不同用途的并查集，其中就包括带边权的权值并查集和对元素进行分类的种类并查集。这篇文章将探讨这两种并...