/ Vijos / 题库 /

学姐吃牛排

学姐吃牛排

描述

学姐今晚想吃牛排, doc便领着她去吃啦. 但是怎么能这样轻易就让馋嘴的学姐吃到牛排呢!

图片

doc决定在纸上画一颗完全二叉树, 然后询问学姐:"这是不是一个堆(Heap)呀? 这是不是一个二叉排序树(BST)呀?"
如果学姐答对了, doc就会喂她吃一小块牛排呢!

格式

输入格式

第一行一个整数T, 表示总的询问次数.
之后有T次询问, 对于每一次询问, 第一行有一个整数N, 表示给定的完全二叉树中的结点个数, 之后一行给出了一组[1..N]的排列A[1],...,A[N], 依次表示树上每一个结点i的权值.
我们假定下标i所对应的结点为根, 其左右子结点的下标分别为2i和2i+1.

输出格式

对于每一次询问, 输出一行.
首先输出询问的标号(参见样例输出), 之后输出"Both", "Heap", "BST", "Neither"中的某一个, 表示给定的完全二叉树"既是堆也是二叉排序树", "只是堆", "只是二叉排序树", "什么也不是".
这里需要注意: 大根堆小根堆都是堆, 按照升序按照降序得到的二叉排序树都是二叉排序树.

样例1

样例输入1

4
4
2 1 3 4 
3
2 1 3
3
1 2 3
1
1

样例输出1

Case #1: Neither
Case #2: BST
Case #3: Heap
Case #4: Both

限制

对于40%的数据, N <= 20
对于100%的数据, 1 <= N <= 1000, T <= 100

信息

ID
1897
难度
7
分类
(无)
标签
(无)
递交数
1233
已通过
215
通过率
17%
被复制
4
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

NOIP模拟赛 之 周五的夜晚