专栏文章

题解：P9842 [ICPC 2021 Nanjing R] Klee in Solitary Confinement

WWZwangchongming
P9842题解参与者 3已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mip2zxn8
此快照首次捕获于
2025/12/03 05:19
3 个月前
此快照最后确认于
2025/12/03 05:19
3 个月前
查看原文
可莉可爱捏！但是没有芙芙可爱！
Solution：
直接考虑枚举众数的值。
假设枚举的这个众数的值为 xx。那么我们可以知道，如果操作了一个区间 [l,r][l,r]，且这个区间里有 aa 个 xx 和 bb 个 x−kx-k，那么最后 xx 的个数就会增加 b−ab-a 个。
所以就有一个很自然的贪心：让 xx 产生的贡献为 −1-1，x−kx-k 的贡献为 11，其余的贡献为 00，再求一个最大子段和。那么 xx 的最多出现次数只需要再加上 xx 原来的出现次数。最后对所有 xx 取一个最大值就可以得到答案。
但是这个贪心的时间复杂度是 O(n2)O(n^2) 的。
明显，既不是 xx 又不是 x−kx-k 的那些位置对答案不会产生影响。因此，对于每一个 xx，单独把所有值为 xx 或 x−kx-k 的位置存进一个 vector 里，在每个 vector 中做最大子段和。这样每个数最多被放进 22 个 vector，时间复杂度 O(n)O(n)。
Main code：
CPP
void solve() {
	n = read(), k = read();
	for(int i = 1; i <= n; i++) {
		a[i] = read() + 2e6;
		vec[a[i]].eb(-1), vec[a[i] + k].eb(1);
	}
	int ans = 0;
	for(int i = 0; i <= 4000000; i++) 
		if(vec[i].size()) {
			int res = 0, sum = 0;
			for(auto &x : vec[i]) if(x == -1) res++;
			ans = max(ans, res);
			for(auto &x : vec[i]) {
				sum = max(sum + x, x);
				ans = max(ans, res + sum);
			}
		}
	printf("%d\n", ans);
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...