noip2023提高组试题(day1+day2)Word版.docx

《noip2023提高组试题(day1+day2)Word版.docx》由会员分享，可在线阅读，更多相关《noip2023提高组试题(day1+day2)Word版.docx（14页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、CCF全国信息学奥林匹克联赛（NOIP2023 ）复赛提高组dayl（请选手务必细致阅读本页内容）一.题目概况中文题目名称小凯的怀疑时间困难度逛公园英文题目与子书目名mathcomplexitypark可执行文件名mathcomplexitypark输入文件名math.incomplexity.inpark. in输出文件名math.outcomplexity.outpark.out每个测试点时限1秒1秒3秒测试点数目201010每个测试点分值51010附加样例文件有有有结果比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统运行内存上限256M256M512M二.提交源程序文件名对

2、,于C+语言math.cppcomplexity.cpppark.cpp对于C语言math.ccomplexity.cpark.c对于pascal语言math.pascomplexity.paspark.pas三.编译叮嘱（不包含任何优化开关）对于C+语言g+ -o math math.cpp -Img+ -o complexity complexity.cpp -Img+ -o park park.cpp -Im对于c语言gcc -o math math.c-Imgcc -o complexity complexity.c -Imgcc -o park park.c-Im对于pascal语言

3、fpc math.pasfpc complexity.pasfpc park.pas留意事项：1、文件名（程序名和输入输出文件名）必需运用英文小写。2、C/C+中函数main（）的返回值类型必需是int,程序正常结束时的返回值必需是0。3、全国统一评测时接受的机器配置为：CPU AMD Athlon（tm） II x2 240 processor, 2.8GHz, 内存4G,上述时限以此配置为准。4、只供应Linux格式附加样例文件。5、提交的程序代码文件的放置位置请参照各省的具体要求。6、特别提示：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。见选手书目下的 ch

4、eese/cheesel , in 和 cheese/cheesel. anso【输入输出样例1说明】第一组数据，由奶酪的剖面图可见：第一个空洞在（0, 0, 0）与下表面相切 其次个空洞在（0, 0, 4）与上表面相切 两个空洞在（0, 0, 2）相切输出Yes其次组数据，由奶酪的剖面图可见： 两个空洞既不相交也不相切输出No第三组数据，由奶酪的剖面图可见：两个空洞相交且与上下表面相切或相交输出Yes【输入输出样例2见选手书目下的 ches/ches2 . in 和 chs/chse2 . anso【数据规模与约定】对于20%的数据，n = l, 1 W h,rW 10,000,坐标的确定值

5、不超过10,000o对于40%的数据，1 n 8, 1 h , r W 10,000,坐标的确定值不超过10,000。对 于80%的摩，1 W n 1,000, 1 W h,r W 10,000,坐标的确定值不超过10,000。对 于 100%的数据，1 n W 1,000, 1 W h, rW 1,000,000,000, T W 20,坐标的 确定值不超过1,000,000,000。2 .宝藏（treasure.cpp/c/pas）【问题描述】参加考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n个深埋在地下的宝藏屋， 也给出了这n个宝藏屋之间可供开发的m条道路和它们的长度。小明决心亲自前

6、往挖掘全部宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则 相对简洁许多。小明的决心感动了考古挖掘的赞助商，赞助商确定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来确定。在此基础上，小明还须要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 随意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所 能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之 间的道路无需再开发。新开发一条道路的代价是：这条道路的长度X从赞助商帮你打通的宝藏屋到这条道

7、路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。【输入格式】输入文件名为 treasure . ino第一行两个用空格分别的正整数n和m,代表宝藏屋的个数和道路数。接下来m行，每行三个用空格分别的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为1n）,和这条道路的长度v。【输出格式】输出文件名为treasure . outo输出共一行，一个正整数，表示最小的总代价。【输入输出样例11treasure.intreasure.out4 5412 11

8、3 314 12 3 43 4 1见选手书 目下的 treasure/treasurel. intreasure/treasure 1. ans【输入输出样例1说明】小明选定让赞助商打通了 1号宝藏屋。小明开发了道路192,挖掘了 2号宝 藏。开发了道路194,挖掘了 4号宝藏。还开发了道路4玲3,挖掘了 3号宝 藏。工程总代价为：1X1+ 1X1 + 1X2 = 4(12)(194)(493)【样例输入输出2treasure.intreasure.out4 512 113 314 12 3 43 4 25见选手书目下的 treasure/treasure2 . in 与 treasure/t

9、reasure2 . anso【输入输出样例2说明】小明选定让赞助商打通了 1号宝藏屋。小明开发了道路192,挖掘了 2号宝 藏。开发了道路1f3,挖掘了 3号宝藏。还开发了道路194,挖掘了 4号宝 藏。工程总代价为：1X1 + 3X1 + 1XL5(12) (193)(1 9 4)【输入输出样例3见选手书 目下的 treasure/treasure 3 . in 和 treasure/treasure 3 . out。【数据规模与约定】对于20%的数据：保证输入是一棵树，lWnW8, vW5000且全部的v都相等。对于40%的数据：lWnW8, OWmWlOOO, vW5000 且全部的

10、v 都相等。对于70%的数据：lnW8, OWmWlOOO, 5000对于100%的数据：iWnW0WmW1000, vW 5000003 .列队(phalanx.cpp/c/pas)【问题描述】Sylvia是一个酷爱学习的女孩子。前段时间，Sylvia参加了学校的军训。众所周知，军训的时候须要站方阵。Sylvia 所在的方阵中有nxm名学生，方阵的行数为n,列数为m。为了便于管理，教官在训练起先时，依据从前到后，从左到右的依次给方阵中 的学生从1至U n x m编上了号码（参见后面的样例）。即：初始时，第i行第j列 的学生的编号是（i - 1） x m + j。然而在练习方阵的时候，经常会有

11、学生因为各种各样的事情须要离队。在一天 中，一共发生了 q件这样的离队事务。每一次离队事务可以用数对。）（lxn, lym）描述，表示第x行第y列的学生离队。在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达 这样的两条指令：1 .向左看齐。这时第一列保持不动，全部学生向左填补空缺。不难发觉在这条 指令之后，空位在第x行第m歹限2 .向前看齐。这时第一行保持不动，全部学生向前填补空缺。不难发觉在这条 指令之后，空位在第n行第m歹限教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后， 下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第n行第 m

12、列一个空位，这时这个学生会自然地填补到这个位置。因为站方阵真的很无聊，所以Sylvia想要计算每一次离队事务中，离队的同学 的编号是多少。留意：每一个同学的编号不会随着离队事务的发生而变更，在发生离队事务后 方阵中同学的编号可能是乱序的。【输入格式】输入文件名为phalanx. in。输入共q+1行。第1行包含3个用空格分隔的正整数n, m,q,表示方阵大小是 行m歹U，一共发生 了 q次事务。接下来q行依据事务发生依次描述了 q件事务。每一行是两个整数x,y,用一个空 格分隔，表示这个离队事务中离队的学生当时排在第x行第y列。【输出格式】输出文件名为phalanx.outo依据事务输入的依次

13、，每一个事务输出一行一个整数，表示这个离队事务中离队学 生的编号。【输入输出样例1】phalanx.inphalanx.out2 2 31 12 21 2114见选手书目下的 phalanx/phalanxl. in 与 phalanx/phalanxl. anso【输入输出样例1说明】2 42 42 42 42 4今今今今列队的过程如上图所示，每一行描述了一个事务。在第一个事务中，编号为1的同学离队，这时空位在第一行第一列。接着全部同学 向左标齐，这时编号为2的同学向左移动一步，空位移动到第一行其次列。然后全部同 学向上标齐，这时编号为4的同学向上一步，这时空位移动到其次行其次列。最终编号

14、为1的同学返回填补到空位中。【样例输入输出21见选手书目下的phalanx/phalanx2 , in 与 phalanx/phalanx2.anso【数据规模与约定】测试点编号nmq其他约定1,23,45,6 1000 1000 500无7,89,10 5 x 104 5 x 10411,12=1 105 105所有事件/=113,14 3 X 105 3 X 10515,16 3 x 10517,18 105 105 105无19,20 3 x 105 3 x 105 3 x 105数据保证每一个事务满足1.小凯的怀疑(math.cpp/c/pas)【问题描述】小凯手中有两种面值的金币，两

15、种面值均为正整数且彼此互素。每种金币小凯都有 多数个。在不找零的状况下，仅凭这两种金币，有些物品他是无法精确支付的。现在小凯 想知道在无法精确支付的物品中，最贵的价值是多少金币？留意：输入数据保证存在小凯 无法精确支付的商品。【输入格式】输入文件名为math. in。输入数据仅一行，包含两个正整数a和b,它们之间用一个空格隔开，表示小凯手 中金币的面值。【输出格式】输出文件名为math . onto输出文件仅一行，一个正整数N,表示不找零的状况下，小凯用手中的金币不能精 确支付的最贵的物品的价值。【输入输出样例1math , inmath . out3 711见选手书目下的 math/math

16、l. in 和 math/mathl. anso【输入输出样例1说明】小凯手中有面值为3和7的金币多数个，在不找零的前提下无法精确支付价值为1、2、4、5、8、11的物品，其中最贵的物品价值为11,比11贵的物品都能买到，比如:12 = 3*4 + 7*013 = 3*2 + 7* 114 = 3*0 + 7*215 = 3*5 + 7*0【输入输出样例2见选手书目下的 math/math2 . in 和 math/math2 . anso【数据规模与约定】1Wa,bW50o1a,b10,000。1a,b1,000,000,000。对于30%的数据：对于60%的数据：对于100%的数据:2.时

17、间困难度（complexity.cpp/c/pas）【问题描述】小明正在学习一种新的编程语言A+,刚学会循环语句的他激烈地写了好多程序并 给出了他自己算出的时间困难度，可他的编程老师实在不想一个一个检查小明的程序， 于是你的机会来啦！下面请你编写程序来推断小明对他的每个程序给出的时间困难度是否 正确。A+语言的循环结构如下：F i x y循环体E其中“Fix y”表示新建变量i （变量i不行与未被销毁的变量重名）并初始化为x, 然后推断i和y的大小关系，若i小于等于y则进入循环，否则不进入。每次循环结束 后i都会被修改成i+1, 一旦i大于y终止循环。x和y可以是正整数（x和y的大小关系不定）

18、或变量no n是一个表示数据规模的 变量，在时间困难度计算中需保留该变量而不能将其视为常数，该数远大7100o表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。注：本题中为了书写便利，在描述困难度时，运用大写英文字母“0”表示通常意 义下的概念。【输入格式】输入文件名为 complexity. ino输入文件第一行一个正整数t,表示有t （t 10）个程序须要计算时间困难度。 每个程序我们只需抽取其中“F i x y”和即可计算时间困难度。留意：循环结构 允许嵌套。接下来每个程序的第一行包含一个正整数L和一个字符串，L代表程序行数，字符串 表示这个程序的困难度，为（1）”表示常数困难

19、度，% （n人w）”表示困难度为，其中w是 一个小于10。的正整数（输入中不包含引号），输入保证困难度只有。（1）和。（I1Aw）两种 类型。接下来L行代表程序中循环结构中的“Fix y”或者“E”。程序行若以“F”开头，表示进入一个循环，之后有空格分别的三个字符（串）ix y, 其中i是一个小写字母（保证不为n”），表示新建的变量名，x和y可能是正整数或 n,已知若为正整数则确定小于100o程序行若以“E”开头，则表示循环体结束。【输出格式】输出文件名为complxity.out。输出文件共t行，对应输入的t个程序，每行输出“Yes”或“No”或者“ERR”（输 出中不包含引号），若程序实际

20、困难度与输入给出的困难度一样则输出“Yes”，不一样 则输出“No”，若程序有语法错误（其中语法错误只有：F和E不匹配新建的变 量与已经存在但未被销毁的变量重复两种状况），则输出“ERR”。留意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 “ERR”。【输入输出样例1complexity.incomplexity. out8 2 0(1) Fill E2 0 (nAl) F x 1 n E 1 0(1) F x 1 n4 0 (nA2) F x 5 nF y 10 n EE 4 0(n人2) F x 9 n EF y 2 n E4 0 (nAl) F x 9 n F y n

21、 4 EE 4 0(1) F y n 4 F x 9 n EE4 0 (nA2) F x 1 n F x 1 10 EEYesYes ERRYes NoYesYes ERR见选手书目下的complexity/complexity! . in 和 complexity/complexityl. ans0【输入输出样例1说明】第一个程序i从1到1是常数困难度。其次个程序x从1到n是n的一次方的困难度。第三个程序有一个F开启循环却没有E结束，语法错误。第四个程序二重循环，n的平方的困难度。第五个程序两个一重循环，n的一次方的困难度。第六个程序第一重循环正常，但其次重循环起先即终止（因为n远大于100

22、,100大于4）。 第七个程序第一重循环无法进入，故为常数困难度。第八个程序其次重循环中的变量x与第一重循环中的变量重复，出现语法错误，输出 ERRo【输入输出样例2见选手书目下的complexity/complex!ty2 . in 和 complexity/complexity2 . anso【数据规模与约定】对于30%的数据：不存在语法错误，数据保证小明给出的每个程序的前L/2行确定 为以F开头的语句，第L/2+1行至第L行确定为以E开头的语句，L=10,若x、y均 为整数，x确定小于y,且只有y有可能为no对于50%的数据：不存在语法错误，L=100,且若x、y均为整数，x确定小于y,

23、 且只有y有可能为no对于70%的数据：不存在语法错误，L=100o对于100%的数据：L=100o3.逛公园(park , cpp/c/pas)【问题描述】策策同学特别宠爱逛公园。公园可以看成一张个点条边构成的有向图，且没有自 环和重边。其中1号点是公园的入口，号点是公园的出口，每条边有一个非负权值，代 表策策经过这条边所要花的时间。策策每天都会去逛公园，他总是从1号点进去，从号点出来。策策宠爱簇新的事物，他不希望有两天逛公园的路途完全一样，同时策策还是一个 特别酷爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。假如1号点到 号点的最短路长为，那么策策只会宠爱长度不超过+的路途。

24、策策同学想知道总共有多少条满足条件的路途，你能帮帮他吗？为避开输出过大，答案对取模。假如有无穷多条合法的路途，请输出-1。【输入格式】输入文件名为park. ino第一行包含一个整数，代表数据组数。接下来组数据，对于每组数据：第一行包含四个整数每两个整数之间用一个空格隔开。接下来行，每行三个整数，一代表编号为，的点之间有一条权值为的有向边，每两个 整数之间用一个空格隔开。【输出格式】输出文件名为park. outo输出文件包含行，每行一个整数代表答案。【输入输出样例1park . inpark out25 7 2 1012 12 4 04 5 22 3 23 4 14 5 215 32 2 0

25、 1012 02 103-1见选手书 目下的 park/parklin 和 park/parkl. anso 对于第一组数据，最短路为3o1 5, 12 4 5, 12 3 5 为 3 条合法路径。【输入输出样例2见选手书 目下的 park/park2.in 和 park/park2 . anso【数据规模与约定】对于不同的测试点，我们约定各种参数的规模不会超过如下测试点编号是否有0边155100否25100020000否351000200050否451000200050否551000200050否651000200050是751000002000000否8310000020000050否93

26、10000020000050是10310000020000050是对于 100%的数据4109,0 4 4 1000。数据保证：至少存在一条合法的路途。CCF全国信息学奥林匹克联赛（NOIP2023 ）复赛提高组day2（请选手务必细致阅读本页内容）一.题目概况中文题目名称奶酪宝藏列队英文题目与子书目名cheesetreasurephalanx可执行文件名cheesetreasurephalanx输入文件名cheese.intreasure. inphalanx.in输出文件名cheese.outtreasure.outphalanx.out每个测试点时限1秒1秒2秒测试点数目102020每个

27、测试点分值1055附加样例文件有有有结果比较方式全文比较（过滤行末空格及文末回车）题II类型传统传统传统运行内存上限256M256M512M二.提交源程序文件名对于C+语言cheese.cpptreasure.cppphalanx.cpp对于C语言cheese.ctreasure.cphalanx.c对于pascal语言cheese.pastreasure.pasphalanx.pas三.编译叮嘱（不包含任何优化开关）对于C+语言g+ -o cheese cheese.cpp -Img+ -o treasure treasure.cpp -Img+ -o phalanx phalanx.cpp

28、 -Im对于c语言gcc -o cheesegcc -o treasuregcc -o phalanxcheese.c -Imtreasure.c -Imphalanx.c -Im对于 pascal语言fpc cheese.pasfpc treasure.pasfpc phalanx.pas留意事项：1、文件名（程序名和输入输出文件名）必需运用英文小写。2、C/C+中函数main（）的返回值类型必需是int,程序正常结束时的返回值必需是0。3、全国统一评测时接受的机器配置为：CPU AMD Athlon（tm） II x2 240 processor, 2.8GHz, 内存4G,上述时限以此配

29、置为准。4、只供应Linux格式附加样例文件。5、提交的程序代码文件的放置位置请参照各省的具体要求。6、特别提示：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。1.奶酪(cheese.cpp/c/pas)【问题描述】现有一块大奶酪，它的高度为h,它的长度和宽度我们可以认为是无限大的，奶酪中 间有许多半径褶国的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中， 奶酪的 下表面为Z=0,奶酪的上表面为2 =限现在，奶酪的下表面有一只小老鼠Jerry,它知道奶酪中全部空洞的球心所在的坐 标。假如两个空洞相切或是相交，则Jerry可以从其中一个空洞跑到另一个空洞，特

30、别地，假如一个空洞与下表面相切或是相交，Jerry则可以从奶酪下表面跑进空洞；假如 一个空洞与上表面相切或是相交，Jerry则可以从空洞跑到奶酪上表面。位于奶酪下表面的Jerry想知道，在不被筑勿酷的状况下，能否利用已有的空洞跑到奶酪的上表面去?空间内两点2（22）的距离公式如下:dist(L2)= V(1 -2)2 + (1 -2)2 + (1 2)2【输入格式】输入文件名为cheese . ino每个输入文件包含多组数据。输入文件的第一行，包含一个正整数T,代表该输入文件中所含的数据组数。接下来是T组数据，每组数据的格式如下：第一行包含三个正整数n, h和r,两个数之间以一个空格分开，分别代表奶酪中空 洞的数量，奶酪的高度和空洞的半径。接下来的n行，每行包含三个整数x、y、z,两个数之间以一个空格分开，表示空 洞球心坐标为Q ,）。【输出格式】输出文件名为chs.out。输出文件包含T行，分别对应T组数据的答案，假如在第i组数据中，Jerry能从下 表面跑到上表面则输出Yes,假如不能，贝脖俞出“N。”（均不包含弓1号）。【输入输出样例11cheese.incheese.out32 4 10 0 10 0 32 5 10 0 10 0 42 5 20 0 22 0 4YesNoYes