【比赛记录】蓝桥杯 24 省 A（周测 #11）

KSCD_ · 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=k 或 j=l，与已经确定的条件 i\ne k,j\ne l 冲突，所以组数为 0。

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

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