[SCOI2015]国旗计划

柔光的暖阳◎ 2023-10-11 05:24 7阅读 0赞

[题目][Link 1]

首先考虑一下环形的区间覆盖问题怎么做

我们可以把环倍长成链，之后惊讶的发现我只会枚举一个\\(i\\)作为起点跑\\(\[i,i+m\]\\)的区间覆盖

看起来非常垃圾，但是会这样做就够了

考虑枚举到的这个\\(i\\)作为一个某一个给定的区间的左端点的时候，想要覆盖\\(\[i,i+m\]\\)这段区间这个给定的区间是必须选择的，于是我们**对于每一个给定的区间\\(\[l\_i,r\_i\]\\)，来算一下覆盖\\(\[l\_i,l\_i+m\]\\)的最少要用多少个区间即可**

这是一个非常经典的贪心，我们把区间按照左端点排序，贪心地选择左端点不超过当前区间右端点中右端点最大的即可

题目中保证了任意两个区间不相互包含，也就是说我们按照左端排序之后右端点也是单调的，我们只需要利用单调性就可以求出每个区间的最优转移了

对于一个区间\\(\[l\_i,r\_i\]\\)，我们顺着最优转移走，直到当前区间的右端点不小于\\(l\_i+m\\)，那么\\(\[l\_i,l\_i+m\]\\)就被完全覆盖了，答案就是中间经过的区间个数

考虑让每个区间向其最优转移连边，这样我们就得到了一棵树，我们只需要在树上倍增一下就能快速计算了

代码

#include<bits/stdc++.h>
    #define re register
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=4e5+5;
    struct E{int v,nxt;}e[maxn];
    struct Seg{int l,r,rk;}a[maxn];
    int n,m,sz,T;
    int head[maxn],num,id[maxn],lg[maxn];
    int f[20][maxn],deep[maxn];
    inline void add(int x,int y) {
        e[++num].v=y;e[num].nxt=head[x];head[x]=num;
    }   
    inline int cmp(const Seg &A,const Seg &B) {return A.l<B.l;}
    void dfs(int x) {
        for(re int i=1;i<=lg[deep[x]];++i)
            f[i][x]=f[i-1][f[i-1][x]];
        for(re int i=head[x];i;i=e[i].nxt) {
            deep[e[i].v]=deep[x]+1;
            f[0][e[i].v]=x;dfs(e[i].v);
        }
    }
    int main() {
        n=read(),m=read();T=m;m=0;
        for(re int L,R,i=1;i<=n;i++) {
            L=read(),R=read();
            if(L<=R) 
                a[++m].l=L,a[m].r=R,a[m].rk=i,a[++m].l=L+T,a[m].r=R+T;
            else a[++m].l=L,a[m].r=R+T,a[m].rk=i,a[++m].l=L+T,a[m].r=T+T;
        }
        std::sort(a+1,a+m+1,cmp);
        for(re int i=1;i<=m;i++) id[a[i].rk]=i;
        for(re int i=2;i<=m;++i) lg[i]=lg[i>>1]+1;
        for(re int now=1,i=1;i<=m;i++) {
            while(now<m&&a[now+1].l<=a[i].r) ++now;
            if(i!=now) add(now,i);else deep[i]=1,dfs(i);
        }
        for(re int i=1;i<=n;++i) {
            int x=id[i];int to=a[x].l+T;
            if(a[x].r>=to) {putchar('1');putchar(' ');continue;}
            for(re int j=lg[deep[x]];j>=0;--j)
            if(f[j][x]&&a[f[j][x]].r<to) x=f[j][x];
            printf("%d ",deep[id[i]]-deep[f[0][x]]+1); 
        }
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11498688.html

[Link 1]: https://www.luogu.org/problem/P4155