C国旗计划实现源码分享

Description

传送门

Solution

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

我们用st表记录以某个位置开始，派了1<

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

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

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

1 2 3 4 5

Code

#include

#include

#include

#include

#include

using namespace std;

int n,m,l,r,st[400010][20],bin[20],ans[200010];

struct node{int l,id;

}a[400010];int cnt=0;

bool cmp(node a,node b){return a.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,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

}

ans[a[i].id]=cnt;

}

for (int i=1;i<=n;i++) printf("%d ",ans[i]);

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!