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 + 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 %d\n", 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 %d\n", L[i], R[i]);
    printf("%d", dp() % mod);
 
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java思维导图

JAVA容器-自问自答学ArrayList

前言 这次我和大家一起学习HashMap,HashMap我们在工作中经常会使用,而且面试中也很频繁会问到,因为它里面蕴含着很多知识点,可以很好的考察个人基础。但...

3709
来自专栏开发技术

排序之冒泡排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

954
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》 附录A NumPy高级应用A.1 ndarray对象的内部机理A.2 高级数组操作A.3 广播A.4 ufunc高级应用A.5 结构化和记录式数组A.6 更多

在这篇附录中,我会深入NumPy库的数组计算。这会包括ndarray更内部的细节,和更高级的数组操作和算法。 这章包括了一些杂乱的章节,不需要仔细研究。 A.1...

7086
来自专栏python成长之路

集合常用操作

1734
来自专栏Java技术栈

递归算法介绍及Java应用实战

什么是递归算法 递归算法是把问题转化为规模缩小了的同类问题的子问题,然后递归调用函数(或过程)来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程...

40310
来自专栏伪君子的梦呓

题解 ~ 输出三个数中的最大值 ~ C++ 做法

2255
来自专栏灯塔大数据

每周学点大数据 | No.32优先队列

No.32期 优先队列 Mr. 王:我们回到这个问题中,如果是在内存中,我们只需要对前面的这些点做一个拓扑排序,就可以保证每一个节点在求解时,它们的所有入度...

30310
来自专栏九彩拼盘的叨叨叨

学习纲要:JavaScript 基础语法

1183
来自专栏五分钟学算法

每天一算:Minimum Size Subarray Sum

leetcode上第209号问题:Minimum Size Subarray Sum

691
来自专栏用户画像

C语言测试题

2. 假设已指定i为整型变量,f为float变量,d为double型变量,e为long型,有下面式子:

1925

扫码关注云+社区

领取腾讯云代金券