Codeforces Round 694 C. Strange Shuffle
$n$个人坐在一圈玩游戏, 分别标号$1 \sim n$. 初始每人手里有$k$张牌($2|k$). 一次洗牌, 每个人都会进行这样的操作: (当前手牌设为$x$)把 $\lfloor\frac{x}{2}\rfloor$ 张牌给左边的人, 把 $\lceil\frac{x}{2}\rceil$ 张牌给右边的人.
然而, 人群中有一个🤡, 每次他只会把所有牌给右边的人.
? p用来询问当前局面, $p$ 号玩家有几张牌.每次询问后都进行一次洗牌.
任务是用不超过 $1000$ 次询问, 找出🤡,
! p用来回答找到的🤡.$4 \le n \le 10^5, 2 \le k \le 10^9, 2 | k$
手玩可以发现, 🤡的牌数永远是 $k$, 而且在前 $\frac{n}{2}$ 次洗牌中, 🤡左边的人的牌比 $k$ 少, 右边的比 $k$ 多.
为什么要限制 $\frac{n}{2}$ 呢? 首先, 我们能用的询问很少, 根本到达不了 $\frac{n}{2}$, 所以可以直接假定就是前 $\frac{n}{2}$ 步. 其次, 大于这个数的时候, 就会出现少的和多的交换的情况, 这里不好处理, 我们就不处理.
证明一下:
设$i, j$ 是关于 $p$ 对称的两个位置. 某次洗牌前的序列是$a$, 洗牌后的序列是$b$.
先证明, $b_i + b_j = 2k$.
注意到有
$$b_i = \lceil\frac{a_{i-1}}{2}\rceil + \lfloor\frac{a_{i+1}}{2}\rfloor$$ $$b_j = \lceil\frac{a_{j-1}}{2}\rceil + \lfloor\frac{a_{j+1}}{2}\rfloor$$ $$b_i + b_j = \left ( \lceil\frac{a_{i-1}}{2}\rceil + \lfloor\frac{a_{j+1}}{2}\rfloor \right ) + \left ( \lceil\frac{a_{i+1}}{2}\rceil + \lfloor\frac{a_{j-1}}{2}\rfloor \right )$$
初始局面满足 $a_i + a_j = 2k$, 不妨设所有局面满足, 那么对于上式, 有 $a_{i-1} + a_{j+1} = 2k, a_{i+1} + a_{j-1} = 2k$.
又因为有这样的一个性质: $x + y = 2m, \lceil\frac{x}{2}\rceil + \lfloor\frac{y}{2}\rfloor = 2m$. 讨论一下 $x, y$ 的奇偶性就能得证.
我们代入, 就能够得到 $b_i + b_j = 2k$
归纳法, 证得任意局面都满足这个性质.
所以有 $a_{p-1} + a_{p+1} = 2k$, 而
$$b_p = \left ( \lceil\frac{a_{p-1}}{2}\rceil + \lfloor\frac{a_{p+1}}{2}\rfloor \right ) - a_p = 2k - k = k$$
(依然需要归纳法)
这样就证得了🤡的牌数永远是 $k$.
再证$p$右边的比$k$多.
这里的证法很巧妙, 转化成证 $p+1, p+2, \dots n, 1, 2, \dots p-1$ 不递增. 还是归纳法, 第$0, 1$次显然成立, 且第$1$次有 $b_{i+1} < b_{i}$
$$b_{i+1} = \lceil\frac{a_{i}}{2}\rceil + \lfloor\frac{a_{i+2}}{2}\rfloor$$ $$b_{i} = \lceil\frac{a_{i-1}}{2}\rceil + \lfloor\frac{a_{i+1}}{2}\rfloor$$
不妨假设所有局面都成立, 就有$a_{i} \le a_{i-1}, a_{i+2} \le a_{i+1}$, 所有有 $b_{i+1} \le b_{i}$, 归纳, 得证.
又由于第一次还有 $b_{p-1} \le b_p \le b_{p+1}$
所以这样就证明了🤡左边的人牌数比$k$少, 右边的比$k$多.
上面的东西只要手玩一下就能猜出来, 严格证明考场谁推啊
下面才是精髓:
我们把这个环分成 $\sqrt{n}$ 块, 先让他跑 $\sqrt{n}$ 次. 那么一定有一个连续的 $\sqrt{n}$, 满足, 这些数比 $k$ 大, 且跨过了某两块的分界线. 那么就可以再用 $\sqrt{n}$ 次询问, 问每一块的第一个数, 找到一个大于 $k$ 的数. 这样, 根据上面的结论, 🤡一定在这个数左边. 于是可以对从他开始的一段长度为 $\sqrt{n}$ 的序列进行二分查找(很容易证明这个序列里的数满足单调性).
但是! 我们这样做会 WA77.
为什么呢?
经过仔细分析偷看数据, 发现, 可能每一块的第一个数正好都是 $k$. 比如四个人, 初始每人两张牌, 🤡是$1$, 这样就会得到 $2, 3, | 2, 1 |$, 然后就找不到大于 $2$的数.
怎么办呢?
那我们就多跑一个. 当每一块的第一个都是 $k$, 就看每一块的第二个. 这样就行了.
(好像这种情况只有 4 2 1 会出现, 应该也可以通过小数据直接跑完遍历求)
总询问不会超过 $2\sqrt{n} + \log \sqrt{n}$ (如果要跑第二个的话, 也只是小数据).
|
|