P1267 排序二叉树

    • 18通过
    • 41提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 树形结构
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    一个边长为n的正三角形可以被划分成若干个小的边长为1的正三角形,称为单位三角形。边长为3的正三角形被分成三层共个小的正三角形,我们把它们从顶到底,从左到右以1~9编号,见下图。

    同理,边长为n的正三角形可以划分成n^2个单位三

    角形。

    四个这样的边长为n的正三角形可以组成一个三棱锥。我们将正三棱锥的三个侧面依顺时针次序(从顶向底视角)编号为A, B, C,底面编号为D。侧面的A, B, C号三角形以三棱锥的顶点为顶,底面的D号三角形以它与A,B三角形的交点为顶。

    上图为三棱锥展开后的平面图,每个面上标有圆点的是该面的顶,该图中侧面A, B, C分别向纸内方向折叠即可还原成三棱锥。我们把这A,B、C、D四个面各自划分成n2个单位三角形。

    对于任意两个单位三角形,如有一条边相邻,则称它们为相邻的单位三角形。显然,每个单位三角形有三个相邻的单位三角形。现在,把1—4n^2分别随机填入四个面总共4n^2个单位三角形中。

    现在要求你编程求由单位三角形组成的最大排序二叉树。所谓最大排序二叉树,是指在所有由单位三角形组成的排序二叉树中节点最多的一棵树.对于任一单位三角形,可选它三个相邻的单位三角形中任意一个作为父节点,其余两个分别作为左孩子和右孩子。当然,做根节点的单位三角形不需要父节点,而左孩子和右孩于对于二叉树中的任意节点来说并不是都必须的。

    输入输出格式

    输入格式:

    第一行是一个整数n(1<=n<=18),随后的4n^2个数,依次为三棱锥四个面上所填的数字。

    输出格式:

    仅包含一个整数,表示最大的排序二又树所含的节点数目。

    输入输出样例

    输入样例#1: 复制
    3 22 13 9
    19 25 15 1
    33 20 26 28
    32 21 18 7
    31 12 17 2
    29 24 8 6
    3 23 16 36
    5 34 27
    4 35 11
    30 14 10
    
    输出样例#1: 复制
    17
    

    说明

    输入文件解释

    A

    B

    C

    D

    输出样例文件对应的最大排序二叉树如下图所示:

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