题解 P3740 【[HAOI2014]贴海报】

· · 题解

我实在没有想到用线段树

所以看见坐标那么大，就用了离散化

离散化每个出现的区间，再暴力完成区间覆盖

但是惊奇的是，我离散化错了

找了整个机房的人都没有找到错误

可以看到，我交了若干遍/好吧小号/，每次都WA4个点

同学在vjudge上A了在这里WA同样的点

所以拍了一个下午没有拍出来，心一狠拍个大数据

WA了，##于是手玩38个区间上百个端点的大数据。。

嗯，玩出来了

当出现这种情况[5,7],[1,5],[7,8]按顺序覆盖的话，就会出问题：

离散化为区间[2,3],[1,2],[3,4]那么按这样覆盖就会把第一张海报覆盖掉，但实际上第一张海报没有完全被覆盖

那该怎么办？solution：在每个离散区间中强行加一个点比如说在[1,5]加上2，[5,7]加上6，[7,8]由于是相邻的所以不要加

这样问题就解决了

附上代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m;//长度最大为n，m张海报
int tmp[4001],cnt=0;//排序数组
int r[4001],cnt1=0;//去重后的
int fx[1001],fy[1001];//映射数组f[i]表示第i张海报在离散化后的轴上的坐标
int x[1001],y[1001];
int zhou[4001];//新数轴
int tong[1001];//各种海报能看见的桶
int find(int x)
{
    int L=1,R=cnt1;
    while(L<R)
    {
        int mid=(L+R)>>1;
        if(r[mid]>=x)R=mid;
        else L=mid+1;
    }
    return R;
}
int main()
{
    //freopen("data.in","r",stdin);
    //freopen("test.out","w",stdout);
    //输入排序离散化
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        tmp[++cnt]=x[i];
        tmp[++cnt]=y[i];
    }
    sort(tmp+1,tmp+cnt+1);
    //for(int i=1;i<=cnt;i++)printf("tmp[%d]=%d\n",i,tmp[i]);
    r[++cnt1]=tmp[1];
    for(int i=2;i<=cnt;i++)
    {
        if(tmp[i]!=tmp[i-1])
        {
            r[++cnt1]=r[cnt1-1]+1;//最重要的一句
            if(tmp[i]!=r[cnt1])r[++cnt1]=tmp[i];
        }
    }
    //for(int i=1;i<=cnt1;i++)printf("r[%d]=%d ",i,r[i]);
    //printf("\n");
    for(int i=1;i<=m;i++)
    {
        fx[i]=find(x[i]);
        fy[i]=find(y[i]);
    }
    //for(int i=1;i<=m;i++)printf("fx[%d]=%d,fy[%d]=%d\n",i,fx[i],i,fy[i]);
    //操作
    for(int i=1;i<=m;i++)
        for(int w=fx[i];w<=fy[i];w++)zhou[w]=i;
    //for(int i=1;i<=cnt1;i++)printf("zhou[%d]=%d\n",i,zhou[i]);
    for(int i=1;i<=cnt1;i++)
    {
        if(r[i]>n)break;
        tong[zhou[i]]=1;
    }
    int ans=0;
    //for(int i=1;i<=m;i++)printf("tong[%d]=%d\n",i,tong[i]);
    for(int i=1;i<=m;i++)if(tong[i])ans++;
    printf("%d",ans);
    return 0;
}

希望能对你有帮助！