NOIP考前冲刺考试练习-武森汇总课件.ppt

1、NOIP考前冲刺-考试练习武森2023-1-1模拟试题一 胖胖的陶陶胖胖的陶陶tao 懒懒的多多懒懒的多多duo 笨笨的金明笨笨的金明ming 郁闷的郁闷的QQ 输入输出统一为输入输出统一为 文件名文件名.in/文件名文件名.out 时间限制统一为时间限制统一为1s2023-1-1胖胖的陶陶题目描述题目描述 陶陶家的院子里有一棵苹果树，每到秋天树上就会结出陶陶家的院子里有一棵苹果树，每到秋天树上就会结出NN个个苹果，第苹果，第i i个苹果离地面高度为个苹果离地面高度为aiai。苹果成熟的时候，陶陶就会。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有跑去摘苹果。陶陶有MM个板凳，第个板凳，第i i个

2、板凳的高度为个板凳的高度为bibi，当她不，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。不过请能直接用手摘到苹果的时候，就会踩到板凳上再试试。不过请注意，因为陶陶最近长胖了，所以每个板凳只能用一次。注意，因为陶陶最近长胖了，所以每个板凳只能用一次。任务任务 陶陶把手伸直的时候能够达到的最大高度为陶陶把手伸直的时候能够达到的最大高度为HH，站在第，站在第i i个板个板凳上时能够达到的最大高度为凳上时能够达到的最大高度为H+biH+bi，请帮陶陶算一下她够摘到，请帮陶陶算一下她够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。的苹果的数目。假设她碰到苹果，苹果就会掉下来。2023-1-

3、1胖胖的陶陶输入文件输入文件 第一行三个正整数第一行三个正整数 N M H 第二行第二行 N个正整数个正整数ai 第三行第三行 M个正整数个正整数bi输出文件输出文件 一个数，最多摘到的苹果的数目。一个数，最多摘到的苹果的数目。2023-1-1胖胖的陶陶样例输入样例输入 4 2 2 2 3 5 7 1 4样例输出样例输出 3数据约定数据约定 60%N,M=1000 100%N,M=100000 1=ai,bi,H=10000 2023-1-1解法贪心贪心将苹果的高度按照从低到高的顺序排序。将苹果的高度按照从低到高的顺序排序。将梯子的高度按照从低到高的顺序排序。将梯子的高度按照从低到高的顺序排序

4、。一直如果淘淘站在梯子一直如果淘淘站在梯子i上够不到苹果上够不到苹果j，则淘淘站在梯子，则淘淘站在梯子i上也上也够不到苹果够不到苹果j+1.所以淘淘只能用梯子所以淘淘只能用梯子i+1去尝试去尝试.以此类推。以此类推。2023-1-1懒懒的多多题目描述题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了子的不同种类分成了NN堆，第堆，第i i堆果子重量为堆果子重量为wiwi，坐标为，坐标为(xi,yi)(xi,yi)。多多决定把所有的果子合成一堆。多多决定把所有的果子合成一堆。每一次，多多可以把第每一次，多多可以把第

5、i i堆果子移至第堆果子移至第j j堆，消耗的体力为堆，消耗的体力为wiwi*(|xi-xj|+|yi-yj|)(|xi-xj|+|yi-yj|)，这样两堆果子就合并成一堆了。可以看，这样两堆果子就合并成一堆了。可以看出，所有的果子经过出，所有的果子经过N-1N-1次合并之后，就只剩下一堆了。多多次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为多多很懒，所以他不想消耗太多的体力。因为多多很懒，所以他不想消耗太多的体力。任务任务 请问将所有果子合并成一堆消耗的总体力最少是多少。请问将所有果子合并成一堆消耗

6、的总体力最少是多少。2023-1-1懒懒的多多输入文件 第一行 N。接下来N行 xi yi wi。输出文件 一个数，最少消耗的体力和。2023-1-1懒懒的多多样例输入样例输入 4 2 1 1 1 2 3 3 1 2 2 4 2样例输出样例输出14数据约定数据约定 60%N=1000 100%N=100000 1=xi,yi,wi,Ans=|xi-x|xi-xk k|+|yi-y|+|yi-yk k|则为了使的体力耗费最少，每次将两堆合并的时候，将最则为了使的体力耗费最少，每次将两堆合并的时候，将最终目标作为一个合并对象较优。终目标作为一个合并对象较优。则枚举最终合并的目标地点，并且计算体力耗

7、费值即可。则枚举最终合并的目标地点，并且计算体力耗费值即可。2023-1-1笨笨的金明题目描述题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：天对他说：“你的房间需要购买哪些物品，怎么布置，你说了你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过算，只要不超过M元钱就行元钱就行”。今天一早，金明就开始做预算了。金明一共想买今天一早，金明就开始做预算了。金明一共想买N件物品，第件物品，第i件物品价格为件物品价

8、格为ci，重要度为，重要度为wi。物品。物品1可以直接购买，其余的可以直接购买，其余的物品均从属于一个主件物品均从属于一个主件pi，必须要先购买，必须要先购买pi才能购买才能购买i（即构（即构成一棵以成一棵以1为根的树）。为根的树）。金明想要让所购买的物品重要度之和尽量大，但因为他是个笨金明想要让所购买的物品重要度之和尽量大，但因为他是个笨小孩，所以求助于聪明的你。小孩，所以求助于聪明的你。任务任务求出在购买物品总价格不超过求出在购买物品总价格不超过M元（可以等于元（可以等于M元）的前提下，元）的前提下，所购买物品的重要度之和最大为多少。所购买物品的重要度之和最大为多少。2023-1-1笨笨的

9、金明输入文件 第一行 N M。接下来N行 pi ci wi（p1=0）。保证输入数据构成一棵树。输出文件 一个数，最大的重要度之和。2023-1-1笨笨的金明样例输入 5 7 0 1 3 1 5 5 1 4 2 3 2 4 3 1 3样例输出 9数据约定70%N,M=666 100%N,M=5000 1=ci=M 1=wi=10000 且为整数2023-1-1解法白板白板2023-1-1郁闷的Q题目描述题目描述 对于一个对于一个1-N的排列，第的排列，第i个数为个数为ai，若对于，若对于1=I,j=N满足满足 (ij)and(aiaj)那么我们称那么我们称(ai,aj)为一个顺序对，且该顺序对

10、的权值为为一个顺序对，且该顺序对的权值为(aj-ai)。该该1-N的排列的权值则为其所有顺序对的权值之和。的排列的权值则为其所有顺序对的权值之和。任务任务 求出权值和最大的求出权值和最大的1-N的排列。的排列。2023-1-1郁闷的Q输入文件输入文件 一个正整数一个正整数 N 输出文件输出文件 一个数，最大权值和。一个数，最大权值和。2023-1-1郁闷的Q样例输入样例输入 4样例输出样例输出 10数据约定数据约定30%N=1260%N=30 100%N=402023-1-1试题特点基本都是改编自历年基本都是改编自历年NOIP试题试题难度适中难度适中思维巧妙思维巧妙2023-1-1模拟试题二工

11、件处理工件处理Job山顶问题山顶问题Peaks生成树生成树Tree黑白三角形黑白三角形Triangle输入输出统一为输入输出统一为 文件名文件名.in/文件名文件名.out时间限制统一为时间限制统一为1s2023-1-1工件处理题目描述题目描述 一个工厂所运行的生产线对每个工件有一个工厂所运行的生产线对每个工件有2道工序道工序A和和B，每道工，每道工序有一定数量的机器可以实现，分别定义为序有一定数量的机器可以实现，分别定义为A类机和类机和B类机。类机。对于每个工件，都必须先经工序对于每个工件，都必须先经工序A处理，再经工序处理，再经工序B处理，而每处理，而每个机器可以独立的，同时的工作，每个机

12、器工作需要的时个机器可以独立的，同时的工作，每个机器工作需要的时间不一样。间不一样。任务任务现有现有N个工件，找出最早的时间让所有工件完成所有工序个工件，找出最早的时间让所有工件完成所有工序A和最早和最早时间完成两道工序。时间完成两道工序。2023-1-1工件处理输入文件输入文件 第一行第一行 N M1 M2 分别为工件数，分别为工件数，A类机数量，类机数量，B类机数量。类机数量。第二行第二行 M1个整数描述了每个个整数描述了每个A类机处理任一个工件的时间。类机处理任一个工件的时间。第三行第三行 M2个整数描述了每个个整数描述了每个B类机处理任一个工件的时间。类机处理任一个工件的时间。输出文件

13、输出文件 一行包含两个整数，分别是最早的时间让所有的工件完成工序一行包含两个整数，分别是最早的时间让所有的工件完成工序A作与最早的时间完成两道工序。作与最早的时间完成两道工序。2023-1-1工件处理样例输入样例输入5 2 31 1 1 3 4样例输出样例输出3 5数据约定数据约定 60%N=1000 1=M1,M2=30 T=20 Ans=maxint 100%N=100000 1=M1,M2=5000 T=10000 Ans=maxlongint评分方式评分方式本题有部分分，对于每一个测试点，若你仅有第一个输出正确则得本题有部分分，对于每一个测试点，若你仅有第一个输出正确则得40%分数，若

14、你分数，若你仅有第二个输出正确则得仅有第二个输出正确则得60%分数，若你两个输出均正确则得分数，若你两个输出均正确则得100%分数，分数，否则不得分。否则不得分。2023-1-1解法贪心贪心对于子问题对于子问题A，我们可以每次选择使添加任务后时间最小，我们可以每次选择使添加任务后时间最小的机器来处理，直至安排完的机器来处理，直至安排完N个工件。这样的话，子问题个工件。这样的话，子问题A的解是最优的。对于子问题的解是最优的。对于子问题B，可以认为只要一有半成品，可以认为只要一有半成品完成就将其加工为成品，所以方法是记录子问题完成就将其加工为成品，所以方法是记录子问题A的安排的安排次数，构建数组纪

15、录某时间半成品完成的数目，并依此从次数，构建数组纪录某时间半成品完成的数目，并依此从时间上由时间上由1到最后一个半成品出炉，选择当前最优到最后一个半成品出炉，选择当前最优(添加任添加任务后时间最小且当前最空闲，即当前状态下时间最少务后时间最小且当前最空闲，即当前状态下时间最少)的的B类机器加工。这个方法是较优的，在数据较小时是最优的。类机器加工。这个方法是较优的，在数据较小时是最优的。问题之所在，是子问题问题之所在，是子问题A的解是最优的，但子问题的解是最优的，但子问题A的安排的安排次数不一定是最优的。因为子问题次数不一定是最优的。因为子问题A的解仅仅与最多耗时的解仅仅与最多耗时有关，在最多耗

16、时不变的情况下，可能有多种可能。有关，在最多耗时不变的情况下，可能有多种可能。2023-1-1解法？2023-1-1山顶问题题目描述题目描述 话说某某在话说某某在cj校运会上异军突起，其实不是偶然，而是有历史校运会上异军突起，其实不是偶然，而是有历史原因的。原因的。时光回溯到时光回溯到XX年前，某某为了心中的理想，每天爬年前，某某为了心中的理想，每天爬N里山路上里山路上学。直到有一天学。直到有一天mlj（也就是战神（也就是战神Mars）来到这里，被某）来到这里，被某某所打动，于是决定帮某某一把。从某某家到学校中间的某所打动，于是决定帮某某一把。从某某家到学校中间的这这N里山路在一条直线上，第里

17、山路在一条直线上，第i里山路的海拔高度为里山路的海拔高度为Hi，如，如果一段相同高度的山路两边都比它低或者是山的边界，那果一段相同高度的山路两边都比它低或者是山的边界，那么这段山路将被称之为么这段山路将被称之为“山顶山顶”。mlj想这连绵起伏的山路想这连绵起伏的山路爬着多累啊，于是他决定动用神力，降低某些山路的海拔爬着多累啊，于是他决定动用神力，降低某些山路的海拔高度使得山顶的个数不超过高度使得山顶的个数不超过K。但。但mlj不想做得太明显而被不想做得太明显而被某某发现，于是他求助于你。某某发现，于是他求助于你。任务任务 请求出要使请求出要使“山顶山顶”的数目不超过的数目不超过k，所有山路降低

18、的高度之，所有山路降低的高度之和至少是多少。和至少是多少。2023-1-1山顶问题输入文件输入文件 第一行两个正整数第一行两个正整数 N K。接下来一行接下来一行N个正整数个正整数Hi。输出文件输出文件 一个数，最小的所有山路减少的高度之和。一个数，最小的所有山路减少的高度之和。2023-1-1样例输入样例输入12 11 2 3 3 3 2 1 3 2 2 1 2样例输出样例输出5样例解释样例解释 *1 2 3 3 3 2 1 3 2 2 1 2这是之前山的形状，有这是之前山的形状，有3个山顶。个山顶。*-*-*1 2 3 3 3 2 1 1 1 1 1 1这是这是mlj用了神力之后（用了神力

19、之后（-表示被表示被mlj的神力的神力OOXX掉了），只剩下一个山顶。掉了），只剩下一个山顶。数据约定数据约定100%K=25 1=Hi=100000090%N=1000 100%N=1000002023-1-1解法2023-1-1生成树题目描述题目描述 对于无向图对于无向图G,它的任一棵生成树它的任一棵生成树T的权值的权值P(t)定义为定义为T的所有边的所有边权的最大公约数。权的最大公约数。任务任务 对于给定的图对于给定的图G，求出其所有生成树，求出其所有生成树T1,T2的权值的权值P(T1),P(T2)的最小公倍数。的最小公倍数。2023-1-1生成树输入文件输入文件 第一行第一行 N M

20、 表示图表示图G的点数，边数。的点数，边数。接下来接下来M行行 Si Ti Di 描述一条边（描述一条边（Si,Ti）权值为）权值为 Di。保证图连通，无自环。保证图连通，无自环。输出文件输出文件 一个数，所有生成树权值的最小公倍数。一个数，所有生成树权值的最小公倍数。2023-1-1生成树样例输入样例输入 3 31 2 2 2 3 3 1 3 6样例输出样例输出6样理解释样理解释 有有3棵生成树，权值分别为棵生成树，权值分别为1,2,3,它们的最小公倍数为它们的最小公倍数为6。数据约定数据约定20%M=N-1 30%M=N100%N=1000 M=100000 Di=215-1 AnsD，则

21、白点，则白点黑点，否则黑点黑点，否则黑点白点白点这里的这里的Dij指的是曼哈顿（指的是曼哈顿（|xi-xj|+|yi-yj|)，D为给定值为给定值然后，然后，mlj发现有很多三角形很漂亮，漂亮三角形的定义如下：发现有很多三角形很漂亮，漂亮三角形的定义如下：1.三个顶点三个顶点I J K颜色不完全相同颜色不完全相同2.它们之间的连的边是它们之间的连的边是 IJ JK KI（至于为什么（至于为什么mlj觉得这样漂亮，大概是火星人审美观与众不同吧）觉得这样漂亮，大概是火星人审美观与众不同吧）mlj想知道这里面漂亮三角形的个数，但他视力很差，于是求助于你。想知道这里面漂亮三角形的个数，但他视力很差，于

22、是求助于你。任务任务求出漂亮三角形最少有多少个，最多有多少个。求出漂亮三角形最少有多少个，最多有多少个。2023-1-1黑白三角形输入文件输入文件 第一行两个正整数第一行两个正整数 N D 接下来接下来N行行Xi Yi描述第描述第i个白点的坐标个白点的坐标 再接下来再接下来N行行Xj Yj描述第描述第j个黑点的坐标个黑点的坐标输出文件输出文件 两个数依次为漂亮三角形最少的个数，最多的个数，中间两个数依次为漂亮三角形最少的个数，最多的个数，中间用一个空格隔开。用一个空格隔开。2023-1-1黑白三角形样例输入样例输入2 11 21 13 12 2样例输出样例输出0 2样例解释样例解释 左图为无漂亮三角形的情况，右图存在两个漂亮三角形，分别左图为无漂亮三角形的情况，右图存在两个漂亮三角形，分别是是(1,2,4)(1,3,4)数据约定数据约定40%N=30070%N=3000100%N=100000 1=x,y,d=100000且为整数且为整数 2023-1-1解法2023-1-1题目特点设计算法较多设计算法较多思维较为广泛思维较为广泛2023-1-1讨论时间。讨论时间。