UVA1707 Surveillance

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

题目大意

给定一个长度为

n

的环，有

k

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

样例输入

CPP

输出

CPP

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代码

CPP

#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

题解：UVA1707 Surveillance

文章操作