洛谷 P3740 [HAOI2014]贴海报

题目描述

Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的electoral墙。

张贴规则如下：

electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子；
所有张贴的海报的高度必须与electoral墙的高度一致的；
每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报；
后贴的海报可以覆盖前面已贴的海报或部分海报。

现在请你判断，张贴完所有海报后，在electoral墙上还可以看见多少张海报。

输入输出格式

输入格式：

第一行： N M 分别表示electoral墙的长度和海报个数

接下来M行: Ai Bi 表示每张海报张贴的位置

输出格式：

输出贴完所有海报后，在electoral墙上还可以看见的海报数。

这题其实挺不错的，很典型的那种区间染色问题，所以记录一下，以便日后复习。

解法一：线段树

这种题一看就是线段树，我们选择边判断边建树，这样就省去了build和pushdown。把线段树用来存储每条线段是否全部露出来，判断的时候，如果目标线段里有一个点没有被挡住（即segtree[root]==0），那么这条海报就会露出来，ans++，然后把整条线段染色后上推，由于我们刚刚对线段树储存元素的要求，所以上推法则就是：如果一个点有一个子树有标记，那么它也有标记。记得从最上面那个海报开始判断，这样应该就没什么问题了。

#include<cstdio>

#include<iostream>

using namespace std;

int flag,sum[],i,m,n;

int a[],b[],ans;

inline void pushup(int rt){

    sum[rt]=sum[rt<<]&&sum[rt<<|];

}

inline void cck(int rt,int l,int r,int x,int y){

    if (sum[rt]) return;

    if (x>r||y<l) return;

    if (x<=l&&r<=y){

        flag=; sum[rt]=;

        return;

    }

    int mid=(l+r)>>;

    if (mid>=x) cck(rt<<,l,mid,x,y);

    if (mid<r) cck(rt<<|,mid+,r,x,y);

    pushup(rt);

}

int main(){

    scanf("%d%d",&m,&n);

    m=;

    for (i=; i<=n; i++){

        scanf("%d%d",&a[i],&b[i]);

        m=max(m,b[i]);

    }

    for (i=n; i>=; i--){

        flag=;

        cck(,,m,a[i],b[i]);

        if (flag) ans++;

    }

    printf("%d",ans);

    return ;

}

解法二：浮水法

这是一种专门解决区间染色问题的方法，思路大概是这样：

还是倒着判断，找到与海报i相交的海报j，不管他们的公共部分（因为被j挡住了），之后判断它们不相交的部分（这时i的面积变成了公共部分的面积，可能有两个公共部分，这里由递归实现），方法详见代码注释。

inline void water(int l,int r,int now,int p){ //p就是i，now用来枚举j，l,r是当前判断i的边界，a是左边界，b是右边界
　　 if (vis[p]) return;　　//vis用于快速推出递归

    while (now<=n&&(l>=b[now]||r<=a[now])) now++; //这里是判断相交

    if (now>n){　　　　　　//now>n则没有海报挡得住i了

        ans++; vis[p]=;

        return;

    }

    if (l<a[now]&&r>a[now]) water(l,a[now],now+,p); //不好讲，要不，自己画个图模拟一下？

    if (r>b[now]&&l<b[now]) water(b[now],r,now+,p); //同上？

}

完整代码

#include<cstdio>

#include<iostream>

using namespace std;

int vis[],a[],b[];

int ans,n,m,i;

inline void water(int l,int r,int now,int p){

    if (vis[p]) return;

    while (now<=n&&(l>=b[now]||r<=a[now])) now++;

    if (now>n){

        ans++; vis[p]=;

        return;

    }

    if (l<a[now]&&r>a[now]) water(l,a[now],now+,p);

    if (r>b[now]&&l<b[now]) water(b[now],r,now+,p);

}

int main(){

    scanf("%d%d",&m,&n);

    for (i=; i<=n; i++){

        scanf("%d%d",&a[i],&b[i]);

        b[i]++;

    }

    vis[n]=; ans=;

    for (i=n-; i>=; i--){

        water(a[i],b[i],i+,i);

    }

    printf("%d",ans);

    return ;

}

巴特西

洛谷 P3740 [HAOI2014]贴海报

题目描述

输入输出格式

最新文章

热门文章