集训队作业happy解题报告

1、Happy 问题解题一、 算法描述一个平行于坐标轴的矩形是由其左上角坐标和右下角坐标决定的，而一个坐标有x 坐标和 y 坐标两个，所以一个矩形是由四个量共同决定的。如果简单采用离散化的思路，必须首先确定它的左 x 坐标和右 x 坐标，最后在一次扫描中确定y 坐标，时间复杂度为被选取的点都对由它和右边界确定的最大矩形没有影响，因而可以被删除。如果用有序表来保存所有的y 坐标，则在删除这些无用节点后，最大矩形的上下边界由该点的前驱点和后继点分别决定。如果在实现过程中采用静态实现双向链表的方法，并且引入散列对每一个 y 坐标值在链表中进行定位，则找出最大矩形，并该结构的事件复杂度为W,L,n;lon

2、g ans;datmaxn2;/ hashmaxl+1;/line所有点的信息所有存在的y 坐标，hash所有 y 坐标在 line 中的listmaxn3,mapmaxn;/list了当前右边界左边的所有 y 坐标，/其中，lista0y 坐标的值，/lista1,lista2分别其当前的前驱结点和后继结点/map了一个点在 list 中的对应位置void qsort(a,b);/以 x 坐标为第一序，y 坐标为第二序对所有点坐标排序inline long max(long a,long b)return ab?a:b;main()tol,i;n=1;m=0; finWLtol; for (

3、i=0;iab;if (!a|!b|a=W|b=L) continue;/所有在地图边缘的点可以不用考虑 datn0=a;datn1=b;n+;datn0=W;datn1=L;n+;/加入一个虚拟点 qsort(1,n-1);/排序memsesh,0,sizeof(hash);for (i=1;in;)/移动右边界memset(list,0,sizeof(list); memset(map,0,sizeof(map); list00=0;list01=-1;/加入虚拟 y=0 的坐标t=0,j;for (j=1;jL;j+)if (hashj)/该 y 坐标出现在当前右边界的左边ans=max

4、(ans,(long(j)-listt0)*dati0);listt2=t+1;t+;listt0=j;listt1=t-1;/加入到 y 坐标列表，并计算新面积maphashj=t;/建立点到 y 坐标列表的对应方式ans=max(ans,(long(L)-listt0)*dati0);listt2=t+1;t+;listt0=L;listt1=t-1;listt2=-1;/加入 y=L 的虚拟点for (j=1;ji;j+)/移动左边界if (!mapj) continue;/该点不在当前需要处理的 y 坐标列表中x=mapj,x0=listx1,x1=listx2; ans=max(ans,(long(listx10)-listx00)*(dati0-datj0); listx02=x1;listx11=x0;/将点 x 从 y 坐标列表中脱钩dohashdati1=i;/将点 i 加入已出现集合i+;/移动右边界while (in&dati0=dati-10);fouans=b) return; x=dat(a+b)/20,i=a,j=b;while (i=j)while (dati0 x) j-; if (i=j)t=dati0;da