2023/10/06 模拟赛 总结
时间安排
07:40 - 08:35
看题，写 A,B。
08:35 - 09:30
想 C，写 C 暴力，回来拍 A,B。
09:30 - 10:20
想 C，写 C，拍 C。
10:20 - 11:00
写 D 暴力。想 D，中间 C 炸了，调了会 C。
11:00 - 11:40
写 D 的包，罚坐，瞪了几遍代码。
总结反思
不熟悉根号分治的套路。
题解
A.
贪心扫一遍。
B.
区间 dp，转移平凡。
C.
形式很像异或为 0，只有全部相同时不同。先用上两个边界的异或构造。
没有这种情况只需要一条边上交替 01，分讨每种情况容易计算答案。
D.
答案有上界 \(n+k\)，所以块数不超过 \(\frac{n+k}{k+1}\)。
对 \(k\) 根号分治，小的每次跑 dfs，大的树形背包一遍，求出连通块数一定时最小选点数，每次暴力扫。