当前位置：首页 > news >正文

CSP-S 2025口胡记

news 2026/5/12 1:08:38

《重回到CSP-S的赛场上，发现我终究是菜狗》

菜狗只做了前两个题。

社团招新

这在 luogu 上是一道黄，但是它是一道贪心

最开始注意到 a[i][d] 可能会相等（这样一个不重要的条件），然后就开始分讨+贪心，结果我错了。

这个题应该算是一道反悔贪心，针对与 a[i][d] 可能会相等的情况，完全没有必要去想怎么处理它，对于 \(i=1,2,\cdots,n\) 取满意度值最大的部门分配，而对于相等的情况先随便选一个部门。

然后这样就可以发现至多只有一个部门人数会大于 \(\frac{n}{2}\)，不像上文分了不知道多少情况。

对于这样一个人数大于 \(\frac{n}{2}\) 的部门，将多余的人数调整到其他部门去，这些人需要满足调整后（即相差）的贡献最小的，排序即可。\(_{\text{Code}}\)

道路修复

这在 luogu 上是一道蓝，我感觉相比T1的贪心要好写一些（（菜菜，现在已经只会口胡出假做法了

Sol 1

在考虑不改造任何一个乡镇的情况下，构建原图的最小生成树为最优解。

然而在考虑改造的情况下，剩下的 \(m -n + 1\) 边也不会有额外的贡献。

对于乡镇的数量 \(k\), 满足 \(k\le 10\)，即 \(2^k\le1024\)。

那么目前先考虑将原图的最小生成树的 \(n - 1\) 计算出来，假设选取了 \(\ell\) 个乡镇 \(S\) 进行改造，那么就会多出 \(\ell \cdot n\) 条边，这 \((\ell + 1)\cdot n - 1\) 条边的最小生成树的边权和加上 \(\ell\) 个乡镇的 \(c_i\) 即为此时的答案。

枚举每个乡镇是否改造，取其最小值即为最终答案。时间复杂度为 \(\text O{\left(m\log m+2^k\cdot k n\log kn\cdot \alpha(n)\right)}\)。

这样的做法在 luogu 的机子上跑了 \(80\ \text{pts}\) 。\(_{\text{Code}}\)

Sol 2

在 Sol 1 的基础上，对边权离散化后桶排。时间复杂度为 \(\text O{\left(m+2^k\cdot k n\cdot \alpha(n)\right)}\)。

Sol 3

在 Sol 1 的基础上，将所有乡镇的 \(k\cdot n\) 边与最小生成树的 \(n - 1\) 条边统一排序，然后在后续的枚举过程中判断那些边需要被加入即可。时间复杂度为 \(\text O{\left(m \log m + kn\log kn+2^k\cdot k n\cdot \alpha(n)\right)}\)。