《重回到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)}\)。
这样的做法在
luogu的机子上跑了 \(100\ \text{pts}\) 。\(_{\text{Code}}\)
不过好像还有其他优化，再说再说
听说今年 CCF 上了少爷机/jy/jy/jy