注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

APIO2007[风铃/mobiles]  

2010-04-19 19:55:05|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

本来挺水的题,却花了我好久时间啊,后来发现是一个边界出错了。唉。

然后,这道题就是直接做就行了。

需要注意的是如果递归深度超过32,可以直接判断无解,避免数据中出现变态的链。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-19

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

 

#define MAXN 100000

#define NOCHILD -1

#define MAXDEPTH 32

#define MAX(a,b) ((a)>(b)?(a):(b))

#define get_height(root) ((root)==NOCHILD?0:height[(root)])

#define get_have(root) ((root)==NOCHILD?0:have[(root)])

#define is_full(height,have) (((1<<height)-1)==have)

 

struct Tree{int left,right;};

 

int n;

Tree tree[MAXN];

int height[MAXN];

long long int have[MAXN];

bool noanswer;

int answer;

 

int dfs_get_height(int root,int depth=1)

{

    if (depth>MAXDEPTH)

       return noanswer=true;

   

    if (root==NOCHILD) return 0;

    else

    {

        int left_height=dfs_get_height(tree[root].left,depth+1);

        int right_height=dfs_get_height(tree[root].right,depth+1);

        return height[root]=MAX(left_height,right_height)+1;

    }

}

long long int dfs_get_have(int root,int depth=1)

{

    if (depth>MAXDEPTH)

       return noanswer=true;

   

    if (root==NOCHILD) return 0;

    else

    {

        long long int left_have=dfs_get_have(tree[root].left,depth+1);

        long long int right_have=dfs_get_have(tree[root].right,depth+1);

        return have[root]=left_have+right_have+1;

    }

}

bool dfs_judge(int root)

{

     if (noanswer) return false;

     if (root==NOCHILD) return true;

    

     int left=tree[root].left;

     int right=tree[root].right;    

     int left_height=get_height(left);

     int right_height=get_height(right);

     long long int left_have=get_have(left);

     long long int right_have=get_have(right);

     bool left_is_full=is_full(left_height,left_have);

     bool right_is_full=is_full(right_height,right_have);

    

     if (left_height==right_height)

     {

        if (left_is_full)

             return dfs_judge(right);

        else if (right_is_full)

        {

             answer++;

             return dfs_judge(left);

        }

        else return false;

     }

     else if (left_height+1==right_height)

     {

          if (right_is_full)

          {

             answer++;

             return dfs_judge(left);

          }

          else if (left_is_full)

          {

               answer++;

               return dfs_judge(right);

          }

          else return false;

     }

     else if (left_height==right_height+1)

     {

          if (left_is_full)

             return dfs_judge(right);

          else if (right_is_full)

               return dfs_judge(left);

          else return false;

     }

     else return false;

}

 

int main()

{

    //freopen("mobiles.in","r",stdin);

    //freopen("mobiles.out","w",stdout);

    scanf("%d\n",&n);

    for (int i=0;i<n;i++)

    {

        int l,r;

        scanf("%d %d\n",&l,&r);

        if (l>0) tree[i].left=l-1;

        else tree[i].left=NOCHILD;

        if (r>0) tree[i].right=r-1;

        else tree[i].right=NOCHILD;

    }

   

    dfs_get_height(0);

    dfs_get_have(0);

   

    if (dfs_judge(0)) printf("%d\n",answer);

    else printf("-1\n");

    //fclose(stdin);

    //fclose(stdout);

    return 0;

}

 

  评论这张
 
阅读(360)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018