首页 > ACM题库 > HDU-杭电 > HDU 3642-Get The Treasury-线段树-[解题报告]HOJ
2014
11-30

HDU 3642-Get The Treasury-线段树-[解题报告]HOJ

Get The Treasury

问题描述 :

Jack knows that there is a great underground treasury in a secret region. And he has a special device that can be used to detect treasury under the surface of the earth. One day he got outside with the device to ascertain the treasury. He chose many different locations on the surface of the earth near the secret region. And at each spot he used the device to detect treasury and got some data from it representing a region, which may contain treasury below the surface. The data from the device at each spot is six integers x1, y1, z1, x2, y2 and z2 (x1<x2, y1<y2, z1<z2). According to the instruction of the device they represent the range of x, y and z coordinates of the region. That is to say, the x coordinate of the region, which may contain treasury, ranges from x1 to x2. So do y and z coordinates. The origin of the coordinates is a fixed point under the ground.
Jack can’t get the total volume of the treasury because these regions don’t always contain treasury. Through years of experience, he discovers that if a region is detected that may have treasury at more than two different spots, the region really exist treasure. And now Jack only wants to know the minimum volume of the treasury.
Now Jack entrusts the problem to you.

输入:

The first line of the input file contains a single integer t, the number of test cases, followed by the input data for each test case.
Each test case is given in some lines. In the first line there is an integer n (1 ≤ n ≤ 1000), the number of spots on the surface of the earth that he had detected. Then n lines follow, every line contains six integers x1, y1, z1, x2, y2 and z2, separated by a space. The absolute value of x and y coordinates of the vertices is no more than 106, and that of z coordinate is no more than 500.

输出:

The first line of the input file contains a single integer t, the number of test cases, followed by the input data for each test case.
Each test case is given in some lines. In the first line there is an integer n (1 ≤ n ≤ 1000), the number of spots on the surface of the earth that he had detected. Then n lines follow, every line contains six integers x1, y1, z1, x2, y2 and z2, separated by a space. The absolute value of x and y coordinates of the vertices is no more than 106, and that of z coordinate is no more than 500.

样例输入:

2
1
0 0 0 5 6 4
3
0 0 0 5 5 5
3 3 3 9 10 11
3 3 3 13 20 45

样例输出:

Case 1: 0
Case 2: 8

HDU 3642 Get The Treasury(离散化+线段树:扫描线)

http://acm.hdu.edu.cn/showproblem.php?pid=3642

分析:

       本题要求的是重叠3次及以上的立方体体积,由于Z轴范围很小,可以枚举Z轴,然后固定了Z轴之后,就是求二维矩形的面积交>=3次的总面积了.其实Z轴就算很大也可以求,只需要把Z轴离散化即可.

比如Z轴从小到大出现了1,10,100,1000共四个值.然后假设当前考虑Z==1时,那么只需要把那些包括了[1,10]区间的立方体加入到二维矩形球面积的线段树扫描线中即可.如何判断一个立方体包括了区间[1,10]呢? 只要该立方体的Z轴最小值<=1且Z轴最大值>1,那么它就必然包括了区间[1,10].想想是不是.

       对于每个给定的Z轴区间,我们只要求出交>=3次以上的总面积res,然后用res*该Z轴区间长度,即可求出该区间的ans体积.由于X轴的范围也很大,所以X轴也需要离散化处理.

       线段树需要维护的信息有:

cover:值为0,1,2,3,4… 表示当前节点控制的X轴区被覆盖的次数.

sum: 表示当前节点控制的X轴区域被覆盖次数>=3的总长度

len1: 表示当前节点控制的X轴区域被覆盖次数=1的总长度

len2: 示当前节点控制的X轴区域被覆盖次数=2的总长度

具体实现见代码.

AC代码:1468ms

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2222;
#define lson i*2,l,m
#define rson i*2+1,m+1,r
int cover[MAXN*4],sum[MAXN*4],len1[MAXN*4],len2[MAXN*4];
int X[MAXN],Z[MAXN];
int cnt_x,cnt_z;
struct seg
{
    int l,r,h,d;
    seg(){}
    seg(int a,int b,int c,int d):l(a),r(b),h(c),d(d){}
    bool operator < (const seg& b)const
    {
        return h<b.h;
    }
}ss[MAXN];
struct point
{
    int x,y,z;
    void read()
    {
        scanf("%d%d%d",&x,&y,&z);
    }
};
struct cube
{
    point a,b;
}cubes[MAXN];
void PushUp(int i,int l,int r)
{
    if(cover[i]>=3)
    {
        sum[i]=X[r+1]-X[l];
        len1[i]=len2[i]=0;
    }
    else if(cover[i]==2)
    {
        sum[i]=sum[i*2]+sum[i*2+1]+len1[i*2]+len1[i*2+1]+len2[i*2]+len2[i*2+1];
        len2[i]=X[r+1]-X[l]-sum[i];
        len1[i]=0;
    }
    else if(cover[i]==1)
    {
        sum[i]=sum[i*2]+sum[i*2+1]+len2[i*2]+len2[i*2+1];
        len2[i]=len1[i*2]+len1[i*2+1];
        len1[i]=X[r+1]-X[l]-sum[i]-len2[i];
    }
    else
    {
        sum[i]=sum[i*2]+sum[i*2+1];
        len1[i]=len1[i*2]+len1[i*2+1];
        len2[i]=len2[i*2]+len2[i*2+1];
    }
}
void update(int ql,int qr,int v,int i,int l,int r)
{
    if(ql<=l&&r<=qr)
    {
        cover[i]+=v;
        PushUp(i,l,r);
        return ;
    }
    int m=(l+r)>>1;
    if(ql<=m) update(ql,qr,v,lson);
    if(m<qr) update(ql,qr,v,rson);
    PushUp(i,l,r);
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int kase=1;kase<=T;kase++)
    {
        int n;
        cnt_x=cnt_z=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            cubes[i].a.read();
            cubes[i].b.read();
            X[cnt_x++]=cubes[i].a.x;
            X[cnt_x++]=cubes[i].b.x;
            Z[cnt_z++]=cubes[i].a.z;
            Z[cnt_z++]=cubes[i].b.z;
        }
        if(n<3)
        {
            printf("Case %d: 0\n",kase);
            continue;
        }
        sort(X,X+cnt_x);
        sort(Z,Z+cnt_z);
        cnt_x=unique(X,X+cnt_x)-X;
        cnt_z=unique(Z,Z+cnt_z)-Z;
        long long ans=0;

        for(int i=0;i<cnt_z-1;i++)
        {
            int cnt=0;
            long long res=0;
            for(int j=1;j<=n;j++)
            {
                if(cubes[j].a.z<=Z[i] && cubes[j].b.z>Z[i])
                {
                    ss[cnt++]=seg(cubes[j].a.x,cubes[j].b.x,cubes[j].a.y,1);
                    ss[cnt++]=seg(cubes[j].a.x,cubes[j].b.x,cubes[j].b.y,-1);
                }
            }
            sort(ss,ss+cnt);
            memset(cover,0,sizeof(cover));
            memset(sum,0,sizeof(sum));
            memset(len1,0,sizeof(len1));
            memset(len2,0,sizeof(len2));
            for(int j=0;j<cnt-1;j++)
            {
                int ql=lower_bound(X,X+cnt_x,ss[j].l)-X;
                int qr=lower_bound(X,X+cnt_x,ss[j].r)-X-1;
                update(ql,qr,ss[j].d,1,0,cnt_x-1);
                res +=(long long)sum[1]*(ss[j+1].h-ss[j].h);
            }
            ans += res*(Z[i+1]-Z[i]);
        }
        printf("Case %d: %I64d\n",kase,ans);
    }
}

参考:http://blog.csdn.net/u013480600/article/details/22625139


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  3. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。