题解 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]由于是相邻的所以不要加 这样问题就解决了 附上代码 ```cpp #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; } ``` 希望能对你有帮助！