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普及组]

其它题目

下面不属于C++的预定义的流对象是

下列关于函数模板的描述中，错误的是

如果表达式a>b中的“>”是作为非成员函数重载的运算符

在匹配器（Matcher）类中，用于输入字符串与模式串

输入一段中文文本，不含标点符号和空格，保存为变量 s，

给定程序MODI1.C中函数fun的功能：先将s所指字

算法的空间复杂度是指（）。

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

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

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

表达式'He11o wor1d!'［-4:]的值为__

表达式 'C:\\Windows\\notepad.e

以下代码的输出结果是（）。

Python标准库os.path中用来判断指定路径是否

在C语言源程序中，一个变量代表___________。

有以下程序，程序中库函数islower （ch）用以判

Linux内核主要由哪几部分组成？每部分的作用？参考答

要使得名为fido的文件具有如下权限-r-xr-x—x

哪一条命令用来装载所有在 /etc/fstab 中定义

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

MySQL创建存储过程时 _____表示输入类型参数。

视图定义时algorithm参数值为 _____ 表示

（7 分）下表给出了整型信号量 S 的 wait和

若输入的字符串长度为( )，那么输入的字符串跟输出的字

（交朋友）根据社会学研究表明，人们都喜欢找和自己身高相

输出：（）

在8位二进制补码中，10101011表示的数是十进制下

FTP 可以用于（）。

输入： 10 20输出： _________

更多选择题

更多填空题

题量:	0 道
总分:	分

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷