Codeforces Round 694 C. Strange Shuffle

警告
本文最后更新于 2021-01-14,文中内容可能已过时。

$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}$ (如果要跑第二个的话, 也只是小数据).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
int n, k;

int query(int x) {
	int y;
	printf("? %d\n", x);
	fflush(stdout);
	scanf("%d", &y);
	return y;
}

int main() {
	scanf("%d%d", &n, &k);
	int m = floor(sqrt(n));
	for (int i = 1; i <= m; i++)
		query(1);
	for (int i = 1; i <= n; i += m) {
		if (query(i) > k) {
			int r = i;
			int l = r - m;
			while (l <= r) {
				int mid = (l + r) >> 1;
				int modmid = mid;
				modmid = ((modmid - 1) % n + n) % n + 1;
				int x = query(modmid);
				if (x > k)
					r = mid - 1;
				else if (x < k)
					l = mid + 1;
				else
					printf("! %d\n", modmid);
			}
		}
	}
	for (int i = 2; i <= n+1; i += m) {
		if (i > n)
			i = n;
		if (query(i) > k) {
			int r = i;
			int l = r - m - 1;
			while (l <= r) {
				int mid = (l + r) >> 1;
				int modmid = mid;
				modmid = ((modmid - 1) % n + n) % n + 1;
				int x = query(modmid);
				if (x > k)
					r = mid - 1;
				else if (x < k)
					l = mid + 1;
				else
					printf("! %d\n", modmid);
			}
		}
	}
	return 0;
}