首页 > ACM题库 > HDU-杭电 > HDU 4095-Very Boring Homework[解题报告]HOJ
2015
04-16

HDU 4095-Very Boring Homework[解题报告]HOJ

Very Boring Homework

问题描述 :

  Prof. Z thinks his homework is very hard for most of his students to solve (do you remember the task “Boring Homework”?) To his surprise, many students hand in correct solutions. He thinks the reason is actually the small size of the data set he used to test students’ programs rather than the low difficulty of the homework task. He decides to give his students the same homework again, but with enormous test cases. Of course, his students think his homework becomes even more boring this time. They need your help again.
  For the ones who don’t know what homework Prof. Z. had given to his students last time:
  
  You’re asked to draw a graph of a binary search tree (BST).

  A binary search tree, which may sometimes also be called ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
  The left subtree of a node contains only nodes with keys less than the node’s key.
  The right subtree of a node contains only nodes with keys greater than the node’s key.
  Both the left and right subtrees must also be binary search trees.
  –from Wikipedia

  Given a list of integer keys that should be inserted into the BST one by one orderly, we can form a unique BST. Moreover, Prof. Z wants the students to draw the graph of this BST.
  
  The rules to draw a graph of a BST are listed below:
  
1. The graph of a 1-node BST is a single ‘o’ (15th small Latin letter).
2. If a BST has a non-empty subtree, draw a single ‘|’ just above the subtree’s root, and a single ‘+’ just above the previous drawn ‘|’. Finally, in the row of ‘+’, use the least number (including 0) of ‘-’s to connect ‘+’ (corresponding to the left or right subtree) and ‘o’ (denoting the parent node of the subtrees).
3. The left subtree (if exists) must be drawn on the left side of its parent. Similarly, the right subtree (if exists) must be drawn on the right side of its parent.
4. The column of the BST’s root must not contain any characters belonging to left or right subtree.
5. For each node of the BST, the graph of its left subtree and the graph of its right subtree do not share common columns in the picture of the whole tree.

  After the whole BST has been drawn, we number the rows from top to bottom, counting from 1, and so do the columns from left to right, counting from 1.
  Due to the large scale of the tree, the graph will become so large that it is impossible for Prof. Z to check every detail of the graph this time. So you are only asked to hand in m fragments of that graph to Prof. Z instead of the whole one.

输入:

  The first line contains T, the number of test cases. T test cases follow.
  For each test case:
  The first line contains a positive integer N (N <= 100000).
  The second line contains N distinct integers, each of which can be represented by a 32-bit signed integer. These numbers should be inserted into an empty BST one by one in the given order.
  The third line contains an integer M (M <= 5).
  M lines follow, each contains four integers, which are the row and column number of the top left corner, and the number of rows Ri and columns Ci of the required graph fragment, respectively. All the input integers will be positive and fit into a 32-bit signed integer, except Ri and Ci, which will be less than or equal to 200 and greater than 0.

输出:

  The first line contains T, the number of test cases. T test cases follow.
  For each test case:
  The first line contains a positive integer N (N <= 100000).
  The second line contains N distinct integers, each of which can be represented by a 32-bit signed integer. These numbers should be inserted into an empty BST one by one in the given order.
  The third line contains an integer M (M <= 5).
  M lines follow, each contains four integers, which are the row and column number of the top left corner, and the number of rows Ri and columns Ci of the required graph fragment, respectively. All the input integers will be positive and fit into a 32-bit signed integer, except Ri and Ci, which will be less than or equal to 200 and greater than 0.

样例输入:

3
3
3 1 2
1
1 1 5 3
6 4 5 6 1 3 2
1
1 1 8 10
10
2 6 7 4 5 3 1 9 10 8
2
1 1 5 5
3 6 5 5

样例输出:

Case #1:
+-o
|  
o+ 
 | 
 o 

Case #2:
+--o+     
|   |     
o-+ o+    
  |  |    
 +o  o    
 |        
 o        

Case #3:
+o---
|    
o  +-
   | 
  +o+

o+   
 |   
 o-+ 
   | 
  +o+

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int MAXV = 101010;
const long long INF = 1010101010101LL;
struct pt{
    long long val;
    int order,l,r,pnt;
}p[MAXV];
bool cmp(pt x,pt y){return (x.val < y.val);}
int n,root;
void insert(int i){
    int j = i-1;
    while (p[j].order < p[i].order) j = p[j].pnt;
    p[i].l = p[j].r;
    p[p[i].l].pnt = i;
    p[j].r = i;
    p[i].pnt = j;
}

vector<pair<int,char> > c[200010];
int cnt;
struct stackifo{
    int x,deep;
    int state,tmp;
    stackifo(int a,int b,int c,int t)
    {
        x=a,deep=b,state=c,tmp=t;
    }
};
void dfs()
{
    stack<stackifo> S;
    stackifo s(0,0,0,0);
    S.push(stackifo(root,1,0,-1));
    int tmp;
    while (!S.empty())
    {
        s=S.top();
        S.pop();
        if (s.state==0)
        {
            if (p[s.x].l!=0)
            {
                s.state=1;
                S.push(s);
                S.push(stackifo(p[s.x].l,s.deep+2,0,-1));
                continue;
            }
            else s.state=2;
        }
        else if (s.state==1)
        {
            c[s.deep].push_back(make_pair(tmp,'L'));
            c[s.deep+1].push_back(make_pair(tmp,'|'));
            s.state=2;
        }
        if (s.state==2)
        {
            s.tmp=cnt++;
            c[s.deep].push_back(make_pair(s.tmp,'o'));
            s.state=3;
        }
        if (s.state==3)
        {
            if (p[s.x].r!=0)
            {
                s.state=4;
                S.push(s);
                S.push(stackifo(p[s.x].r,s.deep+2,0,-1));
                continue;
            }
            else s.state=5;
        }
        else if (s.state==4)
        {
            c[s.deep].push_back(make_pair(tmp,'R'));
            c[s.deep+1].push_back(make_pair(tmp,'|'));
            s.state=5;
        }
        if (s.state==5)
        {
            tmp=s.tmp;
        }
    }



  /*  if (p[x].l!=0)
    {
        int l=dfs(p[x].l,deep+2);
        c[deep].push_back(make_pair(l,'L'));
        c[deep+1].push_back(make_pair(l,'|'));
    }
    int ans=cnt++;
    c[deep].push_back(make_pair(ans,'o'));
    if (p[x].r!=0)
    {
        int r=dfs(p[x].r,deep+2);
        c[deep].push_back(make_pair(r,'R'));
        c[deep+1].push_back(make_pair(r,'|'));
    }
    return ans;*/
}

int find(int x,int v)
{
    int l=-1,r=c[x].size();
    while (l+1<r)
    {
        int m=(l+r)/2;
        if (c[x][m].first>v)
            r=m;
        else
            l=m;
    }
    return l;
}

int main(){
   // freopen("test.in","r",stdin);
    int T;scanf("%d",&T);
    for (int ca=1;ca<=T;ca++){
        scanf("%d",&n);
        printf("Case #%d:\n",ca);
        for (int i=1;i<=n;i++){
            scanf("%I64d",&p[i].val);
            p[i].l = p[i].r = p[i].pnt = 0;
            p[i].order = n-i;
        }
        p[0].order = n+1; p[0].val = -INF;
        p[0].l = p[0].r = p[0].pnt = 0;
        sort(p,p+1+n,cmp);
        for (int i=1;i<=n;i++)  insert(i);
        root = p[0].r;

        cnt=1;
        for (int i=1;i<200010;i++)
        {
            c[i].clear();
        }

        dfs();
    /*    for (int i=1;i<=n*2;i++)
        {
            for (int j=0;j<c[i].size();j++)
                printf("%d %c ",c[i][j].first,c[i][j].second);
            printf("\n");
        }*/
        int M;
        scanf("%d",&M);
        while (M-->0)
        {
            int x,y,a,b;
            scanf("%d%d%d%d",&x,&y,&a,&b);
            for (int i=x;i<x+a;i++)
            {
                int begin=find(i,y);
                char state=' ';
                if (begin>=0 && (c[i][begin].second=='L'|| (c[i][begin].second=='o'&& begin+1<c[i].size()&& c[i][begin+1].second=='R')))
                    state='-';
                if (begin<0 || c[i][begin].first<y) begin++;
                string ans="";
                for (int j=y;j<y+b;j++)
                {
                    if (begin<c[i].size() && c[i][begin].first==j)
                    {
                        if (c[i][begin].second=='L')
                        {
                            ans=ans+"+";
                            state='-';
                        }
                        else if (c[i][begin].second=='R')
                        {
                            ans=ans+"+";
                            state=' ';
                        }
                        else if (c[i][begin].second=='o')
                        {
                            ans=ans+"o";
                            if (begin+1<c[i].size() && c[i][begin+1].second=='R')
                                state='-';
                            else
                                state=' ';
                        }
                        else if (c[i][begin].second=='|')
                        {
                            ans=ans+'|';
                        }
                        begin++;
                    }
                    else
                    {
                        ans=ans+state;
                    }
                }
                bool flag=false;
                for (int k=0;k<ans.length();k++)
                {
                    if (ans[k]!=' ')
                    {
                        flag=true;
                        break;
                    }
                }
                if (flag)
                    puts(ans.c_str());
            }
            printf("\n");
        }

    }
    return 0;
}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

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