「AT1730」「CODE FESTIVAL 2015 OKINAWA OPEN」Happy 2015

AutumnKite

题解AtCoderCODE FESTIVAL 2015 OKINAWA OPEN

发布于：2019年3月3日

题意

给定 \(n\) 个区间 \((l_r,r_i]\)（注意原题中虽然写着 \([l_i,r_i]\)，但通过转化后相当于 \((l_i,r_i]\)），每个区间有存在和不存在两种状态。求所有 \(2^n\) 种方案中，本质不同的方案的数量 \(\bmod (10^9+7)\) 的值。

记一个方案的点集合为数轴上至少被一个区间覆盖的整数组成的集合，则两个方案本质不同当且仅当这两个方案的点集合不同。

\(n\le 2000,0\le l_i< r_i\le 10^9\)

题解

为方便处理，我们把 \(l_i\) 加 \(1\) 使得区间变为闭区间。

显然，\(l_i,r_i\) 可以离散，所以坐标变为 \(O(n)\) 级别。

然后考虑一个 DP，\(dp_{i,0/1}\) 表示覆盖前 \(i\) 个点，且第 \(i\) 个点必须覆盖/不覆盖的本质不同的方案数。

那么可以写出一个 \(O(n^2)\) 的 DP，方程如下：\[dp_{i,j}=\begin{cases} dp_{i-1,0}+dp_{i-1,1} & \text{ if } j=0 \\ \sum\limits_{cov(k,i)=1} dp_{k-1,0} & \text{ if } j=1 \end{cases}\]

其中 \(cov(k,i)=0/1\) 表示是否存在一种区间覆盖方案使得刚好覆盖 \([k,i]\)。

\(cov(i,j)\) 可以用如下方式处理：

记 \(p_i\)（一个 vector）表示所有右端点为 \(i\) 的区间的左端点。

枚举 \(i\)（被覆盖部分的左端点），首先枚举所有左端点为 \(i\) 的区间 \([i,r_j]\)，使得 \(cov(i,r_j)=1\)。

然后枚举所有右端点 \(j\)，再枚举所有右端点为 \(j\) 的区间（即 \([p_{j,k},j]\) ），若 \(p_{j,k}> i\) 且存在一个 \(x\in [p_{j,k},j]\) 满足 \(cov(i,x)=1\)，则 \(cov(i,j)=1\)。

至于如何判断“存在一个 \(x\in [p_{j,k},j]\) 满足 \(cov(i,x)=1\)”，可以在枚举右端点求 \(cov(i,j)\) 的同时用前缀和进行判断，具体实现见代码。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define P 1000000007
int n, m, pos[4005], sum[4005], dp0[4005], dp1[4005];
bool cov[4005][4005];
std :: vector<int> p[4005];
struct node{
    int l, r;
}a[2005];
void add(int &x, int y){
    (x += y) >= P ? x -= P : 0;
}
int main(){
    scanf("%d", &n);
    for (register int i = 1; i <= n; ++i)
        scanf("%d%d", &a[i].l, &a[i].r), pos[++m] = a[i].l, pos[++m] = a[i].r;
    std :: sort(pos + 1, pos + 1 + m);
    m = std :: unique(pos + 1, pos + 1 + m) - pos - 1;
    for (register int i = 1; i <= n; ++i){
        a[i].l = std :: lower_bound(pos + 1, pos + 1 + m, a[i].l) - pos + 1;
        a[i].r = std :: lower_bound(pos + 1, pos + 1 + m, a[i].r) - pos;
        p[a[i].r].push_back(a[i].l);
    }
    // 以上分别为：转为闭区间、离散、处理 p
    for (register int i = 1; i <= m; ++i){
        sum[i] = 0;
        for (register int j = 1; j <= n; ++j)
            if (a[j].l == i) cov[i][a[j].r] = 1;
        for (register int j = i; j <= m; ++j){
            for (register int k = 0; k < p[j].size(); ++k)
                if (p[j][k] > i && sum[j] > sum[p[j][k] - 1]){ cov[i][j] = 1; break; } // 根据前缀和判断
            sum[j + 1] = sum[j] + cov[i][j]; // 同时处理前缀和
        }
    }
    // 以上为处理 cov
    dp0[0] = 1;
    for (register int i = 1; i <= m; ++i){
        add(dp0[i], dp0[i - 1]), add(dp0[i], dp1[i - 1]);
        for (register int j = 1; j <= i; ++j)
            if (cov[j][i]) add(dp1[i], dp0[j - 1]);
    }
    // 以上为 dp
    add(dp0[m], dp1[m]), printf("%d\n", dp0[m]);
}

更新于：2020年3月26日

离散

「AT1731」「CODE FESTIVAL 2015 OKINAWA OPEN」Implementation Addict

题目传送门题意有 \(n\) 天，每天有一个值 \(a_i\)（未确定的值），其中 \(a_i=0\) 的天数称为“休息”，其他的称为“工作”。若第 \(i\) 天为“工作”，设第 ...

「AT1729」「CODE FESTIVAL 2015 OKINAWA OPEN」Gorgeous Vases

题目传送门题意有两个有序二元组 \((A,B),(C,D)\)，\(A,B\) 给定且保证 \(A\ge B\)，\(C,D\) 一开始为 \(0\)。另外给定 \(n\) 个有序二元组...