Dotcpp > 试卷列表 > （笛卡尔树）对于一个给定的两两不等的正整数序列，

（笛卡尔树）对于一个给定的两两不等的正整数序列，

"NOIP真题" 试卷中 NOIP第十七届全国青少年信息学奥林匹克联赛初赛试题[2011提高组] 中有题目如下：

（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树。首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父结点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列 7、2 、12 、1、10 、5、15 、3 ，下图就是一棵对应的笛卡尔树。现输入序列的规模 n（1<=n<100 ）和序列的 n 个元素，试求对应的笛卡尔树的深度 d（根节点深度为 1），以及有多少个叶节点的深度为 d 。

QQ截图20210120141530.png

【程序清单】

#include <iostream>
using namespace std;
const int SIZE = 100+5;
const int INFINITY = 1000000;
int n, a[SIZE], maxDeep, num;
void solve(int left, int right, int deep){
    int i, j, min;
    if (deep > maxDeep) {
        maxDeep = deep;
        num = 1;
    }else if (deep == maxDeep)
        ①;
    min = INFINITY;
    for (i = left; i <= right; i++)
        if (min > a[i]) {
            min = a[i];
            ②;
        }
    if(left < j)③;
    if(j < right)④;
}
int main(){
    int i;
    cin>>n;
    for (i = 1; i <= n; i++)
        cin>>a[i];
    maxDeep = 0;
    solve(1, n, 1);
    cout<<maxDeep<<' '<<num<<endl;
    return 0;
}

共 12 分　

所属试卷：NOIP第十七届全国青少年信息学奥林匹克联赛初赛试题[2011提高组]

其它题目

下列程序的执行结果是（递归函数fun相关程序）

编写代码，获得用户输入的一个字符串，将其以逗号分隔输出

有以下程序段：已知字符a的ASCII码十进制值为97，

以下程序的主函数中调用了在其前面定义的函数则以下选项中

Python标准库os中的方法startfile可

下面程序的运行结果是_________。

字符串“ab\n\012\\\"”的长度是______

若有定义int b=7;float a=2.5;c=4

利用管道技术统计当前目录下有多少个文件，该命令是___

设定限制用户使用磁盘空间的命令是（）。

将/home/stud1/wang目录做归档压缩，压缩

MYSQL查询语句中用inner join(join)

在客户/服务器结构中，应用程序运行在。

如果一个关系中每个属性都是不可再分的，则该关系属于__

在INSERT触发器中，可以引用一个名为 ______

已知L是带头结点的单链表，且P结点既不是首元结点，也不

以下语句错误的是( )

某网络拓扑如题 47 图所示，其中 R 为路由器，主机

对含有600个元素的有序顺序表进行折半查找，关键字之间

假设输入的 n 为不大于 100 的正整数，k 为不小

设有以下结构类型说明和变量定义，则变量b在内存所占字节

有如下程序：运营时，若输入1 2 3 4 5 0<回车

输出的第二行一定是由小写字母、大写字母、数字和“+”、

对于入栈顺序为a,b,c,d,e的序列，下列（）不是

以下程序用来统计文件中字符的个数（函数feof用以检查

以下选项中合法的变量是

若某算法的计算时间表示为递推关系式：T(N)=2T(N

输入：5输出：（）

（哥德巴赫猜想）哥德巴赫猜想是指，任一大于 2 的偶

地面上有标号为 A、B、C 的3 根细柱，在 A 柱上

更多选择题

更多填空题

题量:	0 道
总分:	分

（笛卡尔树）对于一个给定的两两不等的正整数序列，

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

（笛卡尔树 ）对于一个给定的两两不等的正整数序列，

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

（笛卡尔树）对于一个给定的两两不等的正整数序列，