XXI Open Cup Grand Prix of Korea H.Alchemy @ Wings            分类 ACM
发布于 星期四, 九月 16 日, 2021 年
更新于 星期五, 九月 17 日, 2021 年

题目

题意

数值为 $i (0 \le i < n)$ 的数有 $c_i$ 个. 从中选取一些数 $S, |S| > 0$, 变为 $\rm{mex}\{S\}$ 放回. 最后剩一个数, 问这个数最大是多少.

$1 \le n \le 10^5, 0 \le c_i \le 10^9, \sum c_i \ge 1$

题解

不会思考的人有难了!

一开始想的是把某点之后所有的数单独拎出来变成 $0$, 然后 $0$ 往上推. 这样就几个问题. 首先是这个点会不会在同一个数里, 然后是即使往上推, 如果有多的, 我还可以拿出来变成 $0$. 比如 $0, 1, 1, 1, 2$, 可以 $2$ 不动, 但是拿出两个 $1$ 变成 $0$. 还有一个, 不是说要"物尽其用", 有时候可以通过"放弃"来达到更好的结果. 假设有 $4, 5$ 两个数, 虽然我可以变成两个 $0$, 但是如果恰好多出来一个 $0$, 比如说最后变成了 $0, 3$, 然后再做的话答案就是 $2$; 但其实可以"丢弃"一个数, 即取出 $4, 5$, 取 $\rm{mex}$ 为 $0$. 这样就只有一个 $3$ 了.

这些问题都是不会思考导致的, 没有反问一下自己, 真的是这样吗. 以后注意, 一定要多次反问自己.

接下来就说一下正解.

特判 $\sum cnt_i = 1$.

可以想到二分答案 $k$, 如果最后要得到 $k$, 那么 $0 \sim k-1$ 的数至少要有 $1$ 个, 其他随意. 这样的话, 只要取所有数的 $\rm{mex}$ 就行了. 虽然有的数还可以变成 $0$, 但是完全没必要了. $k$ 及之后的数可以变为 $0$, 考虑 $k$ 之前, 从 $k-1$ 向 $2$ 枚举. 为什么这样呢? 从前向后枚举就会出现"不知道后面可不可以拿一些出来变成$0$". 而从后向前枚举就避免了这个问题, 当然这时候就需要统计一个"当前需要值", 去和枚举到的数比较, 而不是像错误的从前向后枚举去直接推结果.

可以发现, 如果 $cnt_{k-1}$ 是 $0$, 那么就需要去凑一个 $k-1$ 出来. 怎么凑呢? 当然是再来一组 $0 \sim k - 2$. 然后会发现, 需要的"组数"是随着枚举而非严格递增的. 假设当前枚举值为 $i (2 \le i < k)$, 设需要的组数为 $need$, 即 $0 \sim i-1$ 至少需要 $need$ 个. 在枚举的过程中, 尝试去维护 $need$: 若 $cnt_i \ge need$, 即能够满足要求, 并且多了 $cnt_i - need$ 个 $i$, 可以变成 $0$; 若 $cnt_i < need$, 即不够满足要求, 还差 $need - cnt_i$ 个 $i$, 那么就需要 $0 \sim i-1$ 各再多 $need - cnt_i$ 个, 即 $need += need - cnt_i$.

注意到 $0$ 和 $1$ 是特殊的, 他们可以相互转换, 所以我们只做到 $2$, 现在的 $need$ 就是, 需要多少个 $0$ 和 $1$. 只要他们个数加起来不小于 $2need$ 即可.

细节, 由于 $need += need - cnt_i$, 会发现 $need$ 是指数级上升的. 而 $cnt_i \le 10^9$, 所以当 $need > 10^14$ 后一定无解 (🌿写题时想错了写的 $10^9$ 但是过了), $10^14$ 是 $10^5$ 个 $10^9$ 都变为 $0$ 算得的. 特判一下.

再一个是二分的上界确定. 由于第 $i$ 数需要 $2^{i-1}$ 个 $0$ 凑出来, 所以我们对 $10^9 \times 2^i$ 求和, 得到不超过 $10^9 \times 2^{n+1}$, 即答案不超过 $\log(10^9 \times 2^{n+1}) < 30n$ (写题时又错了但是A了笑死)

代码
const int MAXN = 3e6 + 10;	// 注意开 30n

LL a[MAXN], sum = 0, cnt[MAXN];
int n;

bool check(int k) {
	for (int i = 0; i < min(k, n); i++)
		cnt[i] = a[i];
	for (int i = k; i < n; i++)
		cnt[0] += a[i];
	LL need = 1;
	for (int i = k-1; i > 1; i--) {
		if (need > 1e14)
			return false;
		if (cnt[i] < need)
			need += need - cnt[i];
		else
			cnt[0] += cnt[i] - need;
	}
	return cnt[0] + cnt[1] >= need * 2;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", a + i);
		sum += a[i];
	}
	if (sum == 1) {
		for (int i = 0; i < n; i++)
			if (a[i] == 1)
				printf("%d\n", max(1, i));
	}
	else {
		int l = 1, r = 30 * n, ans = -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (check(mid)) {
				ans = mid;
				l = mid + 1;
			}
			else
				r = mid - 1;
		}
		printf("%d\n", ans);
	}
	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. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

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

运动

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

音乐

  • 吉他
  • 词曲
  • 流行

玩具

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

追星

  • VAE
  • Benedict Cumberbatch