agc015E - Mr.Aoki Incubator(dp)

题意

题目链接

平面上有$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 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', 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 = ; i <= N; i++) q.push_back(MP(a[i].x, a[i].id));

    sort(q.begin(), q.end());

    for(int i = ; 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 = ; 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 >= ; 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 = ; i <= N; i++) a[i].r = N - L[i] + , a[i].l = N - R[i] + ;

    sort(a + , a + N + , comp);

    //for(int i = 1; i <= N; i++) printf("%d %d\n", a[i].l, a[i].r);

    static int s[MAXN], f[MAXN];//f[i]：前i只猫覆盖所有区间的方案

    int ans = ;

    for(int i = , j = ; i <= N; i++) {

        while(a[j].r < a[i].l - ) j++;

        f[i] = (s[i - ] + mod - s[j - ] ) % mod;

        if(a[i].l == ) f[i]++;

        if(a[i].r == N) (ans += f[i]) %= mod;

        s[i] = (s[i - ] + f[i]) % mod;

    }

    return ans % mod;

}

main() {

    N = read();

    for(int i = ; i <= N; i++) a[i].x = read(), a[i].v = read(), a[i].id = i, date[i] = a[i].v;

    sort(date + , date + N + );

    int num = unique(date + , date + N + ) - date - ;

    for(int i = ; i <= N; i++) a[i].v = lower_bound(date + , date + num + , a[i].v) - date;

    sort(a + , a + N + );

    GetL(L); GetR(R);

    //for(int i = 1; i <= N; i++) printf("%d %d\n", L[i], R[i]);

    printf("%d", dp() % mod);

}

巴特西

agc015E - Mr.Aoki Incubator(dp)

题意

Sol

最新文章

热门文章