夏晓光(loveJY)的博客

UOJ推荐题

OrzEI

题目大意

数轴上有$N$个点，每个点初始时在位置$X_i$，以$V_i$的速度向数轴正方向前进

初始时刻，你可以选择一些点为其染色，之后的行走过程中，染色的点会将其碰到的所有点都染上色，之后被染上色的点亦是如此

在所有$2^N$种初始染色方案中，问有多少种初始染色方案，能使得最终所有的点都被染色？答案对$10^9+7$取模

首先不难发现到世界末日的时候所有点一定是按照v排布的,而且不会再相交

那么我们把按照v排序的相对顺序和一开始x的相对顺序对于一个点拉成一条线段

问题就变成了选择一些的线段让他们覆盖整个数轴的总方案数

这个东西显然可以dp,先按照右端点排一下序啊,我们每个线段右端点就递增了

$f[i]$表示前i条线段第i条线段强制选,覆盖了$[1,r[i]]$这个范围的总方案数

转移的时候枚举之前的一个l,$l \in [l[i],r[i]]$,,然后就可以

$f[i]=\sum_{j=pre}^{i}[r[j]<=r[i]]{f[j]}$

因为重复不重复这个不重要我们只需要满足全覆盖就好了

code:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
typedef pair<int, int> par;

struct {
	inline operator int() {
		int x;
		return scanf("%lld", &x), x;
	}
	inline operator ll() {
		ll x;
		return scanf("%lld", &x), x;
	}
	template<class T> inline void operator ()(T &x) {
		x = *this;
	}
	template<class T, class ...A >inline void operator () (T &x, A &...a) {
		x = *this;
		this->operator ()(a...);
	}
} read;

const int MAXN = 2e5 + 5, P = 1e9 + 7;
int l[MAXN], r[MAXN];
int p[MAXN];
int tmp[MAXN];
par pr[MAXN];
ll f[MAXN], s[MAXN];

int main() {
	int n = read;
	for(int i = 1; i <= n; ++i) {
		read(pr[i].second, pr[i].first);
		//注意先按照v排序
	}
	std::sort(pr + 1, pr + n + 1);
	for(int i = 1; i <= n; ++i) {
		tmp[i] = pr[i].second;
		//离散化部分
	}
	std::sort(tmp + 1, tmp + n + 1);
	//x数组
	for(int i = 1; i <= n; ++i) {
		pr[i].second = int(std::lower_bound(tmp + 1, tmp + n + 1, pr[i].second) - tmp);
		//离散化
		p[pr[i].second] = i;
		//p数组记录了新位置
	}
	for(int i = 1; i <= n; ++i) {
		r[i] = std::max(r[i - 1], p[i]);
		//这里是求出每段实际区间的右端点是哪个值
	}
	l[n] = p[n];
	for(int i = n - 1; i; --i) {
		l[i] = std::min(l[i + 1], p[i]);
		//同理左端点
	}
	int L = 0;
	f[0] = s[0] = 1;
	for(int i = 1; i <= n; ++i) {
		while(r[L] < l[i] - 1) {
			++L;
			//这句话其实限制了转移方程里面的[]
			//满足区间和是其中任何一个元素都合法
		}
		f[i] = (s[i - 1] - s[L - 1] + P) % P;
		s[i] = (s[i - 1] + f[i]) % P;
	}
	while(r[L] < n) {
		++L;
	}
	printf("%lld\n", (s[n] - s[L - 1] + P) % P);
	return 0;
}