[BZOJ4444][Scoi2015]国旗计划-[ST表]

2018-08-26 17:15:46来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

Description

传送门

Solution

说真的这道题在场上没做出来的我必定是脑子有洞。。

我们用st表记录以某个位置开始,派了1<<j个战士能到达的最远位置。

由于边境线是一圈,我们把把它当成链并复制一遍,操作的时候注意判断是否覆盖了一圈就好。

PS:边防站是点,它所谓覆盖边境线,是指每一个区间都要有士兵跑。如下图,这可不是每个点有士兵就算了的。

比如说一个士兵在1或3,一个在4或5,看起来非常没有毛病,然而3-4的区间没有人,就不算覆盖了啊啊啊。(不过怕是只有我这种脑袋缺点什么的人才会把它理解成覆盖点吧。。)

    1     2     3     4     5          

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,l,r,st[400010][20],bin[20],ans[200010];
struct node{int l,r,id;
}a[400010];int cnt=0;
bool cmp(node a,node b){return a.l<b.l;}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&l,&r);
        if (l>r) {a[i*2-1]=node{l,r+m,i};a[i*2]=node{l+m,r+2*m,0};}
        else {a[i*2-1]=node{l,r,i};a[i*2]=node{l+m,r+m,0};}
    }
    sort(a+1,a+2*n+1,cmp);
    
    int now=0;
    for (int i=1;i<=2*n;i++)
    {
        while (a[now+1].l<=a[i].r&&now<2*n) now++;
        st[i][0]=now;
    }
    bin[0]=1;
    for (int i=1;i<=18;i++) bin[i]=bin[i-1]<<1;
    for (int j=1;j<=18;j++)
        for (int i=1;i<=2*n-bin[j]+1;i++)
            st[i][j]=st[st[i][j-1]][j-1];
            
    int tp,cnt;
    for (int i=1;i<=2*n;i++)
    if (a[i].id)
    {
        tp=a[i].l+m;
        now=i;cnt=2;
        for (int j=18;j>=0;j--) 
        if (st[now][j]){
            if (a[st[now][j]].r<tp) now=st[now][j],cnt+=bin[j];    
        }
        ans[a[i].id]=cnt;    
    }
    for (int i=1;i<=n;i++) printf("%d ",ans[i]);

}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++ 学习笔记(三)string 类

下一篇:HDU4035 Maze(期望DP)