「2025 暑假校内训」第一周

「精选模拟赛」#2

2028C

维护前后缀

abc207_e

直接 dp

1731E

利用 $φ (x)$ 函数可以计算出： $[1, n]$ 中互质对有 $(\sum_{i = 1}^{n} φ (i)) - 1$ 个。进而，容易得知 $[1, n]$ 中 gcd 为 $x$ 的数对一共有 $(\sum_{i = 1}^{⌊ n / x ⌋} φ (i)) - 1$ 。

知道了每个 gcd 为 $x$ 的个数，下面给出一种贪心：

从大往小贪，能用就用。

证明： 题目条件可简化为，选出 $m$ 条边需要花费 $m + c$ ，其中 $c$ 为操作次数，那么我们的目的就是最小化操作次数。

直觉上是从大往小，如果能确保不会发生「不选大的，选两个小的反而更优/能满足式子」之类的，那么这个贪心就是对的。

首先，容易得知，从大到小选，如果合法的话，其次数一定被最小化了。

其次，我们只需要考虑会不会存在「从大往小选不合法但是存在一种选法合法」的局面。

【理论1】：由之前的式子可以得出， $x$ 越小， $[1, n]$ 中 gcd 为 $x$ 的数对越多。

一种情况是【边数不够】。显然怎么选都是不合法的。

会不会存在【不能凑整】的情况？是不会的。在能够选的边数够的情况下，不会存在。

【情况1】选完一次，其边权为 $k + 1$ ，剩余边数小于 $k$ 。由上述【理论1】得知，后面一定存在一个可以恰好把剩下的填满。
【情况2】选完一次，其边权为 $k + 1$ ，剩余边数大于等于 $k$ 。还能再选一次就继续选，否则递归考虑下面的情况。由归纳法，如果边数够，最终一定会进入【情况1】。

abc286_g

考虑把每个由非关键边组成的联通块找出来，直接缩成一个点，因为它们可以随便走，所以可以看做在一个点徘徊不动。然后直接检查是否存在【欧拉路径】即可。

1878G

https://www.luogu.com.cn/article/k5srljmo

杂谈

糖题，太糖了。

卡常卡了我将近一个小时。

~~关键是，我没有想到 std 复杂度和我的这个做法一样。以为 std 的做法更加高妙。~~ 其实大家写的代码都非常简洁，是我比较糖，写了 5KB。

正文

你会发现那个式子可以分为 “基本贡献” 和 “额外贡献” 两个部分。基本就是指的，无论中间点选什么都会造成的贡献，额外部分的贡献依照中间点决定。

然后自然重点是在计算额外贡献上。位运算相关可以考虑把每一位分开算。考虑对于每一位，能造成额外贡献的点：

这些点要满足左右两侧（指的是路径上的两侧）（可以包括自身）都要出现该位。

那我们可以发现不满足条件的点是从路径两端开始的两段长度，也就是说满足条件的点在路径上形成一个段，一个区间。

那么对于这个段的两个端点，可以使用倍增来找：每个点维护其祖先中第 $2^{k}$ 个该位为 $1$ 的点。

最好的情况就是这两个端点分别在 LCA 的两个子树上，那么我们只需要分别求出 $u, v$ 祖先的第一个该位为 $1$ 的点（需要满足在 LCA 子树内）即可。
不太好的情况就是在同一侧，那么对于那一侧，就用倍增跳到子树下最后一个有 $1$ 的点即可。
注意判断一下边界。

那么我们就可以大力树剖，对于每一位，把满足条件点的权值加1，最终路径上权值最大的点就是能造成的最大贡献。

时间复杂度是 $O (n \log^{2} n \log a_{i})$ ，过不了。

其实树剖是不必要的，我们可以按照每个点到路径的某一端点的距离把路径拍平成链，直接线段树维护，时空复杂 $O (n \log n \log a_{i})$ 。会被卡空间。

考虑空间上把 $O (\log a_{i})$ 压掉。把询问离线下来，对于每个位，把所有询问跑一遍，这样子倍增数组可以重复使用。每个询问把需要线段树区间加的区间存起来，最后再对每个询问处理即可。空间复杂度 $O (n \log n)$ 。

以上只是本题目考察点的 $20 %$ 。你需要一定的卡常技巧。这里我通过优化函数调用，尽量复用数据以及从 OI 维基上面复制快读模板可以极限地通过本题。

「精选模拟赛」#3

1973B

直接二分，然后求一个区间的或和可以用拆位前缀和的方式 $O (\log a_{i})$ 求出。

abc282_e

https://www.luogu.com.cn/article/zl9lf2lp

好题啊！

你可以根据这个东西构造一个完全图（ $i \to j$ 的权值就是选 $a_{i}$ 和 $a_{j}$ 这两个的权值），然后完全图的最大生成树就是我们想要的答案。

证明的话，只要证对于一个生成树存在合法操作方案就行了：很明显可以从叶子往上删。同理也可以通过一个操作方案构造出一个生成树，因此贪心选最大生成树等价于选最优方案。

1795E

垃圾题。

首先，爆炸肯定只会消耗 $a_{i} = x$ 。
其次，爆炸会炸死的范围就是一个金字塔，左边单调增右边单调减。

方法如下：枚举以每个点为金字塔的尖尖，考虑把两边尽可能地削成金字塔，然后全炸掉，最后剩下的再普攻击杀（当然按照题目来说这一步在前面，不过没有什么影响，本质相同）。

这个方法的正确性是很显然的，这里就不证了。

这道题的难点在实现。

这里只介绍【削左边】的情况，削右边是同理的，但是需要做若干变动。

不妨把数组看做一个柱状图，就是每个位置上各有一个高度为 $a_{i}$ 的方块。

假如从某个尖开始，向左边，那些方块就会被 $y = x + k$ 这条直线削掉。我们可以维护每个点的 $f (i) = a_{i} - i$ 值，这样子，设 $x$ 为塔尖，那么 $f (i) > f (x)$ 就是 $i$ 处要被削掉， $f (i) = f (x)$ 就是不用动。

但是 $f (i) < f (x)$ 的情况呢？它比直线还低，因此后面的 $j < i$ 方块会被它影响，限制直线的截距会降低。

因此可以分成若干个段，每个段内都满足 $f (i) \geq f (x)$ ，段之间由 $f (i) < f (x)$ 的点隔开。段内的计算直接用【以 $a_{R}$ 结尾的长度为段长、公差为 $1$ 的等差数列和减去原有区间和】即可。

然后还要考虑一种情况就是不能削出第一象限，所以要判断好负数边界。

具体实现可以每个点用单调栈找到【前面第一个 $f (i) < f (x)$ 】，然后找到削到哪里就变成 $0$ 了。

另外塔尖在计算时可以直接把已经成塔部分跳过，这部分可以预处理。但是我发现上述方法好像包含了这个过程，所以应该是不必要的？

另外的提示：削右边的时候判定式是 $g (x) = a_{i} + x$ 。

arc084_b

https://www.luogu.com.cn/article/k5srljmo

不妨搞一个无限大的图，其中点 $i$ 向 $10 i$ 连边权为 $0$ 的边，然后点 $i$ 向 $i + 1$ 连边权为 $1$ 的边。（特别的， $0$ 不参与，后面你就知道原因了）

然后这样子，因为每个数都能被如此 *10, +1 操作表出，并且你会发现到那个点的路径就是它的数位和。

那么问题就转化为了到任意一个 $k$ 的倍数的点的最短路。

但显然是做不了的，因此我们把值域压缩到 $k$ 以内，按照模 k 同余重新建图，这样子的话我们只需要知道 1 到 0 点的最短路就行了，复杂度已经足够被接受。

当然你是从 $1$ 开始的，所以最后不要忘记把 $1$ 本身的代价加上去。

abc281_g

https://www.luogu.com.cn/article/k5srljmo

考虑因为边权为 $1$ ，所以我们可以得知，对于每个 $< d_{N}$ 的距离至少存在一个点。于是我们对着这个距离分层进行 dp，同层 dp 代表同一距离。那么设 $d p_{i, j}$ 为当前给 $i$ 个点分了层，最后一层有 $j$ 个点的方案数。可得转移方程：

d p_{i, j} = \sum_{k} d p_{i - j, k} \times (\binom{n - (i - j) - 1}{j}) \times 2^{j \times (j - 1) \times \frac{1}{2}} \times (2^{k} - 1)^{j}

详细解释一下：枚举上一层的点数 $k$ ，从 $d p_{i - j, k}$ 转移，系数分别为：

$(\binom{n - (i - j) - 1}{j})$ 表示给这一层的点标号的方案数，即从剩余标号中任选（保留 $n$ ）。注意，如果这是最后一层，那这个东西要改成 $1$ 。
$2^{j \times (j - 1) \times \frac{1}{2}}$ 层内部可以选择任意连边或者不连。（层中共有 $j \times (j - 1) \times \frac{1}{2}$ 种边）。
$(2^{k} - 1)^{j}$ 表示从这一层种的每个点，往上一层连边的方案数。每个点单独连，可以连任意多条，但是不能不连，于是就是 $2^{k} - 1$ 。

然后直接做即可。

「精选模拟赛」#4

2039C1

猜出一个结论： $y$ 的范围 $\leq$ 大于 $x$ 的最小 $2^{i}$ 。

证明的话，考虑如果 $x \oplus y$ 是 $x$ 的因子，那么它一定小于 $x$ 。进而二进制位数一定小于等于 $x$ 的二进制位数。

如果 $x \oplus y$ 是 $y$ 的因子，那么由于它们至少相差两倍，所以二进制位数肯定不同。如果 $y$ 大于上述 $2^{i}$ 的话，那么异或出来一定带有 $y$ 的最高位，就无法成为 $y$ 的因子了。

1077F2

考虑动态规划，设 $f_{i, j}$ 为转发了 $i$ 次，当前考虑到了第 $j$ 张图片并且这张图片将被转发。有方程式：

f_{i, j} = max_{1 \leq j - x \leq k} f_{i - 1, j} + a_{j}

使用单调队列优化即可。

abc285_f

题目的【合法子串】实际上可以转化为以下条件，证明是简单的：

单调不降。
除了最大和最小字符之外，其它字符的数量恰好等于整个串中该字符的数量。也就是说这些字符不在该区间以外的位置出现。

于是我们便可以开若干个树状数组，分别维护区间某字母的数量。

对于单调不降条件，我们可以对于每一个 $i \in [1, n - 1]$ 存一个 01 变量表示 $[a_{i} \leq a_{i} + 1]$ 。然后把它也放到树状数组上维护。区间 $[l, r]$ 单调不减可以通过 $[l, r - 1]$ 的变量和是否等于 $r - l$ 判断。

对于每次操作，直接维护即可。

abc232_g

待补

Gym 104053M

待补

2039C2

对于询问区间较小的可以直接枚举。

对于询问区间较大的，考虑以下几种情况：

考虑大于 $x$ 的最小 $2^{w}$ 。令 $k = m - 2^{w}$ ，那么这个区间 $[1, k]$ 内满足 $x | (x \oplus w)$ 的数的数量为 $⌊ n / k ⌋$ 。这是因为它们异或后肯定不会超出限制 $m$ 。
考虑 $2^{w}$ 以内的数，直接枚举即可。注意要把上面考虑过的那些数排除掉。
考虑 $[k - 2^{w}, m]$ 之内的数，如果它合法并且没有被上面统计过就统计下来。

通过以上考虑足以覆盖所有情况。证明是类似于 T1 的。

「暑假复健赛」#4

T1

考虑一种贪心：先把最前面 $k$ 个放上 $0$ ，后面每隔一个放一个 $0$ 直到不能放为止。

贪心的合法性是显然的。正确性，考虑无法再调整使其更优，每个以 $0$ 结尾的长度大于等于 $k$ 的前缀都顶到上限了。

T2

考虑打表，发现以下规律：

f_{1} = f_{2} = 0, f_{3} = 6 f_{i} = 2 f_{i - 1} + 2 s.t. i > 3

可以直接矩阵快速幂做。

T3

考虑可以把人类分成若干段，每一段指定一个最小化 cost 的位置让他们过去。

这样也能满足题目所要求的【走到最近点】，因为最近点本来就是最优的，动态规划会自动帮助我们抉择。

设 $f_{i, j}$ 为考虑到第 $i$ 个人类（注意先排序），分了 $j$ 段，有方程：

f_{i, j} = {min}_{u = 0}^{i - 1} f_{u, j - 1} + calc (u + 1, i)

其中 $calc (l, r)$ 表示区间内任意选定一个点的总 cost 最小值。

它可以 $O (n^{3})$ 预处理，不过由于常数小，所以写成拙劣的 $O (n^{4})$ 预处理也可以。

T4

考虑把树拍成 dfn 序，这样子每个子树都是连续的，上线段树维护即可。

「精选模拟赛」#5

2050E

待补

2050G

待补

agc012_b

待补

abc254_f

根据《九章》，有如此一种【更相减损术】，其内容是：

gcd (a, b, c, d, e, . . .) = gcd (a, b - a, c - b, d - c, e - d) s.t. a \leq b \leq c \leq d \leq e . . .

那么，我们就可以维护 A,B 两个数组的差分的 gcd，然后查询就查询区间差分 gcd 与 $A_{h 1} + B_{w 1}$ 的 gcd 即可。

abc150_f

待补