本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-14 19:54:59

暴力子树加最差复杂度是方的，因为每个点会被加入许多次。准确的说，会暴力加其深度加一次，因为其到根的链上每个点的答案都由它贡献。

发现 DFS 整体是有一条回溯链的。这条链上的点是不需要重复加入与删除的。取这条链为重链，那么有对任意点，其到根的轻边是 $\log$ 级的，整体复杂度是 $O(n\log n)$ 的。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-17 08:18:16

CF865D Buy low sell high

首先有贪心：将每个价值压入堆，如果当前价值大于根，那么就弹根并贡献。

但是这样是错误的：1 2 100，正确答案应当是 99。

我们需要一个反悔的操作：注意到 $p_i - p_o + p_j - p_i = p_j - p_o$，即以 $i$ 做一个中转点。

形式化些，每次购买，弹根的同时，要将自己的价值也压入其中，提供反悔的机会。

考虑正确性。我们要证：不存在任意时刻 $(x, y)$（ 表示 $x, y$ 之间的差价）在最优方案中，而不在上文所述的反悔谈心方案中。

我们有：对于所有不是买进点的 $i \lt x, p_i \gt p_x$。如果 $i$ 是卖出点，我们将其与 $y$ 连接得到不劣的方案；如果 $i$ 时刻什么都不做，那么我们与 $y$ 连起来显然更优。

那么，$x$ 一定是当前堆的堆顶，因此我们一定有一个 $x \lt f \le y, p_f \gt p_x$，那么 $f$ 将 $x$ 弹出，同时 $f$ 被压入。如果 $f$ 是 $y$，那么得证；

麻了，发现太显然了，不想证了。读者自证。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-17 08:41:39

证：每轮操作后 U 数量奇偶性不变

只有三种情况：

UUU
UUD
DUD

分别对应：减少三个，减少一个与增加一个；每轮操作选择两个做，所以奇偶性不变。

最后一种情况数量上界是 $O(n)$，因此操作有穷。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-18 17:12:54

由于我很脑瘫，所以我需要板刷点 CF 小题。

CF1971D

01 交界处肯定是要切开的。统计交界处的数量。如果序列全都一样，那答案就是一；如果交界处多于一个，我们将一个 01 放到最后，其他的 0 放到最前头，1 放到最后；否则有两种情况 01 或 10。前者答案为一，后者答案为二。

CF1739C

如果 A 拿到了 $n$，那么她直接出就赢了；方案数是 ${n-1}\choose {n/2}$；

否则 B 拿到 $n$，第一轮随便出，然后转化到第二轮后手，因为具体大小是没有影响的。

平局只有一种方案，即交叉相错。后手的用总方案减去平局减去先手赢即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-25 16:41:23

简单描述一下匈牙利算法：

首先设 $m_u$ 表示每个点的匹配。

尝试对每个点 $u$ 进行匹配，对每一个 $(u, v) \in E$：

• 如果 $v$ 未匹配就直接匹配；

• 否则，尝试重新匹配 $m_v$；如果成功，那么 $(u, v)$ 相配；否则失配，继续找下一个 $v$。

注意到这个过程就是找增广路的过程。第一种情况中的增广路是 $u \to v$；第二种情况中，若设 $m_v$ 的新匹配是 $m_v'$，那么增广路是 $u \to v \to m_v \to m_v'$。

不难注意到，两种情况都使整体匹配数加一，故一个最大匹配中一定是没有增广路的。

再证充分性。

充分性太难了不好证 但是分讨可以证

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-26 00:03:44

本篇题解是赛后补的，参考学习了官方题解以及 jiangly dalao 的代码。

首先发现本题和最近的 ABC349D 很像。但是注意到那个题里没法将两个区间相减，但是本题可以，于是那个题的策略没法照搬。

那么怎么样才能得到最优解呢？（题目要求我们必须用最优策略）

换句话说，我们需要求出从 $r$ 走到 $l$ 的最少步数。注意到值域相比上一个题小了很多，那么可以尝试最短路。

不难发现，对于一个数 $u$，我们能够转移到的数是 $v = u \pm 2^j, 0\le j \le \mathrm {lowbit}(u)$，其中 $\mathrm{lowbit}(x)$ 是 $x$ 的最低非零位。因为对于 $j \gt\mathrm{lowbit}(u)$，$2^j \nmid u$，无法转移。

由于边权都是 $1$，我们就可以直接 BFS 跑出最短路，然后一边跳一边计算即可。

赛后的 submission

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-28 16:35:38

sosdp 可以在 $O(n2^n)$ 的复杂度内完成一类子集的操作。

对于一类在集合上传递的计算，即对 $S \subseteq T$ 有 $f(S)$ 的值域包含于 $f(T)$，我们可以用类似前缀和的技巧减少重复计算。

本来想放例题的，但是有点板了，就不放了

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-31 16:35:31

设 $f(S)$ 表示匹配完集合 $S$ 的方案数，最后一个匹配的左点编号就是 $S$ 的模，那么这最后一个点可以和一个右点匹配，当且仅当这两点之间有边且这个右点在 $S$ 中。

然后就好了。可以推测这个问题应该是 NP 难的。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-08 15:15:17

最小路径覆盖就是选出最少数量的互不重合的路径，使其包含所有的点。也即，每个点在且仅在一条路径上头。

题解区队爷提到：对于这种“对于每个，有且只有”的性质，可以抽象成二分图。

每个点与两个点连接，分别是作为入点和出点的情况。那么我们考虑把每个点抽象成两个点 $(u, u + n)$，然后向 $u$ 的每个出点连边 $(u + n, v)$。这样，我们就能求出来合并的数量，以 $n$ 减去就是路径数量。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-09 14:11:54

二分图做法

我们考虑将每种试题拆成 $k$ 个点，作为左侧点，代表这种试题的可选项。

右侧点就是每个试题。每个试题与试题选项之间连边。

然后进行二分图匹配。我们知道，每个左侧点有唯一的匹配点，每个右侧点也最多匹配一个左侧点，于是符合题意。

网络流做法

我们设源点为 $S$，汇点为 $T$，那么 $S$ 与每个试题相连，容量均为一；$T$ 与每种类别相连，容量为其需要的数量。然后，试题与其所属于的类型相连，容量是一。

在这个网络中，如果最大流不为总共需要匹配的数量，那么就无解；否则直接找流量非零的点然后输出即可。

这样下来，一共需要 $n + k + 2$ 个点。

p.s. 感觉开始悟到二分图和网络流的一些用处了 /hsh