《NOIP提高组复赛试题day1day2》由会员分享，可在线阅读，更多相关《NOIP提高组复赛试题day1day2（12页珍藏版）》请在金锄头文库上搜索。
1、全国信息学奥林匹克联赛2021复赛提高组11 .转圈游戏【问题描述】n个小伙伴编号从0到1 围坐一圈玩游戏。按照顺时针 方向给n个位置编号，从0到1。最初，第0号小伙伴在第0 号位置，第1号小伙伴在第1号位置，依此类 推。游戏规那么如下：每一轮第 0号位置上的小伙伴顺时针走到第m号位置，第1号位置小伙伴走到第1号位置，依此类推, 第n - m号位置上的小伙伴走到第 0号位置，第1号位置上的小 伙伴走到第1号位置，第1号位置上的小伙伴顺时针走到 第1号位置。现在，一共进行了 10k轮，请问x号小伙伴最后走到了第几 号位置。【输入】输入文件名为。输入共1行，包含4个整数n、m k、x,每两个整数之
2、间 用一个空格隔开。【输出】输出文件名为。输出共1行，包含1个整数，表示10k轮后x号小伙伴所在的位置编号。【输入输出样例】10 3 4 55【数据说明】对于30%的数据，0 k 7 ;对于80%的数据，0 k 10 7;对于 100%的数据，1 n 1,000,000 , 0 m n , 0 w x 9n, 0 k 10 o2 .火柴排队()【问题描述】涵涵有两盒火柴，每盒装有 n根火柴，每根火柴都有一个高 度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相 同，两列火柴之间的距离定义为：富 三式q-瓦)2,其中 表示第一列火柴中第i个火柴的高度，表示第二列火柴中第i个火柴的高度。每
3、列火柴中相邻两根火柴的位置都可以交换，请你通过交换使 得两列火柴之间的距离最 小。请问得到这个最小的距离，最少需 要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。输入文件为共三行，第一行包含一个整数 n,表示每盒中火柴的数目。第二行有n个整数，每两个整数之间用一个空格隔开，表示第 一列火柴的高度。第三行有n个整数，每两个整数之间用一个空格隔开，表示第 二列火柴的高度。【输出】输出文件为。输出共一行，包含一个整数，表示 最少交换次数对99,999,997 取模的结果。【输入输出样例1 412 3 1 43 2 1 4【输入输出样例说明】最小距离是0,最
4、少需要交换1次，比方：交换第1列的前2根火柴或者交换第2列的前2根火柴。【输入输出样例2421 3 4 21 7 2 4【输入输出样例说明】最小距离是10,最少需要交换2次，比方：交换第1列的中间2根火柴的位置，再交换第 2列中后2根火柴的位置。【数据范围】对于10%的数据,1 n 10 ;对于30%的数据，1 n 100;对于60%的数据，1 n 1,000 ;对于100%的数据，1 n 100,000 , 0 w火柴高度w 2 31 - 1。3 .货车运输()【问题描述】A国有n座城市，编号从1到n ,城市之间有 m条双向道 路。每一条道路对车辆都有重量限制，简称限重。现在有 q辆货 车在
5、运输货物，司机们想知道每辆车在不超过车辆限重的情况下， 最多能运多重的货物。【输入】输入文件名为。输入文件第一行有两个用一个空格隔开的整数n, m,表示A国有n座城市和m条道路。接下来m行每行3个整数x、y、z,每两个整数之间用一个空格 隔开，表示从x号城市到y号城市有一条限重为z的道路。注意： x不等于y,两座城市之间可能有多条道路。接下来一行有一个整数q,表示有q辆货车需要运货。接下来q行，每行两个整数x、y,之间用一个空格隔开，表示一辆货车需要从x城市 运输货物到y城市，注意：x不等于y【输出】输出文件名为。输出共有q行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能
6、到达目的地，输出 -1。【输入输出样例】4 31 2 42 3 33 1 131 31 41 33-13【数据说明】对于 30%的数据，0 n 1,000, 0 m 10,000, 0 q 1,000;对于 60%的数据，0 n 1,000, 0 m 50,000,0 q 1,000;对于 100%的数据，0 n 10,000 , 0 m 50,000 , 0 q30,000 , 0 w z 100,000 o全国信息学奥林匹克联赛(2021)复赛提高组21.积木大赛()【题目描述】春春幼儿园举办了一年一度的“积木大赛。今年比赛的内 容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积
7、木组成，第i块积木的最终高度需要是 ？i。在搭建开始之前，没有任何积木可以看成块高度为0的积木。接下来每次操作，小朋友们可以选择一段连续区间口，然后将第L块到第R块之间含第L块和第R块所有积木的高度分 别增加1。小M是个聪明的小朋友，她很快想出了建造大厦的最正确策略， 使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所 以想请你帮助实现这个策略，弁求出最少的操作次数。【输入】输入文件为输入包含两行，第一行包含一个整数n,表示大厦的宽度。第二行包含n个整数，第i个整数为？i。【输出】输出文件为仅一行，即建造所需的最少操作数。【输入输出样例】52 3 4 1 25【样例解释】其中一种可行的
8、最正确方案，依次选择1,5 1,3 2,3 3,3 5,5【数据范围】对于30%的数据，有1 n 10;对于70%的数据，有1 n 1000;对于 100%的数据，有 1 n 100000, 0 g21,同时对于所有的K i g 21；条件B：对于所有的1&i 0可，有g2i g21,同时对于所有的 K i 0 ?有 g2i 1时最多有 一个能满足。请问，栋栋最多能将多少株花留在原地。【输入】输入文件为。输入的第一行包含一个整数，表示开始时花的株数第二行包含个整数，依次为？1, ?2,，？n,表示每株花的高度。【输出】输出文件为。输出一行，包含一个整数，表示最多能留在原地的花的株数【输入输出样
9、例】55 3 2 1 23【输入输出样例说明】有多种方法可以正好保存3株花，例如，留下第1、4、5株，高度分别为5、1、2,满足条件B。【数据范围】对于20%的数据，n 10 ;对于30%的数据，n 25 ;对于 70%的数据，n 1000, 0 ?n 1000;对于 100%的数据，1 n 100,000, 0 ?n 1,000,000 , 所有的？n随机生成，所有随机数服从某区间内的均匀分布。3 .华容道()【问题描述】小B最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面，华容 道是否根本就无法完成，如果能完成，最少需要多少时间。小B玩的
10、华容道与经典的华容道游戏略有不同，游戏规那么是 这样的：1. 在一个n*m 棋盘上有n*m 个格子，其中有且只有一个 格子是空白的，其余 n*1个格子上每个格子上有一个棋子，每个 棋子的大小都是1*1的；2. 有些棋子是固定的，有些棋子那么是可以移动的；3. 任何与空白的格子相邻有公共的边的格子上的棋子都 可以移动到空白格子上。游戏的目的是把某个指定位置可以活动 的棋子移动到目标位置。给定一个棋盘，游戏可以玩 q次，当然，每次棋盘上固定的 格子是不会变的，但是棋盘上空白的格子的初始位置、指定的可移 动的棋子的初始位置和目标位置却可能不同。第i次玩的时候，空白的格子在第行第 列，指定的可移动棋子
11、的初始位置为第行第 歹U,目标位置为第行第 歹I。假设小B每秒钟能进行一次移动棋子的操作，而其他操作的 时间都可以忽略不计。请你告诉小B每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。【输入】输入文件为。第一行有3个整数，每两个整数之间用一个空格隔开，依次表 示n、m和q；接下来的n行描述一个n*m的棋盘，每行有m个整数，每两个 整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，0 表示该格子上的棋子是固定的，1表示该格子上的棋子可以移动或 者该格子是空白的。接下来的q行，每行包含6个整数依次是、，每两 个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定 棋子的初始位置和
12、目标位置。【输出】输出文件名为。输出有q行，每行包含1个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标那么输出 -1。【输入输出样例】3 4 220 1 1 1-10 1 1 00 1 0 03 2 1 2 2 21 2 2 2 3 2【输入输出样例说明】棋盘上划叉的格子是固定的，红色格子是目标位置，圆圈表示 棋子，其中绿色圆圈表示目标棋子。1 .第一次游戏，空白格子的初始位置是 3, 2 图中空白 所示，游戏的目标是将初始位置在 1, 2上的棋子图中绿色圆 圈所代表的棋子移动到目标位置 2, 2图中红色的格子上。移动过程如下：初始状态第一步之后第二步之后2 .第二次游戏，空白格子的初始位置是1, 2图中空白 所示，游戏的目标是将初始位置在2, 2 上的棋子图中绿色 圆圈所示移动到目标位置 3, 2 上。初始状态要将指定块移入目标位置，必须先将空白块移入目标位置，空 白块要移动到目标位置，必然是从位置2, 2上与当前图中目标位置上的棋子交换位置，之后能与空白块交换位置的只有当前图 中目标位置上的那个棋子，因此目标棋子永远无法走到它的目标位 置，游戏无法完成。【数据范围】对于 30%的数据，1 n, m 10 , q = 1 ;对于 60%的数据，1 n, m 30 , q w 10 ;对于 100%的数据，1 n, m w 30 , q w 500。
