新年欢乐赛题解

Loser. / 2024-02-09 / 原文

cyh 巨佬举办的比赛。

比赛页面

赛后补题

官方题解

赛时没时间写题，赛后补一下。

T1:

默认排名第一，对于每次输入，若输入的成绩更优，则将排名降低。这里更劣的成绩没用，因为默认初始排名第一。

T2:

At 上的一道原题。考虑 DP 求解。$dp_{i, 0/1}$ 分别表示到第 $i$ 张翻和不翻的总情况数。每次判断翻或不翻和上一张是否相同，若是就转移。别忘记每次取模。

T3:

给出一个一眼的拆式子的方法。

\[\sum_{i = l}^{r} a_i \times (i - l + 1) = \sum_{i = l}^{r} a_i \times (i + 1) - \sum_{i = l}^{r} a_i \times l \]

令 $suma_i = \sum_{j = 1}^{i} a_j$，$sumb_i = \sum_{j = 1}^{i} a_j \times (j + 1)$。相当于求了两个前缀和。每次输出区间的两个值相减即可。

T4:

cyh 提供的分块算法好强大，我根本看不懂（）。

我们发现随着操作次数增加，满足条件的可能性也增加，单调递增。所以考虑二分操作次数 $mid$。

考虑如何 $check$。用暴力枚举每个位置会 T 飞。我们不妨试着转换一下。给出 $mid$ 次操作的区间，求序列里是否有任何一个值 $\ge v$，就相当于给出 $mid$ 条线段，每条线段有值为 $w_i$，问最大的重叠部分的总值是否 $\ge v$。

再考虑如何实现。我们可以把 $mid$ 条线段打散成 $mid \times 2$ 个点，标记每个点的位置 $p$，所在线段的值 $w$，头尾 $0/1$。然后以 $p$ 为关键字由小到大排序。然后依次枚举排序后 $mid \times 2$ 个点，若为开头，就加上当前线段的值（相当于加入了当前线段），若为结尾，就减去当前线段的值。对于 $mid \times 2$ 次的枚举，每次判断当前的值是否 $\ge v$ 即可。

时间复杂度约为 $O(k \log k \log k)$，$check$ 的复杂度在于排序。喜提最优解。

#include <bits/stdc++.h>
typedef long long ll;
#define int long long

const int N = 1e4 + 100;
int n, v, l[N], r[N], w[N];

struct node {
	int p, w; bool flag;
	bool operator < (const node &b) const {
		return p < b.p;
	}
}; std::vector <node> vec;

bool check(int mid) {
	vec.clear();
	for (int i = 1; i <= mid; ++ i) {
		vec.push_back((node) {l[i], w[i], 0});
		vec.push_back((node) {r[i] + 1, w[i], 1});
	}
	std::sort(vec.begin(), vec.end());
	int tmp = 0; 
	for (int i = 0; i < vec.size(); ++ i) {
		if (vec[i].flag == 0) tmp += vec[i].w;
		else tmp -= vec[i].w;
		if (tmp >= v) return 1;
	}
	return 0;
}

signed main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	std::cin >> n >> v;
	for (int i = 1; i <= n; ++ i) std::cin >> l[i] >> r[i] >> w[i];
	int l = 1, r = n, ans = -1;
	while (l <= r) {
		int mid = l + r >> 1;
		if (check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	} std::cout << ans;

	return 0;
}