Loading...

bzoj4082 [Wf2014]Surveillance

check评论:0 条 remove_red_eye浏览量:421 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-07-30

bzoj权限题,这里发题目简述。

题目描述

给你一个长度为$len$的环,以及$n$个区间,要你选择尽量少的区间,使得它们完全覆盖整个环。问最少要多少个区间。

输入描述

输入数据的第一行是两个整数$len$和$n$,代表环的长度以及区间个数。之后n行描述的是n个区间,每个区间分别用一对数字$(a,b)$表示,若$a \leq b$则表示这个区间覆盖的是$[a,b]$部分,否则表示这个区间覆盖的是除掉$[a+1,b-1]$以外的其他部分。

输出描述

输出只有一行,一个整数,代表覆盖整个环所需要的最少区间个数。若无解,输出 $impossible$

样例输入

100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20

样例输出

3

这道题只需要将每个区间向它能跳到且右端点最远的区间连边,形成一棵树。

然后倍增一下,求每个点向上倍增最少多少步可以走完这整个环即可。

code:

#include <bits/stdc++.h>
using namespace std; 
#define maxn 1000005
#define inf 0x3f3f3f3f
int n,len,mn[maxn],fa[maxn][25];
struct node
{
    int l,r;
}a[maxn];
int ans;
bool cmp(node a,node b)
{
    return a.r<b.r;
}
int main()
{
    cin>>len>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        if(a[i].r<a[i].l)
        {
            a[i].r+=len;
        }
    }
    sort(a+1,a+n+1,cmp);
    mn[n+1]=inf;
    for(int i=n;i>=1;i--)
    {
        mn[i]=min(a[i].l,mn[i+1]);
    }
    int de=1;
    for(int i=1;i<=n;i++)
    {
        while(de<n&&mn[de+1]-1<=a[i].r)
        {
            de++;
        }
        if(de!=i)
        {
            fa[i][0]=de;
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=20;j++)
        {
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
    ans=inf;
    for(int i=1;i<=n;i++)
    {
        int x=i,s=1;
        for(int j=20;j>=0;j--)
        {
            if(fa[x][j]&&a[fa[x][j]].r<a[i].l+len)
            {
                x=fa[x][j];
                s+=(1<<j);
            }
            if(a[x].r<a[i].l+len-1&&fa[x][0])
            {
                x=fa[x][0];
                s++;
            }
            if(a[x].r>=a[i].l+len-1)
            {
                ans=min(ans,s);
            }
        }
    }
    if(ans==inf)
    {
        printf("impossible");
    }
    else
    {
        cout<<ans;
    }
}

chevron_left 洛谷P1250 种树
洛谷P1262 间谍网络 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名