首页 > ACM题库 > HDU-杭电 > HDU 1821 Get The Treasure-计算几何-[解题报告] C++
2013
12-23

HDU 1821 Get The Treasure-计算几何-[解题报告] C++

Get The Treasure

问题描述 :

One day, a team of archaeologists found a figure and some ancient charactors at a relique. The figure was made up of n points distributing on a circle symmetrically.
After investigating the charactors, they got to know that a treasure was hid beneath the figure. In order to open the door to the treasure, they must redraw all the lines between any two points in the figure with some colors. If the figure was right, the door would open.
Now they want to know how many times they have to try at most to open the door, and they ask you for help.

输入:

Each test case contains an integer n and a string S in a line. n is the number of points in the figure and S is a string made up of distinct capital letters, each indicating a color that can be used to redraw the figure. 3 <= n <= 50.

输出:

Each case outputs the maximum times they may try in one line. Note that two figures are considered the same if one can be obtained by having rotation and mirroring on the other one.

样例输入:

3 BW
3 RGB
4 RG

样例输出:

4
10
19

题意:有T给测试数据,每组数据先给一个数字N,接下来的N行里,每行里有6个数字,分别是x1,y1,z1,x2,y2,z2,表示这个长方体x轴方向的范围从x1到x2,y坐标和z坐标类似,求至少有三个长方体相交的体积是多少。

        因为Z轴的范围很小,所以我们将Z轴离散化之后,枚举Z[i]和Z[i+1]之间,矩形并时覆盖了三次以上的面积,那么这时候,就可以求出在Z[i]和Z[i+1]之间题目所求的体积,遍历一次Z坐标,也就得出了答案。如果求矩形并时覆盖超过三次的面积,与hdu 1255 覆盖的面积,是很类似的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
typedef long long LL;
const int N=2005;

struct CUBE
{
    int x1,y1,z1;
    int x2,y2,z2;
    void get()
    {
        scanf("%d%d%d",&x1,&y1,&z1);
        scanf("%d%d%d",&x2,&y2,&z2);
    }
}cube[N];
struct Line
{
    int x,y1,y2,flag;
    Line(){}
    Line(int a,int b,int c,int d)
    { x=a;y1=b;y2=c;flag=d; }
    bool operator<(const Line &b)const
    { return x<b.x; }
};
struct node
{
    int lft,rht,flag,len[4];
    int mid(){return MID(lft,rht);}
    void init(){memset(len,0,sizeof(len));}
};

vector<int> y,z;
vector<Line> line;
map<int,int> H;

struct Segtree
{
    node tree[N*4];
    void calu(int ind)
    {
        if(tree[ind].flag>=3)
        {
            tree[ind].len[3]=tree[ind].len[0];
            tree[ind].len[2]=tree[ind].len[1]=0;
        }
        else if(tree[ind].flag==2)
        {
            tree[ind].len[2]=tree[ind].len[0];
            if(tree[ind].lft+1==tree[ind].rht)
            {
                tree[ind].len[1]=tree[ind].len[3]=0;
            }
            else
            {
                tree[ind].len[3]=tree[LL(ind)].len[3]+tree[RR(ind)].len[3]
                    +tree[LL(ind)].len[2]+tree[RR(ind)].len[2]
                    +tree[LL(ind)].len[1]+tree[RR(ind)].len[1];
                tree[ind].len[1]=0;
                tree[ind].len[2]-=tree[ind].len[3];
            }
        }
        else if(tree[ind].flag==1)
        {
            tree[ind].len[1]=tree[ind].len[0];
            if(tree[ind].lft+1==tree[ind].rht)
            {
                tree[ind].len[2]=tree[ind].len[3]=0;
            }
            else
            {
                tree[ind].len[3]=tree[LL(ind)].len[3]+tree[RR(ind)].len[3]
                    +tree[LL(ind)].len[2]+tree[RR(ind)].len[2];
                tree[ind].len[2]=tree[LL(ind)].len[1]+tree[RR(ind)].len[1];
                tree[ind].len[1]-=(tree[ind].len[2]+tree[ind].len[3]);
            }
        }
        else
        {
            if(tree[ind].lft+1==tree[ind].rht)
            {
                tree[ind].len[1]=tree[ind].len[2]=tree[ind].len[3]=0;
            }
            else
            {
                tree[ind].len[3]=tree[LL(ind)].len[3]+tree[RR(ind)].len[3];
                tree[ind].len[2]=tree[LL(ind)].len[2]+tree[RR(ind)].len[2];
                tree[ind].len[1]=tree[LL(ind)].len[1]+tree[RR(ind)].len[1];
            }
        }
    }
    void build(int lft,int rht,int ind)
    {
        tree[ind].lft=lft;    tree[ind].rht=rht;
        tree[ind].init();    tree[ind].flag=0;
        tree[ind].len[0]=y[rht]-y[lft];
        if(lft+1!=rht)
        {
            int mid=tree[ind].mid();
            build(lft,mid,LL(ind));
            build(mid,rht,RR(ind));
        }
    }
    void updata(int st,int ed,int ind,int valu)
    {
        int lft=tree[ind].lft,rht=tree[ind].rht;
        if(st<=lft&&rht<=ed) tree[ind].flag+=valu;
        else
        {
            int mid=tree[ind].mid();
            if(st<mid) updata(st,ed,LL(ind),valu);
            if(ed>mid) updata(st,ed,RR(ind),valu);
        }
        calu(ind);
    }
}seg;
int main()
{
    int t,t_cnt=0;
    scanf("%d",&t);
    while(t--)
    {
        y.clear(); z.clear(); line.clear(); H.clear();

        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            cube[i].get();
            y.push_back(cube[i].y1); y.push_back(cube[i].y2);
            z.push_back(cube[i].z1); z.push_back(cube[i].z2);
        }
        printf("Case %d: ",++t_cnt);
        if(n<3) {puts("0");continue;}
        else
        {
            sort(y.begin(),y.end());
            sort(z.begin(),z.end());
            y.erase(unique(y.begin(),y.end()),y.end());
            z.erase(unique(z.begin(),z.end()),z.end());
            for(int i=0;i<(int)y.size();i++) H[y[i]]=i;

            LL res=0;
            seg.build(0,(int)y.size()-1,1);
            for(int i=0;i<(int)z.size()-1;i++)
            {
                line.clear();
                for(int j=0;j<n;j++)
                {
                    if(cube[j].z1<=z[i]&&cube[j].z2>=z[i+1])
                    {
                        line.push_back(Line(cube[j].x1,cube[j].y1,cube[j].y2,1));
                        line.push_back(Line(cube[j].x2,cube[j].y1,cube[j].y2,-1));
                    }
                }
                sort(line.begin(),line.end());
                for(int j=0;j<(int)line.size();j++)
                {
                    if(j!=0) res+=(z[i+1]-z[i])*(line[j].x-line[j-1].x)*(LL)seg.tree[1].len[3];
                    seg.updata(H[line[j].y1],H[line[j].y2],1,line[j].flag);
                }
            }
            printf("%I64d\n",res);
        }
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/shiqi_614/article/details/8236711


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3