VP

时间线

• 8:50-8:55 写 T1
• 8:55-9:20 写 T2
• 9:20-9:43 写 T3（爆搜）
• 9:43-10:24 写 T4
• 10:36-11:06 写 T5

得分

错因与错因分析

C

知识点：思维
错因：没有想到性质，写了个爆搜就看 D 了。

耐心推性质。首先，序列中的最大值与最小值之差不能超过 1，因为假设一种颜色最多出现了 次，则是该种颜色的人至少看到 个人的颜色相同，其他颜色的人能看到 个人的颜色相同。分类讨论可能的可行情况，设最大值出现了 次：

• 所有人的颜色一样，即 且 ；
• 只有一种颜色的数量最多，即 ；
• 有至少两种颜色的数量最多，即 且 。
• 其他的情况都不合法。

D

知识点：图论，bfs
错因：想复杂了，写了个换根 dp，因为全局变量 WA 了。

复习基础。bfs 可以处理从多个点出发，到某个点的最短路，只需要初始把所有叶子节点加入队列，然后跑 bfs 即可。

E

知识点：dp，数论
错因：枚举倍数只有在 时才是 的，可能会被卡成 。

枚举倍数，当且仅当从 1 到 的每个数。

F

知识点：贪心，优先队列
错因：没时间。

加强对于中档题的训练。

不难发现，对于某一段，平均分的时候最优。考虑算每次操作的贡献。假设一个连续的 o 段的长度为 ，要做 次操作。也就是说，要将 个数尽量平均分为 段，答案记为 。令 ，，则有 段有 个数， 段有 段。令 ，则 。对于一段长度为 ，已经被操作了 次的段，再操作一次的代价就是 。用单调队列维护一下最小即可。