本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-30 19:40:03

知道两个做法。

第一个做法好想，我们设 $g(x)$ 表示 $[1, x]$ 中最大的翻转数，$g$ 单增显然，并且可以构造出来，类似数位 DP。然后二分就可了。

第二个做法，把原问题转化为找最小的 $k$ 使得 $f(k) \gt n$，答案就是 $k - 1$。这个好构造。我们考虑 $f(k)$ 一定是某一位比 $n$ 恰好大一，否则不优，然后这一位下面的所有数都是零；同时，最后一位必须不是零。

我们枚举这一位，然后算一下就可以了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-02 21:35:41

A 不表

B

给定一个序列，可以用 $k + 1$ 的代价给一个长度为 $k$ 的子序列加上一；求最小的使得序列不降的代价。

考虑所需要修改的量是静态的，因此可以把每个点上需要做的修改都拿下来，然后排序贪心。

赛时写的有点太保守了，调了一会儿。

C

回家再写。

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

不算难。难点在于 CCF 独有的鹅心大分桃。

答案的单调性是显然的：第 $x$ 天能完成，$x + 1$ 天也定能完成，于是二分一个 $m$ 作为答案，并转化为判定问题。

每棵树每天的增量是不小于一的，但是正由于这个一的下界，我们需要一个有点恶心的分桃。

忽略角标，我们设 $g(x)$ 表示从 $1$ 开始种，种到 $x$ 时刻的总高度，设 $z = \max \{0, \lceil\dfrac{1-b}c\rceil\}$ 是使得增量为一的点，定义域非负。

当 $x \lt z$ 时显然有 $g(x)= bx + \dfrac 1 2 cx(x + 1)$；

当 $x \ge z$ 时：

• $c\gt 0$，$g(x) = z + b(x - z) + \dfrac 1 2cx(x+1)-\dfrac 1 2 cz(z + 1)$

• $c = 0$，$g(x) = bx$

• $c \lt 0$，$g(x) = bz + \dfrac 1 2 cz(z + 1)+(x-z+1)$

很难说这种傻逼线性柿子有什么意义，但凡换成随便其它一个不需要分桃的单调函数都行。但是出了就得做。。

$g(x)$ 单调性显然，我们需要二分找到最大的 $t$ 使得 $g(t) \ge a$ 且 $g(t+1)\lt a$，即种这棵树的最晚入口。$t\le m$ 是显然的，不满足直接跳出。

找到所有的 $t$ 后，问题就转化为了：对每个点，我们为其分配一个 $x$ 使得 $1\le x \le t$ 且 $x_{\text{fa}_i}\lt x_i$，且 $x$ 不重。

那么我们按照 $t$ 排序，优先满足 $t$ 小的即可。

复杂度是两支 $\log$ 的，对应两个二分。

本文章由 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)$，我们可以用类似前缀和的技巧减少重复计算。

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