20231019 NOIP#24总结
时间安排
7:40~8:10
看题，\(A,B,C\) 各会一点，\(D\) 没想法。
8:10~8:30
写 \(A\) 的暴力。
8:30~9:00
写 \(C\) 的暴力。
9:00~9:30
会 \(A\) 写了。
9:30~11:00
马上看出了 \(B\) 的做法，但是可能太久没写了写挂了，调了一个小时。
11:00~11:40
\(D\) 写半天看错题意，后来一下想出了两档的做法，可惜还剩 \(10\) 分钟。
总结反思
- 仔细读题，好好手模样例
- 加快比赛节奏
题解
A.数学
值域只有 \(1e6\)，直接开桶统计个数。枚举答案，将所有答案倍数的个数都加起来，若 \(\geq k\) 则答案合法。复杂度是调和极数。
B.边带权并查集
边带权并查集板子。
C.状压
考虑将边权从大到小加入，设 \(f[s]\) 表示已经确定了 \(s\) 集合的边权情况下的最小值。新加入一条边时，由于是从大到小加入，产生的代价就是连接的两个联通块点权和的乘积在乘上边权，用并查集维护每个状态即可。