题解：P17216 [ICPC 2017 Nanning R] The Chosen One

· · 题解

我们列举一个长度为 16 的队列：

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

第一次操作：

\to 2,4,6,8,10,12,14,16

其中标红的是被移除的人的编号。

第二次操作：

\to 4,8,12,16

第三次操作：

\to 8,16

以此类推。

很容易发现，第 i 次操作后的序列中每个数的差值总是为 2^{i} 且每个数从 2^{i} 开始。于是我们可以枚举最大的 x 使得 2^{x}<n。