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提高组]

其它题目

函数swap（a，n）可完成对a数组从第1个元素到第n

对于int *pa[5];的描述，正确的是。

人员的记录由编号和出生年、月、日组成，N名人员的数据已

有以下定义和语句：能给w中year成员赋1980的语句

下面关于编译预处理的命令行，正确的是（）。

有以下程序程序运行后，若从键盘输入（从第1列开始）12

有以下程序程序的输出结果是。

对于一个正常运行的C程序，以下叙述中正确的是。

表达式'%s'%65==str(65)的值为_____

已知x={1:1，2:2}，那么执行语句x[2]=4之

表达式int('11'，8)的值为__________

Python标准库math中用来计算平方根的函数是__

有以下程序程序的运行结果是（）。

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

下列属于星形拓扑的优点的是（）

若信道在无噪声情况下的极限数据传输速率不小于信噪比为3

某计算机采用页式虚拟存储管理方式，按字节编址。CPU进

Linux系统有几种类型文件？它们分别是什么？有哪些相

设有两个C语言程序模块c1.c和c2.c（不含main

Linux操作系统中，当我们输入sudo 以提升权限时

功能：求给定正整数m以内的素数之和。例如：当m=20时

功能：根据整型形参m，计算如下公式的值：y=sin(m

设有以下共用体类型说明和变量定义，则变量d在内存所占字

以下叙述中正确的

下列叙述中正确的是

由四个没有区别的点构成的简单无向连通图的个数是（）。

. 以比较作为基本运算，在 N 个数中找最小数的最少

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

输入：114 5 6 6 4 3 3 2 3 2 1输

输入： 10 20输出： _________

更多选择题

更多填空题

题量:	0 道
总分:	分

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

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