[CF1943C] Tree Compass 题解

不会 2300，完蛋了/lh

题目链接

题目分析

容易想到先求出直径，然后以直径中点为圆心画 \({d \over 2} + O(1)\) 个圆。

具体地，设直径点数为 \(d\)。当 \(d\) 为奇数时，上述构造需要 \(d + 1 \over 2\) 次操作；当 \(d\) 为偶数时，上述构造需要 \({d \over 2} + 1\) 次操作。

尝试证明上述构造是最优的。观察到对于一条链，一次操作至多将链上两个点染成黑色，因此 \(d\) 为奇数的情况已经最优，但是 \(d\) 为偶数的情况不一定。

手画一下，发现 \(d = 4\) 的情况确实不一定最优，但是 \(d = 6\) 的情况似乎一定最优，但是 \(d = 8\) 的情况又不一定最优。因此可以猜测上述构造方式最优当且仅当 \(4 \nmid d\)。

当 \(4 \nmid d\) 时，上述构造最优是易证的：如果一次操作将链上两个点染成黑色，那么这两个点在链上的位置一定同奇偶。

当 \(4 \mid d\) 时怎么办？这时候就到了本题诈骗的地方。\(n \le 2 \times 10^3\) 的范围很容易让人想到 \(O(n^2)\) 的复杂度，然而正解是 \(O(n)\) 的。考虑把两个直径中点都利用起来，对这两个点同时进行一次距离为 \(1\) 的操作能把中间四个点都染黑，再对这两个点同时进行一次 \(d = 3\) 的操作能够把中间八个点都染黑，依此类推，我们构造出了 \(d \over 2\) 次操作的解法。这一定是最优的。

时间复杂度 \(O(n)\)。

提交记录