题解：UVA1707 Surveillance

· · 题解

UVA1707 Surveillance

（本题同P6902，但是多组数据）

题目大意

给定一个长度为 n 的环，有 k 个区间，求出最少需要多少个区间可以将环完全覆盖。以官方的样例为例（多组输入输出），这里就重点看最后两个样例。

样例输入

100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20
8 2
8 3
5 7
8 2
8 4
5 7

输出

3
impossible
2

解决思路

由最后两个样例（以下倒数第2个样例称之为样例1，最后一个样例称之为样例2）可以看出，题目中的环如图所示。

样例1

所以该样例输出impossible。

样例2

所以该样例输出2。

样例分析

由上图可以发现，我们可以把环断成长度为 2n 的链，只要满足其中一段的长度大于等于 n 就可行。

如果用暴力枚举一段区间的左端点，那么时间复杂度为 O(n^2)。可以使用ST表进行优化，可以用 f_{i,j} 表示从 i 点往后跳 2^j 个区间（包括 i 点所在的区间）所可以到达的最远的小标不大于 2n 的点的下一个点，即下一个线段最小的左端点。然后再利用倍增找出长度不满足条件的最后一个点（如下图红线所示），再加上一个区间（如下图蓝线所示），这样复杂度就为 O(n\,\log\,n)。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
struct qu{
    int l,r;
};
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
bool cmp(qu a,qu b){return a.l<b.l;}
int f[N][21],n,k,s,e,ans=2147483647;
qu a[N+10];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while(cin>>n>>k){//多组数据
        memset(f,0,sizeof f);ans=2147483647;
        for(int i=0;i<k;i++){
            cin>>a[i].l>>a[i].r;
            if(a[i].l>a[i].r) a[i].r+=n;
        }
        sort(a,a+k,cmp);//按l排序
        int nw=0,r=0;
        for(int i=1;i<=2*n;i++){
            while(nw<k&&a[nw].l<=i)r=max(r,a[nw].r+1),nw++;//+1最远可以到达的点的下一个点
            f[i][0]=r;
        }
        for(int j=1;j<=20;j++){
            for(int i=1;i<=2*n;i++){
                f[i][j]=f[f[i][j-1]][j-1];
            }
        }
        for(int i=1;i<=n;i++){
            int nw=i,sum=0;
            for(int j=20;j>=0;j--){
                if(f[nw][j]&&f[nw][j]-i<n){
                    nw=f[nw][j];
                    sum+=(1<<j);
                }
            }
            sum++;
            nw=f[nw][0];
            if(nw-i>=n) ans=min(ans,sum);
        }
        ans==2147483647?cout<<"impossible\n":cout<<ans<<"\n";
    }
    return 0;
}
//参考题解：https://www.luogu.com.cn/article/5clgr3pw