首页 > 代码库 > 「6月雅礼集训 2017 Day8」infection
「6月雅礼集训 2017 Day8」infection
【题目大意】
有$n$个人,每个人有一个初始位置$x_i$和一个速度$v_i$,你需要选择若干个人来感染一个傻逼病毒。
当两个人相遇(可以是正面和背面),傻逼病毒会传染,求经过无限大时间后,传染完所有人的方案数。
【题解】
考虑经过无限大时间后结束的数列,一定是按$v_i$排序的。
对于第i个人,如果他带有病毒,那么
原来在它左边的速度最大的点一定会超过它,到达右边能到达的最大值,这个点会经过若干个点,这些都会被传染。
原来在它右边的速度最小的点一定会跑到它的后面,到达左边能到达的最小值,同理也会被传染。
所以每个人的传染是最后的一个区间,这个区间可以用线段树或者单调队列找出,然后就是经典的区间覆盖问题了。
有一种非常美妙的$O(n)$的dp可以解决这个问题。
反正xjb做就可以了,具体看代码
# include <vector> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int M = 2e5 + 10; const int inf = 1.05e9; const int mod = 1e9 + 7; int n; struct pa { int x, v, ps; pa() {} pa(int x, int v, int ps) : x(x), v(v), ps(ps) {} }p[M]; inline bool cmp_pos(pa a, pa b) { return a.x < b.x; } inline bool cmp_va(pa a, pa b) { return a.v < b.v; } struct segnode { int w, id; segnode() {} segnode(int w, int id) : w(w), id(id) {} friend bool operator < (segnode a, segnode b) { return a.w < b.w; } friend bool operator > (segnode a, segnode b) { return a.w > b.w; } }; struct SMT { # define ls (x<<1) # define rs (x<<1|1) segnode mx[M << 2], mi[M << 2]; inline void set() { for (int i=1; i<=(n<<2); ++i) mx[i] = segnode(-inf, -1); for (int i=1; i<=(n<<1); ++i) mi[i] = segnode(inf, -1); } inline void edt(int x, int l, int r, int ps, int d, int dd) { if(l == r) { mx[x] = mi[x] = segnode(d, dd); return ; } int mid = l+r >> 1; if(ps <= mid) edt(ls, l, mid, ps, d, dd); else edt(rs, mid+1, r, ps, d, dd); mi[x] = min(mi[ls], mi[rs]); mx[x] = max(mx[ls], mx[rs]); } inline segnode gmin(int x, int l, int r, int L, int R) { if(L > R) return segnode(inf, -1); if(L <= l && r <= R) return mi[x]; int mid = l+r>>1; segnode ret = segnode(inf, -1); if(L <= mid) ret = min(ret, gmin(ls, l, mid, L, R)); if(R > mid) ret = min(ret, gmin(rs, mid+1, r, L, R)); return ret; } inline segnode gmax(int x, int l, int r, int L, int R) { if(L > R) return segnode(-inf, -1); if(L <= l && r <= R) return mx[x]; int mid = l+r>>1; segnode ret = segnode(-inf, -1); if(L <= mid) ret = max(ret, gmax(ls, l, mid, L, R)); if(R > mid) ret = max(ret, gmax(rs, mid+1, r, L, R)); return ret; } }T; int pos[M]; int f[M], s[M]; struct intervals { int l, r; intervals() {} intervals(int l, int r) : l(l), r(r) {} friend bool operator < (intervals a, intervals b) { return a.r < b.r || (a.r == b.r && a.l < b.l); } }a[M]; int main() { // freopen("infection.in", "r", stdin); // freopen("infection.out", "w", stdout); cin >> n; for (int i=1; i<=n; ++i) scanf("%d%d", &p[i].x, &p[i].v); sort(p+1, p+n+1, cmp_pos); for (int i=1; i<=n; ++i) p[i].ps = i; sort(p+1, p+n+1, cmp_va); for (int i=1; i<=n; ++i) T.edt(1, 1, n, p[i].ps, p[i].v, i); // for (int i=1; i<=n; ++i) printf("pos = %d, value = http://www.mamicode.com/%d, x = %d, id = %d/n", p[i].ps, p[i].v, p[i].x, i); for (int i=1; i<=n; ++i) { a[i].r = T.gmax(1, 1, n, 1, p[i].ps-1).id; if(a[i].r == -1) a[i].r = i; a[i].l = T.gmin(1, 1, n, p[i].ps+1, n).id; if(a[i].l == -1) a[i].l = i; a[i].l = min(a[i].l, i); a[i].r = max(a[i].r, i); // printf("%d %d\n", a[i].l, a[i].r); } sort(a+1, a+n+1); f[0] = s[0] = 1; for (int i=1, j=1; i<=n; ++i) { s[i] = s[i-1]; for (; j<=n && a[j].r == i; ++j) { // printf("%d %d %d\n", i, a[j].r, s[a[j].r]); int tem = s[a[j].r] - ((a[j].l == 1) ? 0 : s[a[j].l-2]); if(tem < 0) tem += mod; f[i] += tem; if(f[i] >= mod) f[i] -= mod; s[i] = s[i-1] + f[i]; if(s[i] >= mod) s[i] -= mod; } } cout << f[n] << endl; return 0; }
「6月雅礼集训 2017 Day8」infection
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。