专栏文章

P10806 [CEOI 2024] 洒水器

FFracture_Dream
P10806题解参与者 3已保存评论 4

文章操作

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

当前评论
4 条
当前快照
1 份
快照标识符
@miq4x3f6
此快照首次捕获于
2025/12/03 23:01
3 个月前
此快照最后确认于
2025/12/03 23:01
3 个月前
查看原文

前言

怎么题解区全是贪心的做法？来贡献一篇 dpdp 做法的题解。
"膜拜"同机房巨佬 @TTpandas 试图通过复杂度和正确性都错误的奇技淫巧通过此题。

题目大意

一个数轴上有 nn 个洒水器和 mm 个花盆，洒水器的强度为 kk。
一个洒水器可以浇灌位于 [si−k,si][s_i-k,s_i] 或者 [si,si+k][s_i,s_i+k] 中的花朵，现在请你求出最小的 kk，使得 mm 朵话都至少被一个洒水器浇灌到，要求输出方案。

思路

首先一眼二分答案，考虑如何 check。
如果你做过 CF1476F，那么这道题就很简单了，因为你会发现这就是个经典的前缀覆盖问题。
令 dpidp_i 表示考虑完前 ii 个洒水器，能够覆盖的最长花盆前缀。
令 lasRilasR_i 表示最大的 jj 满足 fj<sif_j < s_i，即洒水器往右旋转不能覆盖到的最靠左的花盆。
令 lasLilasL_i 表示最大的 jj 满足 fj≤si∧fj≥si−kf_j \le s_i \wedge f_j \ge s_i-k，即洒水器向左旋转可覆盖到的最靠右的花盆。
令 LiL_i 表示最大的 jj 满足 fj<si−kf_j < s_i - k，即洒水器向左旋转仍无法覆盖到的最靠右的花盆。
令 RiR_i 表示最大的 jj 满足 fj≤si−k∧fj≥sif_j \le s_i - k \wedge f_j \ge s_i，即洒水器向右旋转可覆盖到的最靠右的花盆。
显然这些值是很好求的，重点在于 dpdp 数组的转移。
有如下三种转移：
  • dpi←dpi−1dp_i \leftarrow dp_{i-1}，这是显然的。
  • 若 dpi−1≥lasRidp_{i-1} \ge lasR_i，当前洒水器右旋，那么 dpi←max⁡{Ri,LasLi}dp_i \leftarrow \max\{R_i,LasL_i\}。
  • 找到最小的 ll 满足 dpl≥Lidp_l \ge L_i，当前洒水器左旋，显然将 [l+1,i−1][l+1,i-1] 中的洒水器右旋。那么
dpi←max⁡{max⁡l<j<i{Rj},LasLi}dp_i \leftarrow \max\{\max_{l < j < i}\{R_j\} , LasL_i\}
最后判断一下 dpn≥mdp_n \ge m 即可。
注意 dpdp 的时候记录一下转移路径，输出方案是容易的。

代码

时间复杂度 nlog⁡2nn\log^2n，但其实精细实现可做到 nlog⁡nn\log n，不过没有这个必要，因为不卡常。
这里只给出 check 的核心代码。
CPP
bool check(int mid) {
	for (int i = 1 ; i <= n ; i ++) {
		int k = lower_bound(f + 1 , f + m + 1 , s[i] - mid) - f - 1;
		if (f[k] < s[i] - mid) L[i] = k;
		else L[i] = 0;
	}
	for (int i = 1 ; i <= n ; i ++) {
		int k = upper_bound(f + 1 , f + m + 1 , s[i] + mid) - f - 1;
		if (f[k] >= s[i] && f[k] <= s[i] + mid) R[i] = k;
		else R[i] = 0;
	}
	for (int i = 1 ; i <= n ; i ++) {
		int k = upper_bound(f + 1 , f + m + 1 , s[i]) - f - 1;
		if (f[k] >= s[i] - mid && f[k] <= s[i]) lasL[i] = k;
		else lasL[i] = 0;
		lasR[i] = lower_bound(f + 1 , f + m + 1 , s[i]) - f - 1;
	}
	for (int i = 1 ; i <= n ; i ++) Max[i][0] = R[i];
	for (int j = 1 ; j <= 17 ; j ++) {
		for (int i = 1 ; i + (1 << j) - 1 <= n ; i ++) {
			Max[i][j] = max(Max[i][j - 1] , Max[i + (1 << j - 1)][j - 1]);
		}
	}
	for (int i = 1 ; i <= n ; i ++) {
		dp[i] = dp[i - 1] , pre[i] = i - 1 , dir[i] = -1;
		if (dp[i - 1] >= lasR[i]) {
			if  (max(R[i] , lasL[i]) > dp[i]) {
				dp[i] = max(R[i] , lasL[i]) , dir[i] = 1 , pre[i] = i - 1;
			}
		}
		int l = 0 , r = i - 1;
		while(l < r) {
			int mid = l + r >> 1;
			if (dp[mid] >= L[i]) r = mid;
			else l = mid + 1;
		}
		if (dp[l] >= L[i]) {
			if (max(GetMax(l + 1 , i - 1) , lasL[i]) > dp[i]) {
				dp[i] = max(GetMax(l + 1 , i - 1) , lasL[i]);
				pre[i] = l , dir[i] = -1;
			}
		}
	}
	return (dp[n] >= m);
}

评论

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

正在加载评论...