专栏文章

题解：P10784 【MX-J1-T4】『FLA - III』Wrestle

细细数繁星
P10784题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miniskxt
此快照首次捕获于
2025/12/02 03:06
3 个月前
此快照最后确认于
2025/12/02 03:06
3 个月前
查看原文
我竟然自己一个人把这道题切出来了（花了两天，只算零碎时间是 1 个小时）。算是考前给自己的信心。写完了还是有些感触的，故写篇题解祭。
先读题目。
因为是处理线段关系，所以不管三七二十一，先把蓝色线段按照 LiL_i 为关键字排序，红色线段按照 lil_i 为关键字排序。
每个点至多被一个红色线段和一个蓝色线段覆盖。说明蓝色线段之间不会有交集，红色线段亦然。故 ri<li+1r_i<l_{i+1} 且 Ri<Li+1R_i<L_{i+1}。
定义 sis_i 表示第 sis_i 个红色线段为最左的和第 ii 个蓝色线段有交集的线段，tit_i 表示第 tit_i 个红色线段为最右的和第 ii 个蓝色线段有交集的线段。因为 LiL_i 的单调性且同色线段互不相交，所以可以通过二分求解 sis_i 和 tit_i。
选取线段是有代价的，即为有交的红色线段的权值。也是有收益的，即为交集长度。定义 viv_i 为选取第 ii 个蓝色线段的收益，cic_i 为选取第 ii 个蓝色线段的代价。根据题目，ci=∑k=sitiwkc_i=\sum\limits_{k=s_i}^{t_i} w_k。
而第 ii 个蓝色线段选取的收益就比较复杂——要处理边际。如果有 lsi<Lil_{s_i}<L_i 和 rti>Rir_{t_i}>R_i，则需要特殊处理。中间的皆为连续的，加上 ∑k=si+1ti−1rk−lk+1\sum\limits_{k=s_i+1}^{t_i-1}r_k-l_k+1。
这两个求和，用前缀和优化。
再将 s,t,v,cs,t,v,c 按照 sis_i 排序。
而每个红色线段至多被一个蓝色线段覆盖。所以选取的蓝色线段的 [si,ti][s_i,t_i] 不可以相交。
问题转化成了：有一些线段，代价为 cic_i，收益为 viv_i，起始点为 sis_i，终止点为 tit_i。求选取一些线段的最大收益，使得总代价不超过 kk，且线段两两不相交（这里没有什么蓝色红色线段了）。
等等，这不就是 01 背包吗！
但因为不可以相交，所以方程为：
fi,j=max⁡tk<si{fk,j−ci+vi}f_{i,j}=\max_{t_k<s_i}\{f_{k,j-c_i}+v_i\}
而这样的时间复杂度是 O(m2k)\mathcal{O}(m^2k)，只能拿 50 分。考虑优化。
Fi,jF_{i,j} 表示 max⁡tk<si{fk,j−ci}\max_{t_k< s_i}\{f_{k,j-c_i}\}，这是可以预处理的。二分最小的 ii 使得 tk<sit_k<s_i，在处理到 kk 的时候即可预处理 Fi,jF_{i,j}。此时：
fi,j=max⁡{Fk,j}f_{i,j}=\max\{F_{k,j}\}
时间复杂度 O(mk)\mathcal{O}(mk)。
因此易得代码：
CPP
#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void solve() {
	
}

const int N = 2E5 + 5;
struct RedSegment {
	int l, r;
	ll w;
}reds[N];

struct BlueSegment {
	int l, r;
	ll v, w;
}blues[N];

ll reds_pref[N], reds_len[N], dp[5005][5005], cnt, dp_pre[5005][5005], blue_l[5005];
ll cover[N];

bool cmp(RedSegment a, RedSegment b) {
	return a.l < b.l;
}

bool check(int red, pair<int, int> blue) {
	return max(blue.first, reds[red].l) <= min(blue.second, reds[red].r);
}

bool cmp2(BlueSegment a, BlueSegment b) {
	return a.l < b.l;
}

main() {
//	int t; cin >> t; while (t--) solve();
	int n, m, k;
	cin >> n >> m >> k;
	rep(i, 1, n) 
		cin >> reds[i].l >> reds[i].r >> reds[i].w;
	sort(reds + 1, reds + n + 1, cmp);
	rep(i, 1, n) {
		reds_pref[i] = reds_pref[i - 1] + reds[i].w;
		// 权值的前缀和
		reds_len[i] = reds_len[i - 1] + reds[i].r - reds[i].l + 1;
		// 收益的前缀和
	}
	rep(i, 1, m) {
		int lef, rig;
		cin >> lef >> rig;
		int left_red = 1, r = n;
		int l = 1;
		while (l < r) {
			int mid = (l + r + 1) / 2;
			if (reds[mid].l > lef)
				r = mid - 1;
			else
				l = mid;
		}
		left_red = max(1, l);
		if (!check(left_red, {lef, rig})) {
			left_red++;
		}
		// 二分 si
		int right_red = 1; l = left_red, r = n;
		while (l < r) {
			int mid = (l + r) / 2;
			if (reds[mid].r < rig) 
				l = mid + 1;
			else
				r = mid;
		}
		right_red = min(n, r);
		if (!check(right_red, {lef, rig}))
			right_red--;
		// 二分 ti
		ll v = 0, w = 0;
		// 计算收益与代价
		if (right_red - left_red >= 0) {
			w = reds_pref[right_red] - reds_pref[left_red - 1];
			// 代价易得
			int tmpl = left_red, tmpr = right_red;
			if (reds[left_red].l < lef) {
				v = min(rig, reds[left_red].r) - max(reds[left_red].l, lef) + 1;
				tmpl++;
			}
			if (tmpr >= tmpl && reds[right_red].r > rig) {
				v += min(rig, reds[right_red].r) - max(lef, reds[right_red].l) + 1;
				tmpr--;
			}
			// 收益需要处理边际
			if (tmpr - tmpl >= 0)	
				v += reds_len[tmpr] - reds_len[tmpl - 1];
			blues[++cnt] = {left_red, right_red, v, w};
		}
	}
	sort(blues + 1, blues + cnt + 1, cmp2);
	rep(i, 1, cnt) {
		blue_l[i] = blues[i].l;
		// 因为我二分很烂 qwq，单开一个数组可以用 upper_bound（
	}
	ll ans = 0;
	rep(i, 1, cnt) {
		int ending = upper_bound(blue_l + 1, blue_l + cnt + 1, blues[i].r) - blue_l;
		rep(j, 0, k) {
			dp_pre[i][j] = max(dp_pre[i - 1][j], dp_pre[i][j]);
			if (j < blues[i].w) continue;
			dp[i][j] = dp_pre[i][j - blues[i].w] + blues[i].v;
			dp_pre[ending][j] = max(dp_pre[ending][j], dp[i][j]);
			ans = max(ans, dp[i][j]);
			// dp_pre 为 F 数组
			// 动规优化
		}
	}
	cout << ans;
	return 0;
}

评论

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

正在加载评论...