P2276 [HNOI2002]农场的果树

    • 0通过
    • 12提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 各省省选 2002 湖南
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Farmer John的农场环境优美,其中生长了许多苹果树,而苹果正是Farmer John农场里奶牛最喜爱的食物!

    一天,闲来无事的奶牛Besty坐在苹果树下。她忽然发现,农场里的苹果树都是的二叉树!——当然,这种二叉树并不是严格意义上的二叉树,它可能有左子树而不存在右子树,反之也有可能。

    刚学过Computer Science的Besty给二叉树上每个节点记录下其左子树的个节点数。例如下面的一棵树:

                3
                  /  \
                 1   3
                /  \  / \
               0    0 1  0
                 / \
                0   0

    随后,用先序遍历给这棵树编码,需要注意的是叶子节点上的数值不必考虑。为了更方便表述,Besty又在这样的编码前加入一个数字:该树上节点总数。于是,上面这棵数的编码就是:9 3 1 3 1。

    这样一来,每一种编码就对应了一棵唯一的二叉树。

    Besty还发现,农场里的所有二叉树的节点总数都相同!并且在节点总数确定的情况下,对任意的合法编码,农场里都存在唯一的一棵树与之对应!

    于是,Besty将所有的二叉树按照上述编码规则编码,然后以编码为关键字进行字典排序。

    现在,对于一个给定的编码,奶牛Besty想知道字典排序紧跟其后的编码是什么。

    输入输出格式

    输入格式:

    输入文件名:next.in

    输入文件有一行,为一个二叉树的编码。保证节点总数不超过5000。

    输出格式:

    输出文件名:next.out

    输出文件有一行,为按字典排序紧跟其后的编码是什么。如果输入的编码是最后一个,则输出-1。

    输入输出样例

    输入样例#1: 复制
    9 3 1 3 1
    输出样例#1: 复制
    9 3 1 3 2 0
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。