日记

今天才切了 $4$ 道题，太颓废了。

門松# Link to

总之就是非常神奇。

昨天晚上是因为读错题了导致被硬控一晚上。今天早上是因为码力太强又被硬控一上午。

考虑对于每个偶数 $i$，那么我们发现：$\{a_{i - 1},a_i,a_{i + 1} \}$ 形成的三元组状态一定是 $\{0,1\}$。对于最终的四个状态，大力分讨即可。

这种大力分讨的题往往都很考验码力。但是我的码力又不行。

Ski Slope S# Link to

开启今天的主线。

考虑把询问离线下来。然后把它和边混到一个数组里。用结构体记录三个值：$\{val,id,type\}$。其中，$val$ 表示这条边的难度/这头牛的水平。$id$ 表示边的终点/询问的 $id$。$type$ 就表示类型。对于每个点 $u$ 记录一个 $dis_u$ 表示它到 $1$ 的距离，$cnt_u$ 到 $1$ 有多少条边大于当前的水平。我们从大到小枚举每一条边/每一个查询。

• 如果这是一条边，那么就说明这条边的终点以及它的子树 $cnt$ 都要加 $+1$，因为 $c_i \le 10$，我们用 $10$ 个 set 维护每个 $cnt_u = [1,10]$ 的每个点。每次直接暴力 dfs 更新。剪枝：如果点 $cnt_u > 10$，那么说明 $u$ 和它的子树无论如何都不可能是答案，直接 return。
• 如果这是一个查询，那么我们就枚举 $i = [0,c_{id}]$ 的每个值，在 $set_i$ 里查找 $dis$ 的最大值所对应的点。

记得把 set 的比较器重载成 $dis_x < dis_y$。还有，当有一些边的 $val$ 和查询的 $val$ 一样，那么点一定比边优先。

Sequence Construction S# Link to

考虑 $k$ 在二进制下的第 $i$ 位。如果其为 $1$，就说明有一个数 $x$ 的 $\operatorname{popcount}(x)$ 为 $2^i$，说明 $x$ 为 $2^{2^i} - 1$。其实也不一定，但是我们按照这个策略构造是对的。

我们枚举 $k$ 的每一个为 $1$ 的位。将其记录进答案。并将其从 $m$ 中减去。如果出现 $m < 0$，就说明无解，因为我们已经按照最小方案来构造了。

对于 $m$ 剩下的，如果它为偶数，就在答案序列的末尾添加两个 $\frac{m}{2}$，这样既能保证和为 $m$，又能保证异或和不受影响。如果它为奇数，就先加 $\{1,2\}$，再加 $\frac{m - 3}{2}$，原因同上。

记得特判 $m$ 剩下的是 $1$。

OohMoo Milk G# Link to

显然有 John 和 Nhoj 都会去操作最大的那几个数，于是我们把题意转化为：John 先对于最大的 $A$ 个数加上 $D$，然后，Nhoj 去减每个数。但是总次数不能超过 $B \times D$，单个数减的次数不能超过 $D$。

考虑二分。设当前二分到了 $mid$，chk 时我们把尝试每个 $i \in [1,A]$ 的 $a_i$，减到 $mid$，但是因为有“单个数减的次数不能超过 $D$”的限制，所以有些数减不到 $mid$。如果总次数大于 $B \times D$，那么就说明 $mid$ 小了，往大二分。反之如果有剩余的，就把每个还能减的减到 $mid - 1$，并计算答案，然后继续往小二分，尝试更大的答案。

后日谈 # Link to 后日谈

我要变强！

4 月 20 日 # Link to 4 月 20 日

迟早要完

T3 # Link to T3

将柿子转化一下，变成 $\sum|T_i|\times |C_i - f|$，发现这玩意相当于：对于每个 $i$，有 $T_i|$ 个 $C_i$。求所有数的中位数。直接上离线将 $C_i$ 离散化。然后权值线段树。具体实现：树上节点存两个信息：$sumt,sumc$，分别表示该区间的 $T$ 之和和 $C$ 之和。中位数直接查询 $\lceil\frac{tot}{2}\rceil$ 的数就行。设中位数为 $med$。那么小于中位数的贡献是 $med - C$，大于的是 $C - med$。我们可以查询 $i \in [1,med]$ 的 $C_i$ 之和和 $i \in (med,n]$ 的 $C_i$ 之和。这样就能做到 $O(n\log n)$ 的复杂度。

后日谈 # Link to 后日谈

但是我们赛时都没做出来的题，deepseek 想了 $8$ min 就过了？

吃枣药丸。