Codeforces Round 694 C. Strange Shuffle @ Wings            分类 ACM
发布于 星期四, 一月 14 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

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

代码
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;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch