题解：P17140 [NOI 2026] 线段

· · 题解

题外话：本人场上写了时空均为 O(n^2k) 的做法，可以一秒转成 O(nmk) 的，但以为这是纯暴力又不是正解反正也没多少分，没必要卡空间，又想不出来更好的方法直接扔了，结果出场后你告诉我再开个滚动数组就过了？？于是 100 分变成 52 分，铜牌变成铁牌。不是，为啥 6\times 10^8 能过啊？

首先容易发现不可能有一个点被不少于 3 条线段包含，因为这样就会出现环了。

可以把所选的线段里右端点最靠右的看成这个树的根，那么它的儿子之间不能相交，并且它的儿子里只有最靠左的儿子不是叶子，并且不能和孙子有交点，否则都会出现环。想象一下，差不多会变成下面这个结构：

发现所有右端点都是递增的。于是可以先把所有线段按右端点大小升序排序。然后右端点必须与父亲相交。

考虑 DP 。记 f_{i,j,p} 在前 i 条线段里选择，要求选的线段的右端点大于等于 j （j 是当前父亲的左端点），还剩 p 条要选择的方案数。第 i 条线段要么选要么不选。设 d(x) 是满足 r_{d(x)}<x 的最大的数。 如果第 i 条线段只能成为叶子，即 l_i\geq j，那么 f_{i,j,p}=f_{i-1,j,p}+f_{d(l_i),j,p-1}。否则线段 i 能够有儿子，即 l_i<j，那么 f_{i,j,p}=f_{i-1,j,p}+f_{d(j),l_i,p-1}。这里用的 d 是为了保证下一条线段的右端点不会与上一条重合。

然后随便处理一下边界，开个滚动数组就做完了。

#include <bits/stdc++.h>
#include "segment.h"

using namespace std;

const int N = 3010, fff=998244353;

void init(int c, int t) {
    return;
}

struct node {
    int l, r;
}b[N];

bool cmp(node x, node y) {
    return x.r<y.r;
}

int dp[3010][1010][2], ds[N];

vector<int> segment(int n, int m, int k, vector<int> l, vector<int> r) {
    vector<int> a;
    for(int i=0;i<=k;i++)a.push_back(0);
    for(int i=0;i<n;i++) {
        b[i+1]={l[i], r[i]};
    }
    sort(b+1,b+n+1,cmp);
    int pos=0;
    for(int i=1;i<=m;i++) {
        //找r < i的
        while(pos<n&&b[pos+1].r<i)++pos;
        ds[i]=pos;
    }
    for(int p=0;p<=k;p++) {
        for(int i=0;i<=n;i++) {
            for(int j=0;j<=m;j++) {
                if(i==0) {
                    if(p==0)dp[i][j][p&1]=1;
                    else dp[i][j][p&1]=0;
                    continue;
                }
                dp[i][j][p&1]=dp[i-1][j][p&1];
                if(p==0)continue;
                //决定i要不要选
                if(j==0) {
                    dp[i][j][p&1]+=dp[i-1][b[i].l][(p&1)^1], dp[i][j][p&1]%=fff;
                    continue;
                }

                if(b[i].r<j)continue;
                if(b[i].l>j) {
                    int d=ds[b[i].l];
                    dp[i][j][p&1]+=dp[d][j][(p&1)^1], dp[i][j][p&1]%=fff;
                }else {
                    int d=ds[j];
                    dp[i][j][p&1]+=dp[d][b[i].l][(p&1)^1], dp[i][j][p&1]%=fff;
                }

            }
        }
        if(p>=1&&p<=k)a[p]=dp[n][0][p&1];
    }
    return a;
}