专栏文章

SnackOI R1-D 战争与和平 题解

lliangjindong0504
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minpl2ad
此快照首次捕获于
2025/12/02 06:16
3 个月前
此快照最后确认于
2025/12/02 06:16
3 个月前
查看原文

闲话

这题在测试人员里面通过人数第二多。

nn 较小的部分分

爆搜每个元素属于第几组，期望得分 15pts15pts。
状压，时间复杂度 O(4n)O(4^n)，期望得分 30pts30pts。
优化一下枚举子集，时间复杂度 O(3n)O(3^n)，期望得分 35pts35pts。

特殊性质

特殊性质 BC 一起看吧。
容易发现区间长度取 11，22 的时候是非常优秀的，贡献很大，以此进行贪心即可。期望得分 45pts45pts。
特殊性质 AD 好像没啥特殊做法。

正解

发现，我们将数组排序后，一定会选择多个连续的段。
实际上这个很好理解，因为如果我们以此分完段后，有两组交换了一个元素，那么贡献一定不优。所以排序后取连续段是最优的。
O(n2)O(n^2) 暴力 dp，期望得分 65pts65pts。
我们发现 dp 式子好像非常有趣，就是 dpi=max⁡{dpj−1+si−sj−1−ai+aj}dp_i = \max\{dp_{j-1} + s_i - s_{j - 1} - a_i + a_j\}，ss 为前缀和数组。发现这个东西可以用线段树或者 set 优化，时间复杂度 O(nlog⁡n)O(n \log n)，期望得分 85pts85pts。
用单调队列优化，时间复杂度线性，期望得分 100pts100pts。实际上上面的复杂度都是除了排序以外的复杂度。所以正解实际上还是 O(nlog⁡n)O(n \log n) 的，只是常数很小而已。
代码献上。
CPP
#include <bits/stdc++.h>
 
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

const int MAXN = 5e6 + 10;
const i64 INF  = 1e18;

int n, l, r;

int h, t;
int q[MAXN];

i64 a[MAXN];
i64 dp[MAXN];
i64 sum[MAXN];

i64 f (int x) {
	return dp[x] - sum[x] + a[x + 1];
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	std::cin >> n >> l >> r;
	for (int i = 1; i <= n; ++i) {
		std::cin >> a[i];
	}
	std::sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) {
		sum[i] = sum[i - 1] + a[i];
	}
	
	h = 1, t = 0;
	if (1 - r <= 0 && 0 <= 1 - l) {
		q[++t] = 0;
	}
	
	for (int i = 1; i <= n; ++i) {
		while (h <= t && q[h] < i - r) {
			++h;
		}
		
		if (h <= t) {
			int j = q[h];
			dp[i] = f(j) + sum[i] - a[i];	
		} else {
			dp[i] = -INF;
		}
		
		int id = i - l + 1;	
		if (id >= 0) {
			while (h <= t && f(q[t]) <= f(id)) {
				--t;
			}
			q[++t] = id;
		}
	}
	std::cout << dp[n];
 
	return 0;
}

评论

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

正在加载评论...