NOIP 模拟试题 by yali middle school第 1 页 共 5 页模拟一序列(sequence.exe)问题描述有一个非递减的整数序列 S1，S 2，S 3，S n+1（S i_=1）【输出】输出仅一个数，即最少工作时间。【样例输入】315 0 2550 0 9045 15 70【样例输出】50【数据范围】Ti=1，01，n0；50%的数据满足 n=0，y=2；)()2(1yxxXY那么原题即求 mmn )1(0容易证明： )()(11yxyxXy则NOIP 模拟试题 by yali middle school第 15 页 共 5 页)0()1 )1()01()01()1 ()11() m mmmmn n根据上式直接高精度计算即可。NOIP 模拟试题 by yali middle school第 16 页 共 5 页模拟三一、任务分配图书馆按顺序排列有 N 本书需要维护，每本书的总页数不相同。现有 M 位员工。可以给每个员工分配连续的一段书籍，让他进行维护。现在的问题是，怎么样分配，工作任务最重（需要维护的页数最多）的人维护的页数尽量少。 输入：第一行两个数，N、M。接下来 N 行，每行一个整数，表示一本书的页数。输出：任务最重的人最少需要维护的页数。样例：book.in5 332415book.out5数据范围：Naj，那么我们称之为逆序对，求逆序对的数目输入：第一行为 n,表示序列长度，接下来的 n 行，第 i+1 行表示序列中的第 i 个数。输出：所有逆序对总数.样例：deseq. in43232deseq.out3数据范围：N1 的宫殿，均可以将其化分为 4 个 k/2 大小的宫殿，先看一下公主站的位置是属于哪一块，因为根据公主所在的位置，我们可以确定中间位置所放的毯子类型，再递归处理公主所站的那一块，直到出现边界条件 k1 的情况，然后在公主边上铺上一块合适的地毯，递归结束。由于要递归到每一格，复杂度就是面积，就是 O(22*k*k)。4 K-联赛【算法分析】看一个队是否有希望夺冠，首先，这个队此后的比赛自然是赢越多越好，所以先让这个队把以后的比赛都赢下来，算出这个队最高能拿多少分。下面关键就看是否有可能让其他队的积分都低于刚才计算出的最高分。建立一个网络，所有的球队作为图中的节点，每两个队之间的比赛也作为图中的节点。从网络的源各连一条边到“比赛的节点” ，容量为两队间还剩的比赛场数。从“每个队的节点”都连一条边到网络的汇，容量为这个队当前的积分与最高分之差。如果一个“比赛的节点”代表的是 A 与 B 之间的比赛，那么从这个节点连两条边分别到“A 队的节点”和“B 队的节点” ，容量为无穷大。如果这个网络的最大流等于所有还未进行的比赛的场次之和，那么需要我们判断的那个队抗有可能夺得冠军。本题要我们找出所有可能夺冠的队，那么只需枚举所有的球队，判断它们是否有可能夺冠即可。5 小木棍【问题分析】搜索的顺序是枚举原始木棍的长度，从小到大或从大到小均可。但注意从大到小枚举的时候，可以剪枝，如果长度为 kL 的原始木棍尝试失败的话，长度为 L 的就不必尝试了，因为必然也是失败的。得到了原始木棍的长度后，一个一个的去枚举拼它的方案。注意，枚举要按字典序，举个例子说，就是不允许出现第一个木棍是由第 2、5、6 个小木棍拼成，而第二个木棍是由第 1、3、4 个小木棍拼成（2、5、6 的字典序大于 1、3、4） 。枚举的过程中，有一个比较强的剪枝：如果放入一个长度为 len 的小木棍后，正好拼成了一个原始长度的木棍，但是拼后面的木棍失败，那么就没有必要再枚举比 len 短的木棍了。因为一段整空间被一个刚好长度的木棍去填总是不亏的。 （为方便起见，可以事先将小木棍降序排列）NOIP 模拟试题 by yali middle school第 32 页 共 5 页6 平板涂色【问题分析】指数型动态规划。由于 N 小于 16，故可以以一个 N-bit 的二进制数 A 作为状态，其中每个二进制位表示一个格子的涂色情况，二进制位 0 表示该格子未被涂色，二进制 1 表示该格子已被涂色。用 FA表示要得到状态 A，最少需要改变多少次颜色。对于每个状态 A，通过枚举涂色方案来推新的状态。NOIP 模拟试题 by yali middle school第 33 页 共 5 页模拟六1 单向双轨道源程序名 track.?（pas, c, cpp）可执行文件名 track.exe输入文件名 track.in输出文件名 track.out【问题描述】如图所示 l，某火车站有 B，C 两个调度站，左边入口 A 处有 n 辆火车等待进站(从左到右以 a、b、c 、d 编号)，右边是出口 D，规定在这一段，火车从 A 进入经过 B、C 只能从左向右单向开，并且 B、C 调度站不限定所能停放的车辆数。从文件输入 n 及 n 个小写字母的一个排列，该排列表示火车在出口 D 处形成的从左到右的火车编号序列。输出为一系列操作过程，每一行形如“h L R”的字母序列，其中 h 为火车编号，L 为 h 车原先所在位置(位置都以 A、B、C、D 表示)，R 为新位置。或者输出NO表示不能完成这样的调度。【输入】一个数 n(1m)，费用需 s 分(s【输入输出样例】样例 1：NOIP 模拟试题 by yali middle school第 50 页 共 5 页输入（find.in）：5 2Jason 1 1Herry 4 4Patty 3 4Tom 2 10Petter 5 10输出(find.out)：5 1Patty样例 2：输入（find.in）：6 2Jim 1 1Flord 3 3Joseph 1 1Steve 3 3Tiger 2 10User 10 20输出(find.out)：4 2FlordSteve样例二说明：jim 和 joseph 的礼品是等距的距离最短，被第一个人拿走，剩下的四个人中flord 和 steve 的礼物也是等距的计算得到距离为 4。 【数据范围】对于 30%的数据 KN1000对于所有的数据 KN100000所有的坐标绝对值小于 106NOIP 模拟试题 by yali middle school第 51 页 共 5 页打包pack.pas/pack.c/pack.cpp【问题描述】你现在拿到了许多的礼物，你要把这些礼物放进袋子里。你只有一个最多装下 V 体积物品的袋子，你不能全部放进去。你也拿不动那么重的东西。你估计你能拿的最大重量为 G。现在你了解了每一个物品的完美值、重量和体积，你当然想让袋子中装的物品的完美值总和最大，你又得计划一下了。【输入】第一行：V 和 G 表示最大重量和体积。第二行：N 表示拿到 N 件礼物。第三到 N+2 行：每行 3 个数 Ti Vi Gi 表示各礼物的完美值、重量和体积【输出】输出共一个数，表示可能获得的最大完美值。【输入输出样例】输入(pack.in)：6 5410 2 220 3 240 4 330 3 3输出(pack.out)：50【数据范围】对于 20%的数据 N，V，G，T i，V i，G i10对于 50%的数据 N，V，G，T i，V i，G i100对于 80%的数据 N，V，G，T i，V i，G i30080%到 100%的数据是 N，V，G ，T i，V i，G i380 的离散随机数据。NOIP 模拟试题 by yali middle school第 52 页 共 5 页完美交换change.pas/change.c/change.cpp【问题描述】你和你的伙伴们将礼物都装好了，你们抱着各自的礼物，想通过交换让你们总和的完美值最大。你们的 总和完美值 的计算方法是：每个人的位置*每人礼物的完美值 再求总和。我们保证每个人手上的完美值都不等。如下表：位置 1 2 3 4所拿礼物的完美值 200 400 100 430当前的 总和完美值=1*200+2*400+3*100+4*430现在你们通过两两交换，要使得最终你们的完美值为最大。如上例子：经过交换后位置 1 2 3 4所拿礼物的完美值 100 200 400 430总和完美值的最大值=1*100+2*200+3*400+4*430现在要求出最大完美值是多少。另外假设在一个时间单位内，一个人只可以做一次的交换动作（当然也可以原地不动） ，那么达到最大完美值状态的最短用时是多少。【输入】第一行：N 表示游戏人数。第 2 到 N+1 行：每行一个数 Mi，表示从位置 1 到位置 N，每个人的所拿礼物的完美值。【输出】第一行：最大完美值第二行：最小交换所需时间【输入输出样例】输入(change.in)：4200400100430输出(change.out)：34202【数据范围】对于 30%的数据 N10对于全部的数据 N10 4NOIP 模拟试题 by yali middle school第 53 页 共 5 页对于全部的数据 Mi100050NOIP 模拟试题 by yali middle school第 54 页 共 5 页老妹的难题(sister.pas/sister.c/sister.cpp)【问题描述】一进家门，你老妹给了你（的礼物） ，一个热情的拥抱，结果礼物撒落一地，你为了让你老妹弥补过失，给她出了一道题。在洒落的礼物中找出一个，使之到其他礼物的距离之和最小。由于你老妹还没学开根号，所以我们定义(x1,y1)(x2,y2)两点间的距离为：|x2-x1|+|y2-y1|你为了验证你老妹给出的答案是否正确，需要编写一个程序，来完成你老妹的任务。输出距离总和的最小值是多少。【输入】第一行：N 表示有 N 个礼物。第 2 到 N+1 行每行一个坐标（x,y）【输出】一行，距离总和的最小值【输入输出样例】输入(sister.in)：42 31 13 24 4输出(sister.out) ：8【数据范围】30%的数据 N100全部的数据 N10 5全部的数据 X i,Yi10000NOIP 模拟试题 by yali middle school第 55 页 共 5 页模拟十游戏规则(logic.pas)【问题描述】这是一个非常有趣的智力游戏，它规则简单而又变化多端。游戏在一个 m*n 的方格里进行。游戏开始时所有的格子都是白色。游戏的目标是通过给出的线索按要求选择一些方格涂黑。这些线索是写在每一行和每一列前面的一些数字，它告诉了你该行或者该列应该出现的几组黑色方格各有多