题解：P12761 [POI 2018 R2] 列车员 Conductor

SMHBD_ · 2025-10-20 17:39:40 · 题解

一道双指针优化 DP 题。

题意

给定一个长为 m 的数轴，每一次可以标记一单位长度，求题目给定的每一个区间都至少有一单位长度是被标记的最小标记数以及在标记数最小情况下的所有标记方案数。

状态

先离散化。定义 d_{i,0/1} 和 s_{i,0/1} 表示是否标记 i-1 至 i，让所有右端点小于等于 i 的区间都满足要求的最小标记数和在标记数最小情况下的方案数。

转移

显然，d_{i,1} 和 s_{i,1} 都由 i-1 转移而来，因为如果标记了 i-1 至 i，则新加进来的区间（右端点为 i）就全被满足了，而其他区间都没被满足，转化成 i-1。注意转移时要乘上 i 和 i-1 对应的原位置的差值，因为离散化把很多单位区间合并了，而这些单位区间是互相等价的。

我们定义 l 表示在所有考虑的区间中，最靠右的左端点坐标加 1。那么 d_{i,0} 和 s_{i,0} 就由 j=l\sim (i-1) 的所有 d_{j,1} 最小的 j 转移过来。如果 j 再小就会有区间不满足了。

这里就用双指针优化。我们发现，由于考虑的区间只会增加，d_{i,1} 一定是单调不降的。所以我们只要知道最右边的 r，使得 d_{r,1}=d_{l,1} ，最后 d_{i,0} 从区间 l\sim r 转移过来就行了。方案数用前缀和处理即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
long long T,n,m,p=1e9+7,l,r,k[maxn],cnt,xx[maxn],yy[maxn],d[maxn][2],s[maxn][2],ss[maxn];
struct xxx
{
    int x,y,z;
    bool operator < (const xxx o) const{return x<o.x;}
    bool operator > (const xxx o) const{return x>o.x;}
};
vector<xxx> b;
vector<int> f[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>m>>n;
        for(int i=1;i<=2*n;i++)f[i].clear();
        b.clear();
        b.push_back((xxx){0,0,0});
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>xx[i]>>yy[i];
            b.push_back((xxx){xx[i],i,0});
            b.push_back((xxx){yy[i],i,1});
        }
        sort(b.begin(),b.end());
        for(int i=1;i<b.size();i++)
        {
            if(b[i].x!=b[i-1].x)
            {
                cnt++;
                k[cnt]=b[i].x;
            }
            if(b[i].z==0)xx[b[i].y]=cnt;
            else yy[b[i].y]=cnt;
        }
        for(int i=1;i<=cnt;i++)f[i].clear();
        for(int i=1;i<=n;i++)
        f[yy[i]].push_back(xx[i]);
        //这里这样初始化是因为在i=1时是没有区间要考虑的
        //但是一些d[i][0]又可以从这里转移
        //所以这里初始化d[i][1]和s[i][1]
        //这样不会有问题
        ss[1]=1;//前缀和
        s[1][1]=1;
        l=1,r=1;
        for(int i=2;i<=cnt;i++)
        {
            if(d[i-1][0]<d[i-1][1])
            {
                d[i][1]=d[i-1][0]+1;
                s[i][1]=s[i-1][0]*(k[i]-k[i-1])%p;
            }
            else if(d[i-1][0]>d[i-1][1])
            {
                d[i][1]=d[i-1][1]+1;
                s[i][1]=s[i-1][1]*(k[i]-k[i-1])%p;
            }
            else
            {
                d[i][1]=d[i-1][0]+1;
                s[i][1]=(s[i-1][0]+s[i-1][1])%p*(k[i]-k[i-1])%p;
            }
            //双指针
            for(long long j:f[i])l=max(l,j+1);
            while((r<l||d[r+1][1]==d[l][1])&&r<i-1)r++;
            ss[i]=(ss[i-1]+s[i][1])%p;
            if(r<l)//无法转移，说明方案不存在
            {
                d[i][0]=1e9;
                continue;
            }
            d[i][0]=d[l][1];
            s[i][0]=(ss[r]-ss[l-1]+p)%p;
        }
        if(d[cnt][1]<d[cnt][0])
        cout<<d[cnt][1]<<" "<<s[cnt][1]<<"\n";
        else if(d[cnt][1]>d[cnt][0])
        cout<<d[cnt][0]<<" "<<s[cnt][0]<<"\n";
        else
        cout<<d[cnt][1]<<" "<<(s[cnt][0]+s[cnt][1])%p<<"\n";
    }
}