CF-Avito Code Challenge 2018-E-Addition on Segments

ACM模版

描述

题解

给定 n n 个值为 0 $0$ 的数，下标从 1∼n 1 ∼ n ，然后给了 q q 次区域加操作，选取这 q $q$ 次操作的任意操作子集，可以得到一个最大的值，取所有操作后最大值在 1∼n 1 ∼ n 的操作子集，他们的最大值组成了结果，这个结果是所有可能构成的在 1∼n 1 ∼ n 之间最大值的数目。

样例 1 1 ，只选取第一次操作可以获得最大值为 1 $1$，只取第二次操作可以获得最大值 2 2 ，只取第三次操作可以获得最大值 4 $4$，取前两次操作可以获得最大值 3 3 ，所以在 1∼n $1\sim n$ 之间，有 1,2,3,4 1 , 2 , 3 , 4 这 4 4 种可以通过某种操作子集操作后构成。

这里我们可以用 dp $dp$，设置 dp[i] d p [ i ] 表示构成最大值 i i 时它所在的最靠右的位置，也就是右区间截止的位置。当我们输入 l,r,x $l,r,x$ 时，我们可以枚举 j=n−x∼0 j = n − x ∼ 0 的情况，这样可以保证构成的最大值在 1∼n 1 ∼ n 之间。对于 j!=0 j ! = 0 的情况，考虑 dp[j]>=l d p [ j ] >= l ，如果为真说明现在这个操作和之前的操作存在交集，所以可以叠加在一起，构成 j+x j + x ，反之则不能，对于 j=0 j = 0 的情况，直接赋值 dp[x]=r d p [ x ] = r 即可。

这里有一点需要强调的，那就是必须将区间加操作排序，按照操作右区间从小到大排序即可。

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e4 + 5;

struct Q
{
    int l, r, x;
    bool operator < (const Q &rhs) const
    {
        return r < rhs.r;
    }
} qs[MAXN];

int n, q;
int dp[MAXN];

int main()
{
    scanf("%d%d", &n, &q);

    for (int i = 0; i < q; i++)
    {
        scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].x);
    }
    sort(qs, qs + q);

    for (int i = 0; i < q; i++)
    {
        int l = qs[i].l, r = qs[i].r, x = qs[i].x;
        for (int j = n - x; j >= 1; j--)
        {
            if (dp[j] >= l)
            {
                dp[j + x] = max(dp[j + x], dp[j]);
            }
        }
        dp[x] = r;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt += (dp[i] > 0);
    }

    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++)
    {
        if (dp[i] > 0)
        {
            printf("%d ", i);
        }
    }
    puts("");

    return 0;
}