万卷网

NOIP提高组

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

NOIP提高组

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

我的练习

顺序练习

随机练习

章节练习

错题练习

题库预览

填空题输入：7输出：_________

简答题信息学NOIP提高组编程试题

填空题信息学NOIP提高组试题

填空题输入：4 61 2 102 3 203 4 304 1 401 3 502 4 60 输出：

填空题输入：114 5 6 6 4 3 3 2 3 2 1输出：

简答题信息学NOIP提高组编程试题

多选题为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。下列英文缩写中，（）是网络协议

填空题平面图可以在画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边，如右图所示。那么，5个顶点的平面图至少有条边。

填空题定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”可以将 A 移到 B 之前，变字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要________次操作。

简答题蚯蚓【问题描述】本题中，我们将用符号表示对c向下取整，例如：蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。蛐蛐国里现在共有 n 只蚯蚓（n 为正整数）。每只蚯蚓拥有长度，我们设第 i 只蚯蚓的长度为 ai(i=1,2,…,n)，并保证所有的长度都是非负整数（即：可能存在长度为 0的蚯蚓）。每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 p（是满足 0 < p < 1 的有理数）决定，设这只蚯蚓长度为 x，神刀手会将其切成两只长度分别为的蚯蚓。特殊地，如果这两个数的其中一个等于 0则这个长度为 0 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 q（是一个非负整常数）。蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m 秒才能到来……（m 为非负整数）蛐蛐国王希望知道这 m秒内的战况。具体来说，他希望知道：m 秒内，每一秒被切断的蚯蚓被切断前的长度（有 m 个数）；m 秒后，所有蚯蚓的长度（有 n+m 个数）。蛐蛐国王当然知道怎么做啦！但是他想考考你……【输入格式】从文件earthworm.in中读入数据。第一行包含六个整数 n , m , q , u , v , t 其中：n , m , q的意义见【问题描述】；u , v , t均为正整数；你需要自己计算 p = u / v（保证 0 < u < v）t 是输出参数，其含义将会在【输出格式】中解释。第二行包含 n 个非负整数，为 a 1 , a 2 , … , a n即初始时 n 只蚯蚓的长度。同一行中相邻的两个数之间，恰好用一个空格隔开。【输出格式】输出到文件earthworm.out中。第一行输出个整数，按时间顺序，依次输出第 t 秒，第 2t 秒，第 3t 秒，……被切断蚯蚓（在被切断前）的长度。第二行输出个整数，输出 m 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 t ，第 2t，第3t，……的长度。同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。请阅读样例来更好地理解这个格式。【样例1输入】3 7 1 1 3 13 3 2【样例1输出】3 4 4 4 5 5 66 6 6 5 5 4 4 3 2 2【样例1说明】在神刀手到来前：3 只蚯蚓的长度为3,3,2。1 秒后：一只长度为3 的蚯蚓被切成了两只长度分别为1 和2 的蚯蚓，其余蚯蚓的长度增加了1。最终4 只蚯蚓的长度分别为(1,2),4,3。括号表示这个位置刚刚有一只蚯蚓被切断。2 秒后：一只长度为4 的蚯蚓被切成了1 和3 。5 只蚯蚓的长度分别为：2,3,(1,3),4。3秒后：一只长度为4 的蚯蚓被切断。6 只蚯蚓的长度分别为：3,4,2,4,(1,3)。4 秒后：一只长度为4 的蚯蚓被切断。7 只蚯蚓的长度分别为：4,(1,3),3,5,2,4。5 秒后：一只长度为5 的蚯蚓被切断。8 只蚯蚓的长度分别为：5,2,4,4,(1,4),3,5。6 秒后：一只长度为5 的蚯蚓被切断。9 只蚯蚓的长度分别为：(1,4),3,5,5,2,5,4,6。7 秒后：一只长度为6 的蚯蚓被切断。10 只蚯蚓的长度分别为：2,5,4,6,6,3,6,5,(2,4)。所以，7 秒内被切断的蚯蚓的长度依次为3,4,4,4,5,5,6。7 秒后，所有蚯蚓长度从大到小排序为 6,6,6,5,5,4,4,3,2,2。【样例2输入】3 7 1 1 3 23 3 2【样例2输出】4 4 56 5 4 3 2【样例2说明】这个数据中只有t=2与上个数据不同。只需在每行都改为每两个数输出一个数即可。虽然第一行最后有一个6 没有被输出，但是第二行仍然要重新从第二个数再开始输出。【样例3输入】3 7 1 1 3 93 3 2【样例3输出】2【样例3说明】这个数据中只有t=9与上个数据不同。注意第一行没有数要输出，但也要输出一个空行。【子任务】

简答题组合数问题【问题描述】组合数表示的是从 n 个物品中选出 m 个物品的方案数。举个例子，从 (1,2,3) 三个物品中选择两个物品可以有 (1,2)，(1,3)，(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数的一般公式：其中 n!=1×2×…×n 。小葱想知道如果给定 n，m 和 k，对于所有的 0≤i≤n，0≤j≤min(i,m) 有多少对 (i,j) 满足是 k 的倍数。【输入格式】从文件problem.in中读入数据。第一行有两个整数 t，k，其中 t 代表该测试点总共有多少组测试数据，k 的意义见【问题描述】。接下来 t 行每行两个整数 n，m，其中 n，m 的意义见【问题描述】。【输出格式】输出到文件problem.out中。t 行，每行一个整数代表所有的 0≤i≤n，0≤j≤min(i,m) 中有多少对 (i,j) 满足是 k 的倍数。【样例1输入】1 23 3【样例1输出】1【样例1说明】在所有可能的情况中，只有是 2 的倍数。【样例2输入】2 54 56 7【样例2输出】07【子任务】

简答题愤怒的小鸟【问题描述】Kiana 最近沉迷于一款神奇的游戏无法自拔。简单来说，这款游戏是在一个平面上进行的。有一架弹弓位于 (0,0) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 y=ax^2+bx 的曲线，其中 a，b 是 Kiana 指定的参数，且必须满足 a＜0。当小鸟落回地面（即x轴）时，它就会瞬间消失。在游戏的某个关卡里，平面的第一象限中有 n 只绿色的小猪，其中第 i 只小猪所在的坐标为 (xi,yi) 。如果某只小鸟的飞行轨迹经过了(xi,yi)，那么第 i 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；如果一只小鸟的飞行轨迹没有经过(xi,yi)，那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。例如，若两只小猪分别位于 (1,3) 和 (3,3) ，Kiana 可以选择发射一只飞行轨迹为 y=-x^2+4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。假设这款游戏一共有 T 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。【输入格式】从文件angrybirds.in中读入数据第一行包含一个正整数T，表示游戏的关卡总数。下面依次输入这T个关卡的信息，每个关卡第一行包含两个非负整数 n，m ，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 n 行中，第 i 行包含两个正实数 xi，yi ，表示第 i 只小猪坐标为 (xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。如果 m=0，表示 Kiana 输入了一个没有任何作用的指令。如果 m=1 ，则这个关卡将会满足：至多用只小鸟即可消灭所有小猪。如果 m=2 ，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少只小猪。保证 1≤n≤18，0≤m≤2，0＜xi,yi＜10，输入中的实数均保留到小数点后两位。【输出格式】输出到文件angrybirds.out中。对每个关卡依次输出一行答案。输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。【样例1输入】22 01.00 3.003.00 3.005 21.00 5.002.00 8.003.00 9.004.00 8.005.00 5.00【样例1输出】11【样例1说明】这组数据中一共有两个关卡。第一个关卡与【问题描述】中的情形相同，2 只小猪分别位于 (1.00,3.00) 和 (3.00,3.00) ，只需发射一只飞行轨迹为 y=-x^2+4x 的小鸟即可消灭它们。第二个关卡中有 5 只小猪，但经过观察我们可以发现它们的坐标都在抛物线 y=-x^2+6x 上，故 Kiana 只需要发射一只小鸟即可消灭所有小猪。【样例2输入】32 01.41 2.001.73 3.003 01.11 1.412.34 1.792.98 1.495 02.72 2.722.72 3.143.14 2.723.14 3.145.00 5.00【样例2输出】223【样例3输入】110 07.16 6.282.02 0.388.33 7.787.68 2.097.46 7.865.77 7.448.24 6.724.42 5.115.42 7.798.15 4.99【样例3输出】6【子任务】数据的一些特殊规定如下表：

简答题玩具谜题【问题描述】小南有一套可爱的玩具小人，它们各有不同的职业。有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图：这时singer告诉小南一个谜题：“眼镜藏在我左数第3个玩具小人的右数第1个玩具小人的左数第2个玩具小人那里。”小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。小南一边艰难地辨认着玩具小人，一边数着：“singer朝内，左数第3个是archer。“archer朝外，右数第1个是thinker。“thinker朝外，左数第2个是writer。“所以眼镜藏在writer这里！”虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为：有n个玩具小人围成一圈，已知它们的职业和朝向。现在第1个玩具小人告诉小南一个包含m条指令的谜题，其中第i条指令形如“左数/右数第Si个玩具小人”。你需要输出依次数完这些指令后，到达的玩具小人的职业。【输入格式】从文件toy.in中读入数据。输入的第一行包含两个正整数n, m，表示玩具小人的个数和指令的条数。接下来n行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。其中0表示朝向圈内，1表示朝向圈外。保证不会出现其他的数。字符串长度不超过10且仅由小写字母构成，字符串不为空，并且字符串两两不同。整数和字符串之间用一个空格隔开。接下来m行，其中第i行包含两个整数ai, si，表示第i条指令。若ai=0，表示向左数Si个人；若ai=1，表示向右数si个人。保证ai不会出现其他的数，1<=Si<n。【输出格式】输出到文件toy.out中。输出一个字符串，表示从第一个读入的小人开始，依次数完m条指令后到达的小人的职业。【样例1输入】7 30 singer0 reader0 mengbier1 thinker1 archer0 writer1 mogician0 31 10 2【样例1输出】writer【样例1说明】这组数据就是【问题描述】中提到的例子。【样例2输入】10 101 c0 r0 p1 d1 e1 m1 t1 y1 u0 v1 71 11 40 50 30 11 61 20 80 4【样例2输出】y【子任务】子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。每个测试点的数据规模及特点如下表：其中一些简写的列意义如下：

简答题换教室【问题描述】对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。在可以选择的课程中，有 2n 节课程安排在 n 个时间段上。在第 i（1≤i≤n）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 ci上课，而另一节课程在教室 di 进行。在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 n 节安排好的课程。如果学生想更换第 i 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 i 个时间段去教室 di上课，否则仍然在教室 ci上课。由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 i 节课程的教室时，申请被通过的概率是一个已知的实数 ki，并且对于不同课程的申请，被通过的概率是互相独立的。学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 m 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的 m 门课程，也可以不用完这 m 个申请的机会，甚至可以一门课程都不申请。因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。牛牛所在的大学有 v 个教室，有 e 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。当第 i（1≤i≤n−1）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。【输入格式】从文件classroom.in中读入数据。第一行四个整数 n,m,v,e。n 表示这个学期内的时间段的数量；m 表示牛牛最多可以申请更换多少节课程的教室；v 表示牛牛学校里教室的数量；e表示牛牛的学校里道路的数量。第二行 n 个正整数，第 i（1≤i≤n）个正整数表示 ci，即第 i 个时间段牛牛被安排上课的教室；保证 1≤ci≤v。第三行 n 个正整数，第 i（1≤i≤n）个正整数表示 di，即第 i 个时间段另一间上同样课程的教室；保证 1≤di≤v。第四行 n 个实数，第 i（1≤i≤n）个实数表示 ki，即牛牛申请在第 i 个时间段更换教室获得通过的概率。保证0≤ki≤1。接下来 e 行，每行三个正整数 aj,bj,wj，表示有一条双向道路连接教室 aj,bj，通过这条道路需要耗费的体力值是 wj；保证 1≤aj,bj≤v，1≤wj≤100。保证1≤n≤2000，0≤m≤2000，1≤v≤300，0≤e≤90000。保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。保证输入的实数最多包含 3 位小数。【输出格式】输出到文件classroom.out中。输出一行，包含一个实数，四舍五入精确到小数点后恰好2位，表示答案。你的输出必须和标准输出完全一样才算正确。测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 4×10^−3。（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）【样例1输入】3 2 3 32 1 21 2 10.8 0.2 0.51 2 51 3 32 3 1【样例1输出】2.80【样例1说明】所有可行的申请方案和期望收益如下表：【提示】道路中可能会有多条双向道路连接相同的两间教室。也有可能有道路两端连接的是同一间教室。请注意区分n，m，v，e的意义，n不是教室的数量，m不是道路的数量。【子任务】特殊性质1：图上任意两点ai，bi，间，存在一条耗费体力最少的路径只包含一条道路。特殊性质2：对于所有的1≤i≤n，ki=1。

简答题天天爱跑步【问题描述】小c 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 n 个结点和 n−1 条边的树，每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 1 到 n 的连续正整数。现在有 m 个玩家，第 i 个玩家的起点为 si，终点为 Ti。每天打卡任务开始时，所有玩家在第 0 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树，所以每个人的路径是唯一的)小c 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 j 的观察员会选择在第 wj 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 wj 秒也正好到达了结点 j。小c 想知道每个观察员会观察到多少人?注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点 j 作为终点的玩家：若他在第 wj 秒前到达终点,则在结点 j 的观察员不能观察到该玩家；若他正好在第 wj 秒到达终点,则在结点 j 的观察员可以观察到这个玩家。【输入格式】从文件running.in中读入数据。第一行有两个整数 n 和 m。其中 n 代表树的结点数量, 同时也是观察员的数量, m 代表玩家的数量。接下来 n−1 行每行两个整数 u 和 v，表示结点 u 到结点 v 有一条边。接下来一行 n 个整数，其中第 j 个整数为 wj , 表示结点 j 出现观察员的时间。接下来 m 行，每行两个整数 Si，和 Ti，表示一个玩家的起点和终点。对于所有的数据，保证 1≤Si,Ti≤n,0≤Wj≤n。【输出格式】输出到文件running.out中。输出 1 行 n 个整数，第 j 个整数表示结点 j 的观察员可以观察到多少人。【样例1输入】6 32 31 2 1 4 4 5 4 6 0 2 5 1 2 3 1 5 1 3 2 6 【样例1输出】2 0 0 1 1 1【样例1说明】对于 1 号点，w1=0，故只有起点为 1 号点的玩家才会被观察到，所以玩家 1 和玩家 2 被观察到，共有 2 人被观察到。对于 2 号点，没有玩家在第 2 秒时在此结点，共 0 人被观察到。对于 3 号点，没有玩家在第 5 秒时在此结点，共 0 人被观察到。对于 4 号点，玩家 1 被观察到，共 1 人被观察到。对于 5 号点，玩家 1 被观察到，共 1 人被观察到。对于 6 号点，玩家 3 被观察到，共 1 人被观察到。【样例2输入】5 3 1 2 2 3 2 4 1 5 0 1 0 3 0 3 1 1 45 5 【样例2输出】1 2 1 0 1【子任务】每个测试点的数据规模及特点如下表所示。提示: 数据范围的个位上的数字可以帮助判断是哪一种数据类型。【提示】如果你的程序需要用到较大的栈空间 (这通常意味着需要较深层数的递归), 请务必仔细阅读选手目录下的文本文档 running/stack.pdf, 以了解在最终评测时栈空间的限制与在当前工作环境下调整栈空间限制的方法。