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

记录

A 模拟，C 是倍增/LCA/树上差分板子，之后回来看发现 B 是二分，全写了。D 贪心，用线段树优化，写完又调一共一个小时。

最后 A 过了，B 由于避开精度问题乘了分母导致需要开 __int128，但是在乘法上没有强转导致溢出，挂了 $30$；C 把 $i$ 手误敲成 $y$ 过样例所以爆零了；D 由于需要严格次大值，但写成了次大值挂了 $10$ 分。赛后杰哥讲了 E 感觉也能做。

题解

A. 训练士兵

枚举 $i\in[1,1e6]$ 表示每个人的第 $i$ 次训练，若第 $i$ 次不花费 $S$ 组团训练，而是分别单独训练，代价会变成 $\sum_{k=1}^n[c_k\ge i]p_k$，所以预处理 $t_i$ 表示 $\sum_{k=1}^n[c_k=i]p_i$。初始令 $now$ 为所有 $p_i$ 的和，每处理完第 $i$ 次就减去 $t_i$，直到 $now<S$ 时退出，此时的 $i-1$ 便为最终组团训练的次数，最终计算即可。

B. 成绩统计

先推式子，得到方差为 $\frac{1}{k}(\sum_{i=1}^k a_i^2-\frac{sum^2}{k})<T$，为了避免精度问题，左右同乘 $k^2$，得到 $k\sum_{i=1}^k a_i^2-sum^2<T\times k^2$。

然后发现这个问题有单调性，即若前 $i$ 个数可以满足题意，则前 $i+1$ 个数一定可以满足，因为一定可以按照前 $i$ 个数的方法选。同时为了使方差尽可能小，所选的一定是排好序后连续的 $k$ 个数。所以考虑进行二分答案。

check 时把前 $x$ 个数拿出来排序，然后预处理前缀和和前缀平方和，找到最小的区间与 $T\times k^2$ 比较即可。要注意如果为了避免精度问题这样做，最大数会到 ${10}^{20}$，开个 __int128 就行，注意乘的时候强转类型即可。

C. 零食采购

考虑树上差分，设 $f_{i,u}$ 表示从根到 $u$ 的路径上 $c_k=i$ 的 $k$ 的个数。分别对 $i\in[1,20]$ 树上差分求出路径上是否有 $i$ 即可。

D. 封印宝石

显然贪心，即从第一个盒子起都尽可能让魔力值大，在此前提下再尽可能减少体力消耗。所以从 $1$ 到 $n$ 依次填，每次从 $[i,\min(i+k,n)]$ 中取能取且最靠前的最大值，并将对应值赋为 $-1$ 表示已经用过即可。由于不能有魔力值相同的相临盒子，所以需要求出最大值和严格次大值依次尝试，线段树维护即可。

E. 因数计数

值域小，为了方便表示设值域 $P={10}^5$。先开桶 $t_x$ 表示 $x$ 出现的次数。同时预处理出每个数编号不相等的因数个数 $s_x$ 和倍数个数 $b_x$，时间复杂度为调和级数 $O(P\ln P)$。

考虑先算出 $i\ne j$ 且 $a_i\mid a_j$ 的 $(i,j)$ 数量 $k$，枚举较小数 $m$，得 $m=\sum_{x=1}^{P}t_x\times b_x$。

有了以上问题的答案，平方一下就是 $a_i\mid a_k,a_j\mid a_l$ 且 $i\ne k,j\ne l$ 的 $(i,j,k,l)$ 组数，还需要容斥减去 $i=j,i=l,k=j,k=l$ 的组数。

首先先减去满足一个条件的：

• $i=j$，较小数相等，枚举这个数 $x$，取两个倍数，组数为 $\sum_{x=1}^P t_x\times b_x^2$。
• $k=l$，较大数相等，枚举这个数 $x$，取两个因数，组数为 $\sum_{x=1}^P t_x\times s_x^2$。
• $i=l$ 或 $j=k$，即一组中较大数与另一组中较小数相等。枚举相等的中间值 $x$，取一个因数和一个倍数，组数为 $\sum_{x=1}^P 2(t_x\times b_x\times s_x)$。

还需要加上满足两个条件的：

• $i=j$ 且 $k=l$，此时两个较小数和两个较大数分别相等，组数即为最初求出的 $(i,j)$ 数量 $m$。
• $i=l$ 且 $j=k$，由于倍数的要求限制了 $i\le k,j\le l$，所以此时 $i,j,k,l$ 均相等，枚举相等值 $x$，组数为 $\sum_{x=1}^Pt_x(t_x-1)$。
• 其他四种情况都会产生 $i=k$ 或 $j=l$，与已经确定的条件 $i\ne k,j\ne l$ 冲突，所以组数为 $0$。

之后满足三个或四个条件也会产生同样的冲突，组数均为 $0$，不用处理。

这样就做完了，但是由于 $n^4$ 达到了 ${10}^{20}$ 级别，开 __int128 才能确保通过。