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

其它题目

2023 年 10 月 26 日，神舟十七号载人飞船发

下列选项中，不属于模块间耦合的是（）。

下面不属于软件设计阶段任务的是（）。

有以下程序：程序运行后的输出结果是（）。

程序阅读题1、2、#include<iostream.

下面程序中A是抽象类。请在下面程序的横线处填上适当内容

在c++中，只能重载已有的运算符。

Python 3.x语句for i in range

以下程序时应用递归算法求某数a的平方根，请填空，求平方

在Internet上浏览时，浏览器和WWW服务器之间传

linux文件系统中每个文件用________来标识

链接分为：硬链接和（）。

VIM文件编辑器的输入模式下，按什么键可以进入底行模式

Linux在命令后面加上什么符号，会将命令放在后台运行

关系中外码的值必须取空值，或等于被参照关系中某个元组的

要保证数据库的逻辑独立性，需要修改的是（）。

路由器运行于OSI模型的

下列关于虚电路网络的叙述中，错误的是

表达式a+=b相当于表达式_____。

以下程序段要求从键盘输入字符，当输入字母为'Y' 时，

若a是int型变量，则计算表达式a=25/3%3后a的

若s是int型变量，且s=6，则下面表达式的值是___

函数fun的功能是：判断整数n是否是“完数”。当一

（最优子序列）取 m = 16，给出长度为 n 的整数

假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，

输入 :3AB:ACDEbFBkBDAR:ACDBrT

如果开始时计算机处于小写输入状态，现在有一只小老鼠反复

以下是面向对象的高级语言的是( )。

输入： 66553输出： ______________

BIOS（基本输入输出系统）是一组固化在计算机内（）

更多选择题

更多填空题

题量:	0 道
总分:	分

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

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