ARC188B sol

Xuan104_WA

2024-11-23 22:52:05

Solution

题面大意

在一个圆上有 N 个间隔相等的点,依次编号为 0,1,\dots,N−1,Alice 在点 0 处,Bob 在点 K 处。

初始时,所有点的颜色都是白色。从 Alice 开始,他们交替执行以下操作:

如果操作符无法执行满足上述条件的操作,则操作序列就此结束。双方合作并做出最佳选择,使最后被涂成黑色的点的总数达到最大。

确定操作序列结束时是否所有点都被染成黑色,是则输出 Yes,不是则输出 No

思路

以下所有点的编号对 N 取模。

当第一个染色点确定时,两人的每一步操作都是确定的:Alice 第一步染点 x,Bob 第二步只能染 x 关于点 K 的对称点……

而在对称的过程中,如果 Bob 上一次染了点 x,则 Alice 这一轮会染点 -x;如果 Alice 上一次染了点 x,则 Bob 这一轮会染点 2K-x

而如果 Alice 第一步绘制的是点 0,那么两人的染色顺序将是:

0,2B,-2B,4B,-4B,\dots

这种情况一直持续到所有与 0 距离为 \gcd(N,2K) 的点全部染色为止。如果 N 为偶数且 Alice 第一步绘制的是点 \frac{N}{2},最终的染色序列也是一样的。此时整个圆在 Alice 和 Bob 看来都是对称的。

此时考虑已经被染色的点数 X=\frac{N}{\gcd(N,2K)}

X 是奇数,则此时轮到 Bob 染色。容易知道此时点 K 一定被染色了。

X 是偶数,则此时轮到 Alice 染色。容易知道 N 为偶数且点 0 的对径点已经染色,Alice 无法继续染色。而此时 \gcd(N,2K) 至少是 2,所有点并没有全部染色,也无法全部染色。

综上,可以全部染色的条件为一下两者之一:

直接判断输出即可,代码就不放了。