Dotcpp > 试卷列表 > 对于一个 1到n 的排列 P（即 1到 n中每一个数在

对于一个 1到n 的排列 P（即 1到 n中每一个数在

"NOIP真题" 试卷中 NOIP第二十四届全国青少年信息学奥林匹克联赛初赛试题[2018普及组] 中有题目如下：

对于一个 1 到 n 的排列 P（即 1 到 n 中每一个数在 P 中出现了恰好一次），令 qi 为第 i 个位置之后第一个比 Pi 值更大的位置，如果不存在这样的位置，则 qi=n+1。举例来说，如果n=5 且 P 为 15423，则 q 为 2, 6, 6, 5, 6

下列程序读入了排列 P，使用双向链表求解了答案。试补全程序。

数据范围 1≤n≤10⁵。

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        ① ;
    }
    for (int i = 1; i <= n; ++i) {
        R[i] = ② ;
        L[i] = i - 1;
    }
    for (int i = 1; i <= n; ++i) {
        L[ ③ ] = L[a[i]];
        R[L[a[i]]] = R[ ④ ];
    }
    for (int i = 1; i <= n; ++i) {
        cout << ⑤ << " ";
    }
    cout << endl;
    return 0;
}

共 14 分　

所属试卷：NOIP第二十四届全国青少年信息学奥林匹克联赛初赛试题[2018普及组]

其它题目

语句ofstream f("SALARY.DAT",

下列转义字符能够实现换行的是（）。

在学校中，“班级”与“学生”两个实体集之间的联系属于

给定程序MODI1.C中函数fun的功能是：判断一个整

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

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

请在下面程序的横线处填上适当内容，以使程序完整,并使运

请在下面程序的横线处填上适当内容，以使程序完整,并使程

已知 x=[3,5,7]，那么执行语句x[:3]= [

表达式list(filter(lambda x:x>5

输出的结果是（）。

有如下数学公式：已知梯形法求积分公式为：（其中n为积分

在一个C源程序文件中，若要定义一个只允许本源文件中所有

以下printf语句中的负号的作用是_________

ss命令执行速度比netstat快，因为ss直接使用T

数据库的三级模式之间存在着两级映像，使得数据库系统具有

数据管理技术发展过程中,（）不是文件系统阶段的特点。

以下哪项用于左连接( )

软件测试的方法有和 (即黑盒法)。

(7分)采用swap 指今实现进程互斥。lock为TR

预处理命令行都必须以_____号开始。

设a，b，t为整型变量，初值为a=7，b=9，执行完语

x*=y+8等价于x=x*(y+8)。

下面函数的功能是。

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

编写一个函数proc，从传入的M个字符中找出最长的一个

下列四个不同进制的数中，与其它三项数值上不相等的是（

重新排列 1234 使得每一个数字都不在原来的位置上，

（数字删除）下面程序的功能是将字符串中的数字字符删除后

拓扑排序是指将有向无环图 G中的所有顶点排成一个线性

更多选择题

更多填空题

题量:	0 道
总分:	分

对于一个 1到n 的排列 P（即 1到 n中每一个数在

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

对于一个 1到n 的排列 P（即 1到 n中每一个数在

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷