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

有的题，横坐标和所切的斜率均不单调，比如 P4655 Building Bridges，这时候我们可以用 CDQ 分治来把朴素的 $O(n^2)$ 优化到 $O(n\log n)$。

具体方法比较简单。CDQ 分治所考虑的核心就是左区间对右区间的贡献。怎么转化成为朴素的斜率优化 DP 呢？左边区间的横坐标要单调，右边区间所切的斜率要单调。

这样，我们就先按照切的斜率排序，然后计算左边对右边的贡献，然后按照横坐标排序。

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

首先奇耻大辱。赛时以为 Unrated 就不要紧，帮人调码交了两发，然后棕了。确实该罚，以后牢记。

然后来看题。

先不管操作一二。对于操作三，要求我们把所有糖果分成 $k$ 份，所要统计的是重复出现的糖果的数量，别的没有要求。

如果每人每种糖果先分一颗，这时候每种糖果数量减去 $k$，接下来还没分完的糖果每颗都会带来 $1$ 的贡献。

换句话说，我们就是对于每次询问的 $k$，统计每种糖果超出 $k$ 部分的总和。也就是说，大于 $k$ 的数的总和，减去大于 $k$ 的数的数量乘上 $k$ 就是答案。

这个操作用什么可以完成？平衡树，树状数组，权值线段树都可以做到。赛时无脑上了平衡树，但是实际上因为值域很小，所以后两者不需要离散化就可以。

总的来说，我们的做法就是：用桶维护每种糖果的数量，然后用上面三种数据结构之一维护；加减可以先删再插入，查询就查大于某数的数的和以及数量。

这里是代码。

平衡树有几个点注意：

• 需要加哨兵，否则需要注意边界情况；

• 查大于某数的数的数量，可以找后继然后用根减去左子树。

本文章由 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'$。

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

再证充分性。

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