2024-12-16

今天上午是省选模拟赛，总体来说打的还行，但是还是太菜了，感觉被所有人吊打。

• T1
  题意：
  赛时思路：赛时想了差不多一个小时的贪心，后面发现不会贪，当时以为dp是正解，就推了个dp，可以用\(f_{i,j}\)表示第1个背包选了几个，第2个背包选了几个，然后发现转移方程就是\(f_{i, j} = max(f_{i-1,j}+a_{now,1},f_{i,j-1}+a_{now,2},f_{i,j}+a_{now,3})\)，能拿50pts，然后想了很久感觉应该有个优化就能过了，但是死活不会，赛后看题解发现还真有这么写的，是用的wqs二分优化过的，但是我太菜了不会。正解是无敌贪心。
  正解：首先把所有都放到第一个背包里，然后考虑把v2个放到第二个背包，v3个放到第三个背包。先设\(e_i\)表示\(b_i - a_i\)，\(f_i\)表示\(c_i-a_i\)，那放到第二个背包的收益就是\(e_i\)，第三个就是\(f_i\)，然后我们设第i个放到第二个背包，第j个放到第三个背包，考虑什么时候把它俩交换会更优，显然是\(e_i+f_j<e_j+f_i\)，移相得到\(e_i-e_j<f_i-f_j\)，所以我们就以这个排序，那么放到第二个背包的一定会全在放到第三个背包的前面，考虑怎么获得答案，发现可以用小根堆来处理出来前缀的前v2大的和，后缀前v3大的和，然后就直接枚举断点，找最大答案就行了。
  代码：

#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int v1, v2, v3, n;
ll mx, ans = -1e9;
ll sum[N], pre[N];
struct zx { int a, b, c, e, f; } a[N];
priority_queue <int, vector<int>, greater<int>> q1, q2;

bool cmp (zx a, zx b) {
	return a.e - a.f > b.e - b.f;
}

int main () {
	cin >> v1 >> v2 >> v3;
	n = v1 + v2 + v3;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i].a >> a[i].b >> a[i].c;
		a[i].e = a[i].b - a[i].a, a[i].f = a[i].c - a[i].a;
		mx += a[i].a;
	}
	sort(a + 1, a + n + 1, cmp);
	for(int i = 1; i <= n; ++i) {
		q1.push(a[i].e);
		sum[i] = sum[i - 1] + a[i].e;
		if(i > v2) {
			sum[i] = sum[i - 1] + a[i].e - q1.top();
			q1.pop();
		}
	}
	for(int i = n; i >= 1; --i) {
		q2.push(a[i].f);
		pre[i] = pre[i + 1] + a[i].f;
		if(i <= n - v3) {
			pre[i] = pre[i + 1] + a[i].f - q2.top();
			q2.pop();
		}
	}
	for(int i = v2; i <= n - v3; ++i) 
		ans = max(ans, mx + sum[i] + pre[i + 1]);
	cout << ans << endl;
	return 0;
}

• T2
  题面：