万卷网

NOIP提高组

万卷网> 考级竞赛> 信息学奥赛> NOIP提高组

NOIP提高组

更新时间： 2023-09-02 20:23:05 试题数量： 316

我的练习

顺序练习

随机练习

章节练习

错题练习

题库预览

简答题乌龟棋【问题描述】小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行 N 个格子，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中 M 张爬行卡片，分成 4 种不同的类型（M 张卡片中不一定包含所有 4 种类型的卡片，见样例），每种类型的卡片上分别标有 1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？【输入】输入文件名 tortoise.in。输入文件的每行中两个数之间用一个空格隔开。第 1 行 2 个正整数 N 和 M，分别表示棋盘格子数和爬行卡片数。第 2 行 N 个非负整数，a1, a2, ……, aN，其中 ai 表示棋盘第 i 个格子上的分数。第 3 行 M 个整数，b1,b2, ……, bM，表示 M 张爬行卡片上的数字。输入数据保证到达终点时刚好用光 M 张爬行卡片，即【输出】输出文件名 tortoise.out。输出只有 1 行，1 个整数，表示小明最多能得到的分数。【输入输出样例 1】【输入输出样例 1 说明】小明使用爬行卡片顺序为 1，1，3，1，2，得到的分数为 6+10+14+8+18+17=73。注意，由于起点是 1，所以自动获得第 1 格的分数 6。【输入输出样例 2】【数据范围】对于 30%的数据有 1 ≤ N ≤ 30，1 ≤ M ≤ 12。对于 50%的数据有 1 ≤ N ≤ 120，1 ≤ M ≤ 50，且 4 种爬行卡片，每种卡片的张数不会超过 20。对于 100%的数据有 1 ≤ N ≤ 350，1 ≤ M ≤ 120，且 4 种爬行卡片，每种卡片的张数不会超过 40；0 ≤ ai ≤ 100，1 ≤ i ≤ N；1 ≤ bi ≤ 4，1 ≤ i ≤ M。输入数据保证

简答题观光公交【问题描述】风景迷人的小城 Y 市，拥有 n 个美丽的景点。由于慕名而来的游客越来越多，Y 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1号景点，随后依次前往 2、3、4……n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。任意时刻，公交车只能往前开，或在景点处等待。设共有 m 个游客，每位游客需要乘车 1 次从一个景点到达另一个景点，第 i 位游客在Ti 分钟来到景点 Ai，希望乘车前往景点 Bi（Ai<Bi）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 k 个氮气加速器，每使用一个加速器，可以使其中一个 Di 减 1。对于同一个 Di 可以重复使用加速器，但是必须保证使用后 Di 大于等于 0。那么 ZZ 该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？【输入】输入文件名为 bus.in。第 1 行是 3 个整数 n, m, k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。第 2 行是 n-1 个整数，每两个整数之间用一个空格隔开，第 i 个数表示从第 i 个景点开往第 i+1 个景点所需要的时间，即 Di。第 3 行至 m+2 行每行 3 个整数 Ti, Ai, Bi，每两个整数之间用一个空格隔开。第 i+2 行表示第 i 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。【输出】输出文件名为 bus.out。共一行，包含一个整数，表示最小的总旅行时间。【输入输出样例】【输入输出样例说明】对 D2 使用 2 个加速器，从 2 号景点到 3 号景点时间变为 2 分钟。公交车在第 1 分钟从 1 号景点出发，第 2 分钟到达 2 号景点，第 5 分钟从 2 号景点出发，第 7 分钟到达 3 号景点。第 1 个旅客旅行时间 7-0 = 7 分钟。第 2 个旅客旅行时间 2-1 = 1 分钟。第 3 个旅客旅行时间 7-5 = 2 分钟。总时间 7+1+2 = 10 分钟。【数据范围】对于 10%的数据，k=0；对于 20%的数据，k=1；对于 40%的数据，2 ≤ n ≤ 50，1 ≤ m ≤ 1,000，0 ≤ k ≤ 20，0 ≤ Di ≤ 10，0 ≤ Ti ≤ 500；对于 60%的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 1,000，0 ≤ k ≤ 100，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 10,000；对于 100%的数据，1 ≤ n ≤ 1,000，1 ≤ m ≤ 10,000，0 ≤ k ≤ 100,000，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 100,000。

简答题聪明的质监员【问题描述】小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1到 n 逐一编号，每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是：1、给定 m 个区间[Li，Ri]；2、选出一个参数 W；3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值 Yi ：这批矿产的检验结果 Y 为各个区间的检验值之和。即：若这批矿产的检验结果与所给标准值 S 相差太多，就需要再去检验另一批矿产。小 T不想费时间去检验另一批矿产，所以他想通过调整参数 W 的值，让检验结果尽可能的靠近标准值 S，即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。【输入】输入文件 qc.in。第一行包含三个整数 n，m，S，分别表示矿石的个数、区间的个数和标准值。接下来的 n 行，每行 2 个整数，中间用空格隔开，第 i+1 行表示 i 号矿石的重量 wi 和价值 vi 。接下来的 m 行，表示区间，每行 2 个整数，中间用空格隔开，第 i+n+1 行表示区间[Li, Ri]的两个端点 Li 和 Ri。注意：不同区间可能重合或相互重叠。【输出】输出文件名为 qc.out。输出只有一行，包含一个整数，表示所求的最小值。【输入输出样例】【输入输出样例说明】当 W 选 4 的时候，三个区间上检验值分别为 20、5、0，这批矿产的检验结果为 25，此时与标准值 S 相差最小为 10。【数据范围】对于 10%的数据，有 1≤n，m≤10；对于 30%的数据，有 1≤n，m≤500；对于 50%的数据，有 1≤n，m≤5,000；对于 70%的数据，有 1≤n，m≤10,000；对于 100%的数据，有 1≤n，m≤200,000，0 < wi, vi≤10^6，0 < S≤10^12，1≤Li≤Ri≤n。

简答题疫情控制【问题描述】H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树，1 号城市是首都，也是树中的根节点。H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。【输入】输入文件名为 blockade.in。第一行一个整数 n，表示城市个数。接下来的 n-1 行，每行 3 个整数，u、v、w，每两个整数之间用一个空格隔开，表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。接下来一行一个整数 m，表示军队个数。接下来一行 m 个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎的城市的编号。【输出】输出文件为 blockade.out。共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。【输入输出样例】【输入输出样例说明】第一支军队在 2 号点设立检查点，第二支军队从 2 号点移动到 3 号点设立检查点，所需时间为 3 个小时。【数据范围】保证军队不会驻扎在首都。

简答题引水入城【问题描述】在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 N 行 M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第 1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第 N 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。【输入】输入文件名为 flow.in。输入文件的每行中两个数之间用一个空格隔开。输入的第一行是两个正整数 N 和 M，表示矩形的规模。接下来 N 行，每行 M 个正整数，依次代表每座城市的海拔高度。【输出】输出文件名为 flow.out。输出有两行。如果能满足要求，输出的第一行是整数 1，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数 0，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。【输入输出样例 1】【样例 1 说明】只需要在海拔为 9 的那座城市中建造蓄水厂，即可满足要求。【输入输出样例 2】【样例 2 说明】上图中，在 3 个粗线框出的城市中建造蓄水厂，可以满足要求。以这 3 个蓄水厂为源头在干旱区中建造的输水站分别用 3 种颜色标出。当然，建造方法可能不唯一。【数据范围】本题共有 10 个测试数据，每个数据的范围如下表所示：对于所有的 10 个数据，每座城市的海拔高度都不超过

简答题计算系数【问题描述】给定一个多项式请求出多项式展开后项的系数。【输入】输入文件名为 factor.in。共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。【输出】输出文件名为 factor.out。输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10007 取模后的结果。【输入输出样例】【数据范围】对于 30%的数据，有 0≤k≤10；对于 50%的数据，有 a = 1，b = 1；对于 100%的数据，有 0≤k≤1,000，0≤n, m≤k，且 n + m = k，0≤a，b≤1,000,000。

简答题机器翻译【问题描述】小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M−1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。假设一篇英语文章的长度为 N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。【输入】输入文件名为 translate.in，输入文件共 2 行。每行中两个数之间用一个空格隔开。第一行为两个正整数 M 和 N，代表内存容量和文章的长度。第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。【输出】输出文件 translate.out 共 1 行，包含一个整数，为软件需要查词典的次数。【输入输出样例 1】【输入输出样例 1 说明】整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：空：内存初始状态为空。1． 1：查找单词 1 并调入内存。2． 1 2：查找单词 2 并调入内存。3． 1 2：在内存中找到单词 1。4． 1 2 5：查找单词 5 并调入内存。5． 2 5 4：查找单词 4 并调入内存替代单词 1。6． 2 5 4：在内存中找到单词 4。7． 5 4 1：查找单词 1 并调入内存替代单词 2。共计查了 5 次词典。【输入输出样例 2】【数据范围】对于 10%的数据有 M=1，N ≤ 5。对于 100%的数据有 0<M ≤ 100，0<N ≤ 1000。

简答题同余方程【问题描述】求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。【输入】输入文件为 mod.in。输入只有一行，包含两个正整数 a, b，用一个空格隔开。【输出】输出文件为 mod.out。输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。【输入输出样例】【数据范围】对于 40%的数据，2 ≤b≤ 1,000；对于 60%的数据，2 ≤b≤ 50,000,000；对于 100%的数据，2 ≤a, b≤ 2,000,000,000。

简答题开车旅行【问题描述】小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 1 到 N 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i 的海拔高度为Hi，城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i, j] = |Hi − Hj|。旅行过程中，小 A 和小 B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划选择一个城市 S 作为起点，一直向东行驶，并且最多行驶 X 公里就结束旅行。小 A 和小 B的驾驶风格不同，小 B 总是沿着前进方向选择一个最近的城市作为目的地，而小 A 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 X 公里，他们就会结束旅行。在启程之前，小 A 想知道两个问题：1．对于一个给定的 X=X0，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。2. 对任意给定的 X=Xi和出发城市 Si，小 A 开车行驶的路程总数以及小 B 行驶的路程总数。【输入】输入文件为 drive.in。第一行包含一个整数 N，表示城市的数目。第二行有 N 个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 N 的海拔高度，即 H1，H2，……，Hn，且每个 Hi都是不同的。第三行包含一个整数 X0。第四行为一个整数 M，表示给定 M 组 Si和 Xi。接下来的 M 行，每行包含 2 个整数 Si和 Xi，表示从城市 Si出发，最多行驶 Xi公里。【输出】输出文件为 drive.out。输出共 M+1 行。第一行包含一个整数 S0，表示对于给定的 X0，从编号为 S0 的城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。接下来的 M 行，每行包含 2 个整数，之间用一个空格隔开，依次表示在给定的 Si 和Xi下小 A 行驶的里程总数和小 B 行驶的里程总数。【输入输出样例 1】【输入输出样例 1 说明】各个城市的海拔高度以及两个城市间的距离如上图所示。如果从城市 1 出发，可以到达的城市为 2,3,4，这几个城市与城市 1 的距离分别为 1,1,2，但是由于城市 3 的海拔高度低于城市 2，所以我们认为城市 3 离城市 1 最近，城市 2 离城市1 第二近，所以小 A 会走到城市 2。到达城市 2 后，前面可以到达的城市为 3,4，这两个城市与城市 2 的距离分别为 2,1，所以城市 4 离城市 2 最近，因此小 B 会走到城市 4。到达城市 4 后，前面已没有可到达的城市，所以旅行结束。如果从城市 2 出发，可以到达的城市为 3,4，这两个城市与城市 2 的距离分别为 2,1，由于城市 3 离城市 2 第二近，所以小 A 会走到城市 3。到达城市 3 后，前面尚未旅行的城市为4，所以城市 4 离城市 3 最近，但是如果要到达城市 4，则总路程为 2+3=5>3，所以小 B 会直接在城市 3 结束旅行。如果从城市 3 出发，可以到达的城市为 4，由于没有离城市 3 第二近的城市，因此旅行还未开始就结束了。如果从城市 4 出发，没有可以到达的城市，因此旅行还未开始就结束了。【输入输出样例 2】【输入输出样例 2 说明】当 X=7 时，如果从城市 1 出发，则路线为 1 -> 2 -> 3 -> 8 -> 9，小 A 走的距离为 1+2=3，小 B 走的距离为 1+1=2。（在城市 1 时，距离小 A 最近的城市是 2 和 6，但是城市 2 的海拔更高，视为与城市 1 第二近的城市，所以小 A 最终选择城市 2；走到 9 后，小 A 只有城市 10 可以走，没有第 2 选择可以选，所以没法做出选择，结束旅行）如果从城市 2 出发，则路线为 2 -> 6 -> 7 ，小 A 和小 B 走的距离分别为 2，4。如果从城市 3 出发，则路线为 3 -> 8 -> 9，小 A 和小 B 走的距离分别为 2，1。如果从城市 4 出发，则路线为 4 -> 6 -> 7，小 A 和小 B 走的距离分别为 2，4。如果从城市 5 出发，则路线为 5 -> 7 -> 8 ，小 A 和小 B 走的距离分别为 5，1。如果从城市 6 出发，则路线为 6 -> 8 -> 9，小 A 和小 B 走的距离分别为 5，1。如果从城市 7 出发，则路线为 7 -> 9 -> 10，小 A 和小 B 走的距离分别为 2，1。如果从城市 8 出发，则路线为 8 -> 10，小 A 和小 B 走的距离分别为 2，0。如果从城市 9 出发，则路线为 9，小 A 和小 B 走的距离分别为 0，0（旅行一开始就结束了）。如果从城市 10 出发，则路线为 10，小 A 和小 B 走的距离分别为 0，0。从城市 2 或者城市 4 出发小 A 行驶的路程总数与小 B 行驶的路程总数的比值都最小，但是城市 2 的海拔更高，所以输出第一行为 2。【数据范围】对于 30%的数据，有 1≤N≤20，1≤M≤20；对于 40%的数据，有 1≤N≤100，1≤M≤100；对于 50%的数据，有 1≤N≤100，1≤M≤1,000；对于 70%的数据，有 1≤N≤1,000，1≤M≤10,000；对于 100%的数据，有 1≤N≤100,000，1≤M≤10,000，-1,000,000,000≤Hi≤1,000,000,000，0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，数据保证 Hi互不相同。

简答题铺地毯【问题描述】为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。【输入】输入文件名为 carpet.in。输入共 n+2 行。第一行，一个整数 n，表示总共有 n 张地毯。接下来的 n 行中，第 i+1 行表示编号 i 的地毯的信息，包含四个正整数 a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在 x轴和 y 轴方向的长度。第 n+2 行包含两个正整数 x 和 y，表示所求的地面的点的坐标（x，y）。【输出】输出文件名为 carpet.out。输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。【输入输出样例 1】【输入输出样例说明】如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2，2）的最上面一张地毯是 3 号地毯。【输入输出样例 2】【输入输出样例说明】如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5）没有被地毯覆盖，所以输出-1。【数据范围】对于 30%的数据，有 n≤2；对于 50%的数据，0≤a, b, g, k≤100；对于 100%的数据，有 0≤n≤10,000，0≤a, b, g, k≤100,000。

简答题关押罪犯【问题描述】S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？【输入】输入文件名为 prison.in。输入文件的每行中两个数之间用一个空格隔开。第一行为两个正整数 N 和 M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 M 行每行为三个正整数 aj，bj，cj，表示 aj号和 bj号罪犯之间存在仇恨，其怨气值为 cj。数据保证1 ≤ a j < bj ≤ N ，0 < c j ≤ 1,000,000,000 ，且每对罪犯组合只出现一次。【输出】输出文件 prison.out 共 1 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。【输入输出样例】【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 3512（由 2 号和 3 号罪犯引发）。其他任何分法都不会比这个分法更优。【数据范围】对于 30%的数据有 N ≤ 15。对于 70%的数据有 N ≤ 2000，M ≤ 50000。对于 100%的数据有 N ≤ 20000，M ≤ 100000。

简答题借教室【问题描述】在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj, sj,tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj个教室。我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。【输入】输入文件为 classroom.in。第一行包含两个正整数n, m，表示天数和订单的数量。第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。接下来有m行，每行包含三个正整数dj, sj,tj，表示租借的数量，租借开始、结束分别在第几天。每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。【输出】输出文件为 classroom.out。如果所有订单均可满足，则输出只有一行，包含一个整数 0。否则（订单无法完全满足）输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。【输入输出样例】【输入输出样例说明】第 1 份订单满足后，4 天剩余的教室数分别为 0，3，2，3。第 2 份订单要求第 2 天到第 4 天每天提供 3 个教室，而第 3 天剩余的教室数为 2，因此无法满足。分配停止，通知第2 个申请人修改订单。【数据范围】

简答题 Mayan 游戏【问题描述】Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 7 行 5 列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：1、每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图 6 到图 7）；如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图 1 和图 2）；2、任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除（参见图 1 到图 3）。注意：a) 如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图 4，三个颜色为 1 的方块和三个颜色为 2 的方块会同时被消除，最后剩下一个颜色为 2 的方块）。b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除（例如下面图 5 所示的情形，5 个方块会同时被消除）。 3、方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的过程中将不会有方块的消除。上面图 1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为（0, 0），将位于（3, 3）的方块向左移动之后，游戏界面从图 1 变成图 2 所示的状态，此时在一竖列上有连续三块颜色为 4 的方块，满足消除条件，消除连续 3 块颜色为 4 的方块后，上方的颜色为 3 的方块掉落，形成图 3 所示的局面。【输入】输入文件 mayan.in，共 6 行。第一行为一个正整数 n，表示要求游戏通关的步数。接下来的 5 行，描述 7*5 的游戏界面。每行若干个整数，每两个整数之间用一个空格隔开，每行以一个 0 结束，自下向上表示每竖列方块的颜色编号（颜色不多于 10 种，从 1 开始顺序编号，相同数字表示相同颜色）。输入数据保证初始棋盘中没有可以消除的方块。【输出】输出文件名为 mayan.out。如果有解决方案，输出 n 行，每行包含 3 个整数 x，y，g，表示一次移动，每两个整数之间用一个空格隔开，其中（x，y）表示要移动的方块的坐标，g 表示移动的方向，1 表示向右移动，-1 表示向左移动。注意：多组解时，按照 x 为第一关健字，y 为第二关健字，1优先于-1，给出一组字典序最小的解。游戏界面左下角的坐标为（0，0）。如果没有解决方案，输出一行，包含一个整数-1。【输入输出样例 1】【输入输出样例说明】按箭头方向的顺序分别为图 6 到图 11 样例输入的游戏局面如上面第一个图片所示，依次移动的三步是：（2，1）处的方格向右移动，（3，1）处的方格向右移动，（3，0）处的方格向右移动，最后可以将棋盘上所有方块消除。【数据范围】对于 30%的数据，初始棋盘上的方块都在棋盘的最下面一行；对于 100%的数据，0 < n≤5。

简答题国王游戏【问题描述】恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。【输入】输入文件为 game.in。第一行包含一个整数 n，表示大臣的人数。第二行包含两个整数 a 和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。【输出】输出文件名为 game.out。输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。【输入输出样例】【输入输出样例说明】按 1、2、3 号大臣这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；按 1、3、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；按 2、1、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；按 2、3、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9；按 3、1、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；按 3、2、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9。因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。【数据范围】对于 20%的数据，有 1≤ n≤ 10，0 < a、b < 8；对于 40%的数据，有 1≤ n≤20，0 < a、b < 8；对于 60%的数据，有 1≤ n≤100；对于 60%的数据，保证答案不超过对于 100%的数据，有 1 ≤ n ≤1,000，0 < a、b < 10000。

简答题选择客栈【问题描述】丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p。他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p元的咖啡店小聚。【输入】输入文件 hotel.in，共 n+1 行。第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；接下来的 n 行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。【输出】输出文件名为 hotel.out。输出只有一行，一个整数，表示可选的住宿方案的总数。【输入输出样例 1】【输入输出样例说明】2 人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤，但是若选择住 4、5 号客栈的话，4、5 号客栈之间的咖啡店的最低消费是 4，而两人能承受的最低消费是 3 元，所以不满足要求。因此只有前 3 种方案可选。【数据范围】对于 30%的数据，有 n≤100；对于 50%的数据，有 n≤1,000；对于 100%的数据，有 2≤n≤200,000，0<k≤50，0≤p≤100， 0≤最低消费≤100。