2024 年 7 月做题记录

前言

会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。

洛谷 P8004 Welcome to Lunatic City [!!*]

大胆猜想只要度数和原树一样的树都能构造出来。考虑构造证明，给每条边都放两个传送门，这样每条边都被切成了两部分，分别连着两个端点，然后对于新树上的每条边，在两个端点各取一条，将传送门匹配起来即可。

然后考虑计算答案。

考虑在答案树上所有关键点及其祖先形成的含根的连通块，其中的非关键点一定是度数最大的一个前缀。枚举这个前缀，显然将其与关键点合并后从大到小加点最优。暴力 check 就是 $O(n^2)$ 的。

考虑优化，首先枚举前缀的过程中维护树的形态，然后 check 的时候只需要插入剩余的关键点。然后每次不是插一个点而是改成插一层点，这样对于度数大于 $2$ 的点，每次都会插入两倍的点，然后只剩下度数小于等于 $2$ 的情况，可以方便地 $O(1)$ check，然后就做完了。

注意枚举完前缀后后面还剩下一些非关键点，因此连成的树必须剩下至少一条空闲的边。

CF1610H Squid Game [!]

首先容易发现选择 $1$ 可以覆盖所有非直链。

那么先考虑只有直链的情况，容易发现如果要覆盖大于 $1$ 条链，那链一定要有交，那可以把题目改成选的点必须在链上，因此转化成覆盖一条链当且仅当有点在链上。

当树退化成链时是经典贪心，考虑在树上一样地做，也就是从下往上考虑，当一条链没被覆盖时选择他最上面的那个点。

然后考虑加入非直链，发现对于非直链也是选的点越高越好，因此直接在直链做完之后 check 一下是否还有非直链未被覆盖即可。

CF1578J Just Kingdom [!!]

从下往上考虑，若点 $u$ 需要 $x$ 的钱，则 $fa_u$ 需要 $\sum_{v \in fa_u \land v \ne u} \min\{siz_v, x\}$，其中 $siz_v$ 为 $v$ 子树需要的钱的总和。

直接往上跳是 $O(n^2\log n)$ 的，考虑优化跳的过程。

发现当 $\min\{siz_v, x\} = x$ 时 $x$ 至少翻倍，因此这种点至多 $\log(nm)$ 个，而对于其他点可以方便的快速计算答案，倍增一下就好了。时间复杂度为 $O(n \log n \log(nm))$。

CF1439D INOI Final Contests [!!]

关键是要注意到最终如果一个位置是空的那么它两边是独立的。

设 $f_{i, j}$ 表示 $i$ 个位置 $j$ 个人的方案数，$g_{i, j}$ 表示总贡献。

当 $i > j$ 时，转移就枚举最后一个不含空位置段的长度：

$$\begin{aligned} f_{i, j} &= \sum\limits_{k = 0}^j f_{i - k - 1, j - k} f_{k, k} \binom{j}{k} \\ g_{i, j} &= \sum\limits_{k = 0}^j (g_{i - k - 1, j - k} f_{k, k} + f_{i - k - 1, j - k} g_{k, k}) \binom{j}{k} \end{aligned}$$

然后考虑 $i = j$ 时的答案，也就是每个位置都坐满。

考虑枚举最后一个人最终坐的位置，则选择的位置若在左边只能是从左往右，在右边只能是从右往左，然后两边也是独立的：

$$\begin{aligned} f_{i, i} &= \sum\limits_{j = 1}^i f_{j - 1, j - 1} f_{i - j, i - j} (i + 1) \binom{i - 1}{j - 1} \\ g_{i, i} &= \sum\limits_{j = 1}^i \left(f_{j - 1, j - 1} f_{i - j, i - j} \left(\frac{j(j - 1)}{2} + \frac{(i - j)(i - j + 1)}{2}\right) + f_{j - 1, j - 1} (i + 1) g_{i - j, i - j} + g_{j - 1, j - 1} (i + 1) f_{i - j, i - j}\right) \binom{i - 1}{j - 1} \end{aligned}$$

然后就做完了。

CF1067D Computer Game [!]

注意到可以升级时一定升级 $b_i p_i$ 最大的那个，并且之后一定只操作那个，记这个值为 $mx$。

设 $f_i$ 为 $t = i$ 时的答案，则：

$$f_t = \max\limits_{i = 1}^n \{p_i ((t - 1)mx + a_i) + (1 - p_i) f_{t - 1}\}$$

将其改写成：

$$f_t = \max\limits_{i = 1}^n \{p_i((t - 1)mx - f_{t - 1}) + p_i a_i\} + f_{t - 1}$$

则可以将每个转移视为一条斜率为 $p_i$，截距为 $p_i a_i$ 的直线，维护出下凸壳，即可 $O(\log n)$ 转移。

继续观察，考虑 $t \cdot mx - f_t$，发现 $(t \cdot mx - f_t) - ((t - 1) mx - f_{t - 1}) = mx - (f_t - f_{t - 1}) \ge 0$，因此转移时的 $x$ 是单调不降的，只需要二分找出每个转移点然后矩阵优化即可。

直接来是 $O(n \log^2 t)$ 的，可以把二分改成倍增，这样就是 $O(n \log t)$ 了。

CF1349F1 Slime and Sequences (Easy Version) [!!*+]

牛牛双射题。

注意到好的序列的个数是 $n!$，考虑构造和长度为 $n$ 的排列的双射。

具体就是好的序列按值域从小到大，从后往前记录下标得到排列，然后排列划分成若干极长下降段，第 $i$ 段的数作为下标使其值为 $i$ 得到好的序列，显然双射。

然后对于排列 $p$，$a_{p_i}$ 即为 $1 + \sum_{j = 1}^{i - 1} [p_j < p_{j + 1}]$。

因此：

$$ans_i = \sum\limits_{j = i}^n \left\langle\begin{matrix}i \\ j - 1\end{matrix}\right\rangle \binom{n}{j} (n - j)!$$

其中 $\left\langle\begin{matrix}n \\ m\end{matrix}\right\rangle$ 为 Eulerian Number，定义为长度为 $n$，有 $m$ 个上升（即相邻两个数前一个小于后一个）的排列个数。

CF1895G Two Characters, Two Colors [!]

改成原本可以获得 $r_i + b_i$ 金币，选红色会减少 $b_i$，选蓝色会减少 $r_i$，然后减少红色逆序对数，这样变成使减少的最少，考虑最小割。

对于 $0$ 的位置连 $(s, i, b_i), (i, r_i, t)$，$1$ 的位置连 $(s, i, r_i), (i, b_i, t)$，然后每个 $1$ 向后面的 $0$ 连流量为 $1$ 的边即可。

考虑模拟网络流，对于每个 $i$，初始可以流 $\min\{r_i, b_i\}$ 的流量，然后对于 $1$ 还能流 $k_i - \min\{r_i, b_i\}$ 的流量，而 $0$ 可以从前面的 $1$ 获取 $k_i$ 的流量，因此从前往后扫，每次遇到 $0$ 就贪心把剩余流量最大的 $k_i$ 个 $1$ 流掉。

具体地，需要维护一个数据结构，支持插入一个数、前 $k$ 大元素 $-1$、删掉值为 $0$ 的元素，FHQ Treap 维护即可。

CF1463F Max Correct Set [*+]

朴素暴力状压是 $O(n 2^{\max\{x, y\}})$ 的。

关键结论：答案存在长度为 $\max\{x, y\}$ 的循环。

对于整的段显然可以将 $\max\{x, y\}$ 的答案复制，然后对于不整的段感性理解一下（还不会证）。

然后还能优化。先将 $\gcd(x, y)$ 变为 $1$，就是将位置按模 $\gcd(x, y)$ 的结果分组，显然只有两种本质不同的组。然后对于每一组将不能同时放的关系连边，显然会连成一个环，求带权最大独立集即可。

洛谷 P10610 异界之门 [!!]

设 $f_{u, i}$ 表示 $u$ 子树能不能匹配 dfs 序区间 $[i, i + siz_u)$。由于题目保证同深度相同的点儿子个数相同，因此 $u$ 的每个儿子的子树大小相同，于是儿子能放的区间也只有儿子数个，若某个儿子可以放在某个区间则连一条边，变成 check 是否存在完美匹配。

然后考虑单点的匹配，注意到一个点的权值要么是其本身，要么加上父亲的权值，要么加上父亲的结果，因此可以设 $f_{u, i}$ 不考虑 $u$ 节点的匹配情况，在二分图匹配时 check 儿子的权值即可。

构造答案是简单的。

复杂度是 $n$ 乘上二分图匹配复杂度，具体分析就是考虑当儿子数大于 $1$ 时子树大小会翻倍。

AGC012C Tautonym Puzzle [*]

一个显然的做法是维护两半，每次在两部分后面加一个相同的数可以 $\times 2 + 1$，在第一部分前面加一个第二部分后面加一个相同的数可以 $+1$，然后不太会直接构造出 $k$ 个。

注意到如果把空序列算进去，那第一个操作就相当于 $\times 2$，然后构造 $k + 1$ 个即可。

CF1239E Turtle [!]

注意到如果确定第一行哪些数第二行哪些数后一定是第一行从小到大，第二行从大到小。

考虑将拐点从 $i$ 移到 $i + 1$，变化量为 $a_{1, i + 1} - a_{2, i}$，显然这个东西单调不降，因此最大值的一定是拐点为 $1$ 或 $n$。

再注意到 $a_{1, 1}$ 和 $a_{2, n}$ 一定是最小的两个数，因此就变成求剩下的 $2n - 2$ 个数中选 $n - 1$ 个，使得和最接近总和的一半，直接 DP 即可。

CF1979F Kostyanych’s Theorem [**++]

挺高妙的交互。

以下称回答的第一个点为 $u$，第二个点为 $v$。

设当前边数 $m \ge \frac{n(n - 1)}{2} - (n - 2)$，此时至少有一个点度数 $\ge n - 2$。

询问 $d = n - 2$，此时根据 $v$ 是否等于 $0$ 可以判断 $u$ 的度数是 $n - 2$ 还是 $n - 1$。

若是 $n - 2$，则删除 $u$ 后边数为：

$$m - (n - 2) \ge \frac{n(n - 1)}{2} - 2(n - 2) = \frac{n^2 - 5n + 8}{2} = \frac{(n - 1)(n - 2)}{2} - (n - 1 - 2)$$

符合原来的限制，可以递归构造哈密顿路，此时一定有一个端点与 $u$ 相连，接上去即可。

否则度数为 $n - 1$，此时显然一定会有一个点度数 $\le n - 3$，询问出来，设为 $x$，则删掉这两个点后边数下限为：

$$m - (n - 1) - (n - 3) + 1 \ge \frac{n(n - 1)}{2} - 3n + 7 = \frac{n^2 - 7n + 14}{2} = \frac{(n - 2)(n - 3)}{2} - (n - 2 - 2)$$

也符合原来的限制，递归构造哈密顿路，然后接上 $u$，再接上 $x$ 即可。

CF1815E Bosco and Particle [++]

首先对于每个对撞机保留最小整周期。

然后考虑只有某个对撞机的情况，可以模拟出一个周期内其在左边的时刻 $a_i$ 和在右边的时刻 $b_i$。

仔细观察可以发现多个对撞机时粒子在每个对撞机左右的位置的时间的比值也是 $\frac{a_i}{b_i}$。

设第一个空隙的时间是 $f_0$，则 $f_i = \frac{b_i}{a_i} f_{i - 1} = \prod_{j = 1}^i \frac{b_j}{a_j} f_0$，只需保证每次 $/ a_i$ 时都是整数即可，维护每个质因子的次数即可求出 $f_0$，答案即为 $\sum\limits_{i = 0}^n f_i$。

CF1572D Bridge Club [+]

首先变成二分图最大权匹配，然后发现图太大了跑不出来。

考虑一条匹配 $(u, v)$，会影响至多 $2n - 2$ 条边，算上其本身 $2n - 1$ 条，因此要存在 $k$ 个匹配只需要 $k(2n - 1)$ 条边。保留最大的几条，显然求出的答案就是原图的答案。

CFGym105112B Brickwork [!!++]

先考虑构造方案。

首先是两行都只用一种，那么设两种的长度分别为 $x, y$，则需要满足 $\mathrm{lcm}(x, y) = w$，这个是好 check 的。

然后考虑如果存在 $x, y$ 使得 $w | y, y | x$，那么一定能构造出一组解。方便起见我们令 $x = 1$，然后第一行全填 $y$，第二行开头一个 $1$，末尾 $y - 1$ 个 $1$，然后剩下全填 $y$ 即可。

除了上面两种情况，我们发现有倍数关系的砖只需要保留较小的那个。

这样搞完后大胆猜想一下只要存在一种使用至少两种砖的方案则一定可以构造出解。事实也确实如此。我们令第一行按从小到大顺序放，第二行开头放一个次小砖，末尾放一个最小砖，然后剩下的按从小到大的顺序放在中间，容易发现这样一定是对的。

现在唯一的问题是求出一组解。首先对于长度为 $l$ 的砖，令其个数为 $\lfloor\frac{w - 1}{l}\rfloor$，这样就解决了至少两种的条件，然后二进制分组加 bitset 优化 DP，对每个位置记录其第一次可以凑出来时的砖即可。