胜利一中 2023 秋提高级友好学校赛前联测 2

AisDaeun 9 2023-10-29

谁共一杯芳酒

T390216 谁共一杯芳酒
题意:
给定n个以[l, r]表示的闭区间,设这些区间构成集合U;
从U中取出任意个元素,按照任意顺序构成序列A;
A是合法序列,当且仅当\forall a_i, a_j \in A 且 i < j, a_i \subseteq a_j
求U构成的最长合法序列长度。

一般地,对于区间作元素的题目,可以对其中一个端点排序,然后处理另一个端点。

本题也是如此。考虑把所有区间按左端点从大到小排序,那么只要区间x的右端点小于x的后继y的右端点,自然有x \subseteq y

设R是所有区间的右端点构成的序列,那么,要求U构成的最长合法序列长度,只需求R的最长非严格上升子序列的长度。

注意到本题的数据范围n \leq 5 \times 10^5,所以要使用O(n \log n)的解法。

代码:


#include <bits/stdc++.h>

#define _for(i, a, b) for (int i = (a); i <= (b); ++i)

#define __for(i, a, b) for (int i = (a); i >= (b); --i)

int read() {

	int x = 0; bool fl(0); char ch = getchar();

	for (; !isdigit(ch); ch = getchar()) fl = ch == '-';

	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';

	return fl ? -x : x;

}

const int N = 5e5 + 10;

struct o {int l, r; } a[N];

int f[N], len;

signed main() {

	std::ios::sync_with_stdio(false);

	int n = read();

	_for(i, 1, n) a[i] = {read(), read()};

	std::sort(a + 1, a + n + 1, [] (o &a, o &b) {

		if (a.l == b.l) return a.r < b.r;

		return a.l > b.l;

	});

	_for(i, 1, n) {

		int &r = a[i].r;

		if (r >= f[len]) f[++len] = r;

		else {

			int pos = std::upper_bound(f + 1, f + len + 1, r) - f;

			f[pos] = r;

		}

	}

	std::cout << len << '\n';

	return 0;

}

约会

T390217 约会
题意:
给定一颗有向带权树
可以花费1的代价翻转一条边的方向
任选一个节点R
求使所有除R以外的点到R的距离小于D的最小代价

乱杀

T390218 乱杀
题意:
给定两个点,t=0时都位于数轴原点
两个点的速度上限为V
给定若干个要求(t, x)
求使对于任意t,至少有一个点在x位置的最小速度上限V

红藕香残

T390219 红藕香残
题意:
给定一个数组a,有q次询问
对于每次询问,从[l, r]中任选k个数,得分是这些数的最大公因数,求最大得分

小结

贴一篇do_while_true大佬的题解:Solution"