APIO2007[风铃/mobiles]

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

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

需要注意的是如果递归深度超过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;

}

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注