NOIP模拟测试题解析：逆序对与序列排序

"noip阶段性复习题" 这是一组针对NOIP(全国青少年信息学奥林匹克联赛)的复习题目，旨在帮助中等水平的参赛者提升编程技能和解题能力。题目集包含四道非交互性的程序设计问题，分别命名为"序列"、"悟空学艺"、"游览路线"和"外星人"，对应的输入和输出文件分别为sequence.in/sequence.out、monkey.in/monkey.out、travel.in/travel.out和et.in/et.out。每道题目的时间限制均为1秒，空间限制为64MB。 对于竞赛中的编程语言限制，有以下几点需要注意： 1. Pascal语言规定： - 如果使用Pascal编写程序，当IDE和Free Pascal Compiler (fpc)的编译结果不一致时，以fpc的编译结果为准。 - 允许使用`uses math`子句以及ansistring，但不能使用特定的编译开关，如关闭范围检查的`{$R-,Q-,S-}`，也不支持与优化相关的编译选项。 2. C++语言中的模板使用限制： - 在C++题目中，允许使用标准库的部分内容，如布尔集合、迭代器、串和流相关的头文件。 - 禁止使用一系列标准库容器和算法，包括序列容器（如vector、list、deque）、序列适配器（如stack、queue、priority_queue）、关联容器（如map、multimap、set、multiset）、拟容器（如valarray）和散列容器（如hash_map、hash_set、hash_multimap、hash_multiset）。 - 由于题目保证了数据的正确性，因此无需进行错误判断。 其中，"序列"题目具体要求参赛者计算一个数字序列的"逆序对"数量，以此来衡量序列的"混乱程度"。逆序对是指在序列中，若存在I<J且ai>aj，则<ai,aj>是一个逆序对。题目的目标是计算逆序对的数量n，并输出2^n对1991取模的结果，即Q mod 1991，以处理可能的大数值。 这四道题目不仅测试选手的基础编程能力，还考察他们对数据结构、算法的理解和应用，以及对竞赛规则的遵守。通过这样的训练，参赛者可以提升在NOIP竞赛中的竞争力。