题解：AT_agc068_a [AGC068A] Circular Distance

BPG_ning · 2025-11-08 21:16:14 · 题解

感觉套路但是不会做。

经典的转化为 \max\leq d 的计数。考虑断环成链，并钦定选择位置 0，最后给答案 \times \frac{L}{n} 即可。

对于一对选择的位置 l,r(r>l)，需要满足 r-l\leq d 或 r-l\geq L-d，意味着 [d+1,L-d-1] 是不能选的。并且对于 [0,d] 和 [L-d,L) 内部的方案是不会矛盾的，所以考虑这两个区间之间的限制关系。

具体来说，对于一个选择的点 x(0\leq x\leq d)，在 [x+d+1,L+x-d-1] 是不可以选的。我们把 [0,d] 这一段向右平移 d+1 个单位，设 l=L-2d-2，那么原问题变成：

在 [d+1,L] 之间给每个点做选择，可以染白(选左边)、染黑(选右边)和不选，一个白点 x 需要满足 [x,x+l] 之内不能有黑点，要求 d+1 是白点，L 是黑点。

发现限制只与黑白连续段的分界点有关，枚举黑白连续段数量，可以插板求出方案数，时间复杂度 O(\frac{L}{l})。总时间复杂度 O(L\ln L)。