题意
平面上有$n$个点，每个点都有一个位置$x_i$，和向右的速度$v_i$
现在要求你对其中的一些点进行染色，当一个点被染色后，在无限距离内与它相遇的点也会被染色
问在可能的$2^n$种染色方案中，有多少种染色方案可以使得最后的点全部被染色
sol
非常好的dp题。
首先考虑若点$i$被染色后，哪些点会被染色
最显然的两种情况
1. $x_j < x_i$且$v_j > v_i$
2. $x_j > x_i$且$v_j < v_i$
当然还有其他的情况，因为题目中的“染色”是一个连锁反应，也就是说$a$被染色，$a$又遇到了$b$，那么$b$也会被染色
实际上，当我们把所有点按速度从大到小排序。
对于$x_i$，向左找到第一个$x_l < x_i$的最小的$l$(此时同时保证了$v_l$最大)
向右找到第一个$x_r > x_i$的最大的$r$(同理保证了$v_r$最小)
那么区间$[l, r]$内所有的点都会被染色
现在问题转化成了，每个点能覆盖一段区间$[l, r]$，问把区间$[l, n]$覆盖的方案数
预处理出每个点能覆盖的区间$[l, r]$。
这些区间有很多好的性质
满足$l_1 leqslant l_2 leqslant dots leqslant l_n, r_1 leqslant r_2 leqslant dots leqslant r_n$
证明显然，拿l来说，对于按速度排序以后的排列中两个位置$x_k, x_{k + 1}$
若$x_{k+1} < x_k$，此时$l_{k + 1} > l_k$
若$x_{k + 1} > x_k$，此时$l_{k + 1} = l_k$
右端点同理
注意一个细节，由于我们是按从大到小排序，这样处理起来不是很方便，直接把所有区间reverse一下
设$f[i]$表示用前$i$个区间覆盖$[1, n]$的方案
$s[i]$为其前缀和
前缀和优化dp即可
统计方案那里不是特别懂，路过的大佬可以说一下思路qwq
到了考场上还是写树状数组吧，无脑一点
#include<bits/stdc++.h> #define pair pair<int, int> #define fi first #define se second #define mp(x, y) make_pair(x, y) #define ll long long using namespace std; const int maxn = 1e6, mod = 1e9 + 7; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, date[maxn], l[maxn], r[maxn], f[maxn]; struct node { int x, v, id, l, r; bool operator < (const node &rhs) const { return v > rhs.v; } }a[maxn]; int comp(const node &a, const node &b) { return a.r == b.r ? a.l < b.l : a.r < b.r; } void getl(int *op) { vector<pair> q; for(int i = 1; i <= n; i++) q.push_back(mp(a[i].x, a[i].id)); sort(q.begin(), q.end()); for(int i = 1; i <= n; i++) { while(!q.empty()) { if(a[i].x <= q.back().fi) op[q.back().se] = i, q.pop_back(); else break; } } } void getr(int *op) { vector<pair> q; for(int i = 1; i <= n; i++) q.push_back(mp(a[i].x, a[i].id)); sort(q.begin(), q.end()); reverse(q.begin(), q.end()); for(int i = n; i >= 1; i--) { while(!q.empty()) { if(a[i].x >= q.back().fi) op[q.back().se] = i, q.pop_back(); else break; } } } int dp() { for(int i = 1; i <= n; i++) a[i].r = n - l[i] + 1, a[i].l = n - r[i] + 1; sort(a + 1, a + n + 1, comp); //for(int i = 1; i <= n; i++) printf("%d %dn", a[i].l, a[i].r); static int s[maxn], f[maxn];//f[i]：前i只猫覆盖所有区间的方案 int ans = 0; for(int i = 1, j = 1; i <= n; i++) { while(a[j].r < a[i].l - 1) j++; f[i] = (s[i - 1] + mod - s[j - 1] ) % mod; if(a[i].l == 1) f[i]++; if(a[i].r == n) (ans += f[i]) %= mod; s[i] = (s[i - 1] + f[i]) % mod; } return ans % mod; } main() { n = read(); for(int i = 1; i <= n; i++) a[i].x = read(), a[i].v = read(), a[i].id = i, date[i] = a[i].v; sort(date + 1, date + n + 1); int num = unique(date + 1, date + n + 1) - date - 1; for(int i = 1; i <= n; i++) a[i].v = lower_bound(date + 1, date + num + 1, a[i].v) - date; sort(a + 1, a + n + 1); getl(l); getr(r); //for(int i = 1; i <= n; i++) printf("%d %dn", l[i], r[i]); printf("%d", dp() % mod); }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/607593.html