首页 > 代码库 > 离散-ACM一道强有力的工具

离散-ACM一道强有力的工具

2024-07-10 13:42:18   223人阅读

最近几天散搞哭了，都怪以前看到没好好学。。。

  就拿一道题来说事PKU：1151，以前Matrix67写过这道题的BLOG，引用一下：

   VOJ1056(http://www.vijos.cn/Problem_Show.asp?id=1056) 永远是离散化的经典问题。大意是给定平面上的n个矩形（坐标为整数，矩形与矩形之间可能有重叠的部分），求其覆盖的总面积。平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”（把矩形所在的位置填上True）。可惜这个想法在这里有些问题，因为这个题目中坐标范围相当大（坐标范围为-10^8到10^8之间的整数）。但我们发现，矩形的数量n<=100远远小于坐标范围。每个矩形会在横纵坐标上各“使用”两个值， 100个矩形的坐标也不过用了-10^8到10^8之间的200个值。也就是说，实际有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面，省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200之间的数，于是一个200*200的二维数组就足够了。实现方法正如本文开头所说的“排序后处理”。对横坐标（或纵坐标）进行一次排序并映射为1到2n的整数，同时记录新坐标的每两个相邻坐标之间在离散化前实际的距离是多少。这道题同样有优化的余地。

我具体讲讲怎么优化：

  当我们定义一个Boolean类型去解小范围的这道题是，假如是这样的图形：

 哎呀，好挫的一张图。。（该学学绘图软件了）

坐标分别对应是：（0,0）-（2,2），（2，2）-（4,4）；

当我们用Boolean枚举是，每次枚举一个小格子的左上角的状态代替这个单位面积;比如：

 可以化成这样的左边矩阵：11000

                                   11110

                                   01110

                                   01110

具体每个格子代表为1；但是程序怎么写，可以把每个格子的一个角的状态表示这个格子的状态，这样就OK了，我开始在这里纠结了老半天

      但是这道题、N和M如此大，普通的标记肯定没戏，

SO ，离散：

        神马是离散，就是把点的位子分别映射对应， 

         这里是：我们排序好，然后把这些点的位置分别映射其排序好的序号。（好像很绕口的样子） 23333；

         等下在结合代码看看，

         然后我们发现对应好一个新的图形出现了，

         然后再用前面的方法去枚举标状态；

         最后统计；

#include<iostream>#include <algorithm>#include<string.h>#include<cstdio>#include<math.h>using namespace std;double x[201],y[201],s[101][4];int xy[201][201];int n,cas=0;double sum;int main(){    int i,j,k;    while(cin>>n)    {        if(n==0)   break;        cas++;        k=0;        sum=0.0;        memset(xy,0,sizeof(xy));        for(i=1;i<=n;i++)        {            cin>>s[i][0]>>s[i][1]>>s[i][2]>>s[i][3];            x[k]=s[i][0];            y[k]=s[i][1];            k++;            x[k]=s[i][2];            y[k]=s[i][3];            k++;        }        sort(x,x+2*n);        sort(y,y+2*n);        for (int i=1;i<=n;i++)        {         int  i1=lower_bound(x,x+2*n,s[i][0])-x;//二分查找，跟普通的FOR语句一样         int  j1=lower_bound(y,y+2*n,s[i][1])-y;         int  i2=lower_bound(x,x+2*n,s[i][2])-x;         int  j2=lower_bound(y,y+2*n,s[i][3])-y;         for (int p1=i1;p1<i2;p1++)//标记状态，记住我们是以一个方块的角标记状态所以p1<i2，不是<=         for (int p=j1;p<j2;p++)         xy[p1][p]=1;        }        for (int i=0;i<2*n;i++)//统计            for (int j=0;j<2*n;j++)            if (xy[i][j]) {            sum+=(x[i+1]-x[i])*(y[j+1]-y[j]);        }         printf("Test case #%d\n",cas);         printf("Total explored area: %.2f\n",sum);         printf("\n");    }    return 0;}
View Code

 

最后还得贴代码，尼玛，我自己的看不懂怎么描述的？

还有跟我一样陷入离散杯具的孩子，欢迎留言，一起解决，^&&^^

                                                                               

                                                                                 


联系
我们