Serval and Bonus Problem - 洛谷 最近有 $\tt ARC\ F$ 题竟然是相似题，好吧其实也没有那么相似，但是第一步转换是经典的。 首先根据期望线性，求一条线段的期望就是求区间内所有点的期望的和。 之后考虑既然是点那问题就简单了，直接考虑每条线段的相对位置就行了，也就是考虑 $(2n + 1)$ 个点，随机排列被钦定的点 $X$ 被 $\tt K$ 条线段覆盖的期望。 直接考虑进行 $\tt Dp$，考虑去对点进行匹配，设考虑到第 $i$ 个点，还有 $j$ 个点没有右端点，当前位置有没有被选择的方案数。 $$\begin{aligned}f(i, j, k) &\to f(i + 1, j + 1, k) \\f(i, j, k) \times j &\to f(i + 1, j - 1, k) \\f(i, j, 0) &\to f(i + 1, j, 1), j \ge K\end{aligned}$$ 当然我们最后的时候还要考虑线段的顺序，点的顺序，两个端点的顺序，还要把之前是考虑长度为 $1$ 现在变成 $l$ 了。 ...

Problem - 1383E - Codeforces 发现删除后得到的子串肯定是原串的一个子序列，考虑我们怎么样才能改变这个串。 考虑如何删除一个 $0$，也就是要么直接删掉要么前面为 $1$。那么本质上就是随意删除。 如果删除一个 $1$，我们需要保证前后存在一个是 $1$ 的位置 我们继续考虑最终的序列也就是在连续的一段 $1$ 中是可以任意删除的，如果是连续的一段 $0$ 我们是不能被 $1$ 影响的，也就是在区间内不存在任意的 $0$。 那么我们事实上只需要考虑限制，也就是我们把每个 $1$ 都拿出来考虑 $0$ 的限制。 考虑将 $S$ 变成一个数组 $\text{ {pre(i)} }$ 表示位置 $i - 1 \sim i$ 的 $0$ 的个数，可以发现 $\tt T$ 合法 当且仅当 $\tt T$ 的前缀和后缀的 $0$ 小于新的数组的第一个或者最后一个值，对于 $\tt T$ 是可以和 $S$ 进行匹配，也就是意味着对于 $\tt pre$ 存在一个子序列对应的元素大于等于 $\tt T$。 考虑我们做法是用来填 $1$ 的所以需要注意全部是 $0$ 的情况。 ...

Walls 防壁 - 题目 - 黑暗爆炸OJ 一下子想不到什么数据结构来维护一车东西，因为考虑对于每个线段对于每一个点都是需要考虑贡献的，所以状态数就已经是 $O(n ^ 2)$ 了，所以要考虑减少状态。 考虑对于一个点 $x$，在区间 $[l, r]$ 是合法的当且仅当 $l \le x \le r$，发现没有什么特别的性质。考虑点 $r = l + len$，那么发现对于上述式子可以变成 $x - len \le l \le x$，诶，线段和点相互转换了。 我们考虑当前用点去匹配线段的情况，我们尝试缩减状态，很明显三条同向的线段是可以变成开头和结尾两条的，那么我们的线段就变成了左右横跳的情况。 但是我们 $\tt len$ 是会变的，我们考虑对于一个点 $l$ 在其左边的线段肯定是横跳到原来的 $x$，对于右边的线段就是 $x - len$，当长度变得足够大的时候我们会发现两条线段有重合部分了，对于这种情况我们其实只要跳到上线段右端点就已经是最优的。 所以我们考虑可以对于距离最近的线段进行删除，因为上述就已经不是反复横跳的情况了。 我们不妨将两条连续线段的编号记成下面线段 ...

[省选联考 2020 A/B 卷] 冰火战士 - 洛谷 奇怪的题面可以看成求 $\tt 2\max(\min(vl, vr))$，其中 $vl, vr$ 表示左右两边的能量和。 这个东西显然可以考虑二分，之后考虑假设我们二分出来一个答案我们需要通过二分找到每边符合条件的战士之和。 但是其实不需要这样，很明显发现我们是尽量让战士越多越好，当然这个条件肯定是有一个临界值，可以发现我们只需要考虑冰战士比火战士能量多和少的情况。而且对于这个情况我们还能发现温度肯定是某个战士的温度进行 $\pm 1$ 的偏移。 考虑直接对于这个温度进行二分，使用树状数组进行二分，这个东西本质就和倍增是一样的。 之后就是考虑无解是怎么判的，考虑无解就是取任意温度双方都有一方是不能参赛的，也就是冰战士的最低温度比火战士的最高温度要高，不然一定存在解。 细节： 冰系战士是不低于，火系战士是不高于。我们考虑什么时候一个战士是不能参赛的，对于冰系来说就是温度严格低于，火系是严格高于。如果考虑让冰系贡献减去火系贡献的时候，加入冰系就是在其温度的时候，减去火系就是在其温度 $+ 1$ 的时刻。 1234567891 ...

[BalticOI 2008]黑手党 - 洛谷 发现就是考虑对多少个点打标记使得 $S \to T$ 的任意一条路径都是有标记的点。 本质就是割掉若干个点使得 $S,T$ 不连通。 每个点有权值也是没有关系的，所以直接拆点跑最小割就行了。 注意： 如果要输出方案的话，我们考虑遍历 $S$ 可以到达的点集，对于每个点打标记，如果说存在一条边使得两边的点是在不同的集合，那么这条边就是被割掉的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123#include <bits/stdc++.h>using names ...

[USACO05JAN]Muddy Fields G 本质上就是求每个点的最小点覆盖，考虑到一个木板可以覆盖横着或者竖着，可以考虑对于可以被同一个木板覆盖的位置可以缩点成同一个。 因为能被同一个木板覆盖肯定比分成两块木板覆盖优。 对于行和列分别进行操作，我们考虑对于图上每个点对于行列的限制是什么。 如果这个行被选择了那么对应的列是不能覆盖到当前位置的。 这个本质就是一个匹配，我们求的是最少要多个点能将全部的行和列被覆盖，本质上就是最大独立集，也就是二分图的最大匹配。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899#include <bits/stdc++.h>using namespace std;namespace Legendgod
...

[ZJOI2007] 矩阵游戏 - 洛谷 不能说我会做，只能说这个题目是我根据套路猜出来的。 众所周知我们会考虑将行和列拆开进行计算，我们考虑这个题目，最终的要求就是第 $(i, i)$ 位置是黑色的，也就是第 $i$ 行和第 $i$ 列恰好有一个黑色的匹配。 那么对于一个最终状态就是有 $n$ 个匹配，我们猜测只要有 $n$ 个匹配的都是合法的状态。 考虑左边是行右边是列，这个就是一个二分图，对于这个二分图考虑进行交换某两行的操作，相对行不变可以发现对应的列进行了交换。 那么对于最终的答案我们可以通过交换某两行达到二分图上列的交换，同理行也是可以进行交换。 根据题目交换明显是可逆的，所以这个就是充要条件。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <bits/stdc++.h>u ...

之前不是很懂我们现在再来了解一下。 三元环首先考虑我们暴力就是枚举一个点之后枚举边看一下是否相连。 那么我们可以考虑枚举一条边 $(u, v)$ 再枚举 $v$ 的出边看一下是否能连接到 $u$，我们只要预先对于 $u$ 的出边打标记就可以了，复杂度是 $O(m ^ 2)$ 的。 但是事实上，三元环是没有方向的，甚至于对于三元环 $(a, b, c)$ 其任意的排列都是同一个三元环。 所以我们考虑对于边能否进行定向，考虑进行根号分治，让每个点的度数尽量小。所以我们让出边少的连接到出边多的点上。 我们还是枚举点，最外层的循环就是 $O(m)$，考虑如果当前的点度数为 $d$，其出边肯定是到比 $d$ 大的点上，最多是 $\frac{m}{d}$ 。 对于度数 $< \sqrt m$ 的点，其出边可以到达 $O(\sqrt m)$ 最多有 $O(m)$ 个。 对于度数 $> \sqrt m$ 的点，其点的个数总共只有 $\sqrt m$ 个。 所以综上复杂度是 $O(m \sqrt m)$。 1234567891011121314151617for(int i = ...