Yui的狗窝
Yui的狗窝
hihocoder 1342 Full Binary Tree Picture 树

原题:https://hihocoder.com/problemset/problem/1342

原先想着完整的建一棵树,结果半途觉得不建树也行,所以出现了一些多余的代码。
只要理清楚两个问题,相信这个问题就会变得简单。
1.如何判断点在矩形内。
2.如何计算子节点在坐标系中的坐标。

#include<iostream>
using namespace std;
int x1,y1,x2,y2;
int res,n,m;
struct node
{
    int x,y,step;
    node(int a,int b):x(a),y(b)
    {
        left=NULL;
        right=NULL;
    }
    ~node()
    {
        delete(left);
        delete(right);
    }
};
int CalStep(int hi)
{
    if(hi==1)
        return 0;
    if(hi==2)
        return 1;
    if(hi==3)
        return 2;
    return CalStep(hi-1)*2+1;
}
void CreateTree(node par,int lev)
{
    node left(par.x+par.step+1,par.y-par.step-1);
    node right(par.x+par.step+1,par.y+par.step+1);
    if(left.x>=x1 && left.y>=y1 && left.x<=x2 && left.y<=y2)
    {
        res++;
    }
    if(right.x>=x1 && right.y>=y1 && right.x<=x2 && right.y<=y2)
    {
        res++;
    }
    if(lev==n)
        return;
    left.step=par.step/2;
    right.step=left.step;
    CreateTree(left,lev+1);
    CreateTree(right,lev+1);
}
int main()
{
    while(cin>>n>>m)
    {
        while(m--)
        {
            cin>>x1>>y1>>x2>>y2;
            res=0;
            node ro(0,0);
            if(ro.x>=x1 && ro.y>=y1 && ro.x<=x2 && ro.y<=y2)
                res++;
            ro.step=CalStep(n);
            CreateTree(ro,1);
            cout<<res<<endl;
        }
    }
}
没有标签
首页      算法训练      hihocoder 1342 Full Binary Tree Picture 树
https://secure.gravatar.com/avatar/d0fe7f1b17d5e9122db921e3a8cc327f?s=256&d=mm&r=g

Suzumiya, Yui

文章作者

发表评论

textsms
account_circle
email

Yui的狗窝

hihocoder 1342 Full Binary Tree Picture 树
原题:https://hihocoder.com/problemset/problem/1342 原先想着完整的建一棵树,结果半途觉得不建树也行,所以出现了一些多余的代码。 只要理清楚两个问题,相信这个问题就会变得简单。 …
扫描二维码继续阅读
2017-11-21


没有激活的小工具