Noip考前冲刺-考试练习

NOIP考前冲刺

--考试练习武森2024/6/2模拟试题一胖胖的陶陶 tao懒懒的多多 duo笨笨的金明 ming郁闷的Q Q输入输出统一为文件名.in/文件名.out时间限制统一为1s2024/6/2胖胖的陶陶题目描述陶陶家的院子里有一棵苹果树，每到秋天树上就会结出N个苹果，第i个苹果离地面高度为ai。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有M个板凳，第i个板凳的高度为bi，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。不过请注意，因为陶陶最近长胖了，所以每个板凳只能用一次。任务陶陶把手伸直的时候能够到达的最大高度为H，站在第i个板凳上时能够到达的最大高度为H+bi，请帮陶陶算一下她够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。2024/6/2胖胖的陶陶输入文件第一行三个正整数NMH第二行N个正整数ai第三行M个正整数bi输出文件一个数，最多摘到的苹果的数目。2024/6/2胖胖的陶陶样例输入 422 2357 14样例输出 3数据约定 60%N,M<=1000 100%N,M<=1000001<=ai,bi,H<=100002024/6/2解法贪心将苹果的高度按照从低到高的顺序排序。将梯子的高度按照从低到高的顺序排序。一直如果淘淘站在梯子i上够不到苹果j，那么淘淘站在梯子i上也够不到苹果j+1.所以淘淘只能用梯子i+1去尝试.以此类推。。。2024/6/2懒懒的多多题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了N堆，第i堆果子重量为wi，坐标为(xi,yi)。多多决定把所有的果子合成一堆。

每一次，多多可以把第i堆果子移至第j堆，消耗的体力为wi*(|xi-xj|+|yi-yj|)，这样两堆果子就合并成一堆了。可以看出，所有的果子经过N-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为多多很懒，所以他不想消耗太多的体力。任务

请问将所有果子合并成一堆消耗的总体力最少是多少。2024/6/2懒懒的多多输入文件第一行N。接下来N行xiyiwi。输出文件一个数，最少消耗的体力和。2024/6/2懒懒的多多样例输入 4 211 123 312 242样例输出14数据约定 60%N<=1000 100%N<=1000001<=xi,yi,wi,Ans<=maxlongint且为整数2024/6/2解法根据体力消耗公式易知|xi-xj|+|yi-yj|+|xj-xk|+|yj-yk|>=|xi-xk|+|yi-yk|那么为了使的体力消耗最少，每次将两堆合并的时候，将最终目标作为一个合并对象较优。那么枚举最终合并的目标地点，并且计算体力消耗值即可。2024/6/2笨笨的金明题目描述金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他快乐的是，妈妈昨天对他说：“你的房间需要购置哪些物品，怎么布置，你说了算，只要不超过M元钱就行”。今天一早，金明就开始做预算了。金明一共想买N件物品，第i件物品价格为c[i]，重要度为w[i]。物品1可以直接购置，其余的物品均附属于一个主件p[i]，必须要先购置p[i]才能购置i〔即构成一棵以1为根的树〕。金明想要让所购置的物品重要度之和尽量大，但因为他是个笨小孩，所以求助于聪明的你。任务求出在购置物品总价格不超过M元〔可以等于M元〕的前提下，所购置物品的重要度之和最大为多少。2024/6/2笨笨的金明输入文件第一行NM。接下来N行piciwi〔p1=0〕。 保证输入数据构成一棵树。输出文件一个数，最大的重要度之和。2024/6/2笨笨的金明样例输入 57 013 155 142 324 313样例输出 9数据约定70%N,M<=666 100%N,M<=50001<=ci<=M1<=wi<=10000且为整数2024/6/2解法白板2024/6/2郁闷的Q题目描述对于一个1-N的排列，第i个数为ai，假设对于1<=I,j<=N满足 (i<j)and(ai<aj)那么我们称(ai,aj)为一个顺序对，且该顺序对的权值为(aj-ai)。该1-N的排列的权值那么为其所有顺序对的权值之和。任务求出权值和最大的1-N的排列。2024/6/2郁闷的Q输入文件一个正整数N输出文件一个数，最大权值和。2024/6/2郁闷的Q样例输入 4样例输出

10数据约定30%N<=1260%N<=30 100%N<=402024/6/2试题特点根本都是改编自历年NOIP试题难度适中思维巧妙2024/6/2模拟试题二工件处理 Job山顶问题 Peaks生成树 Tree黑白三角形 Triangle输入输出统一为文件名.in/文件名.out时间限制统一为1s2024/6/2工件处理题目描述一个工厂所运行的生产线对每个工件有2道工序A和B，每道工序有一定数量的机器可以实现，分别定义为A类机和B类机。对于每个工件，都必须先经工序A处理，再经工序B处理，而每个机器可以独立的，同时的工作，每个机器工作需要的时间不一样。任务现有N个工件，找出最早的时间让所有工件完成所有工序A和最早时间完成两道工序。2024/6/2工件处理输入文件第一行NM1M2分别为工件数，A类机数量，B类机数量。第二行M1个整数描述了每个A类机处理任一个工件的时间。第三行M2个整数描述了每个B类机处理任一个工件的时间。输出文件一行包含两个整数，分别是最早的时间让所有的工件完成工序A作与最早的时间完成两道工序。2024/6/2工件处理样例输入52311134样例输出35数据约定60%N<=10001<=M1,M2<=30T<=20Ans<=maxint100%N<=1000001<=M1,M2<=5000T<=10000Ans<=maxlongint评分方式此题有局部分，对于每一个测试点，假设你仅有第一个输出正确那么得40%分数，假设你仅有第二个输出正确那么得60%分数，假设你两个输出均正确那么得100%分数，否那么不得分。2024/6/2解法贪心对于子问题A，我们可以每次选择使添加任务后时间最小的机器来处理，直至安排完N个工件。这样的话，子问题A的解是最优的。对于子问题B，可以认为只要一有半成品完成就将其加工为成品，所以方法是记录子问题A的安排次数，构建数组纪录某时间半成品完成的数目，并依此从时间上由1到最后一个半成品出炉，选择当前最优(添加任务后时间最小且当前最空闲，即当前状态下时间最少)的B类机器加工。这个方法是较优的，在数据较小时是最优的。问题之所在，是子问题A的解是最优的，但子问题A的安排次数不一定是最优的。因为子问题A的解仅仅与最多耗时有关，在最多耗时不变的情况下，可能有多种可能。2024/6/2解法？2024/6/2山顶问题题目描述话说某某在cj校运会上异军突起，其实不是偶然，而是有历史原因的。时光回溯到XX年前，某某为了心中的理想，每天爬N里山路上学。直到有一天mlj〔也就是战神Mars〕来到这里，被某某所打动，于是决定帮某某一把。从某某家到学校中间的这N里山路在一条直线上，第i里山路的海拔高度为Hi，如果一段相同高度的山路两边都比它低或者是山的边界，那么这段山路将被称之为“山顶”。mlj想这连绵起伏的山路爬着多累啊，于是他决定动用神力，降低某些山路的海拔高度使得山顶的个数不超过K。但mlj不想做得太明显而被某某发现，于是他求助于你。任务请求出要使“山顶”的数目不超过k，所有山路降低的高度之和至少是多少。2024/6/2山顶问题输入文件第一行两个正整数NK。接下来一行N个正整数Hi。输出文件一个数，最小的所有山路减少的高度之和。2024/6/2样例输入121123332132212样例输出5样例解释*************************123332132212这是之前山的形状，有3个山顶。***-*****----************123332111111这是mlj用了神力之后〔‘-’表示被mlj的神力OOXX掉了〕，只剩下一个山顶。数据约定100%K<=251<=Hi<=100000090%N<=1000100%N<=1000002024/6/2解法2024/6/2生成树题目描述对于无向图G,它的任一棵生成树T的权值P(t)定义为T的所有边权的最大公约数。任务对于给定的图G，求出其所有生成树T1,T2……的权值P(T1),P(T2)……的最小公倍数。2024/6/2生成树输入文件第一行NM表示图G的点数，边数。接下来M行SiTiDi描述一条边〔Si,Ti〕权值为Di。保证图连通，无自环。输出文件一个数，所有生成树权值的最小公倍数。2024/6/2生成树样例输入33122233136样例输出6样理解释有3棵生成树，权值分别为1,2,3,它们的最小公倍数为6。数据约定20%M=N-130%M=N100%N<=1000M<=100000Di<=2^15-1Ans<=2^64-1保证极限数据很少。2024/6/2解法2024/6/2黑白三角形题目描述一天，mlj在平面上画了N个黑点和N个白点，按以下方式来连边，构成一个有向完全图。1. IJ同色，随机选择I→J或J→I2. IJ异色，假设Dij>D，那么白点→黑点，否那么黑点→白点这里的Dij指的是曼哈顿〔|xi-xj|+|yi-yj|)，D为给定值然后，mlj发现有很多三角形很漂亮，漂亮三角形的定义如下：1. 三个顶点IJK颜色不完全相同2. 它们之间的连的边是I→JJ→KK→I〔至于为什么mlj觉得这样漂亮，大概是火星人审美观与众不同吧〕mlj想知道这里面漂亮三角形的个数，但他视力很差，于是求助于你。任务求出漂亮三角形最少有多少个，最多有多少个。2024/6/2黑白三角形输入文件 第一行两个正整数ND 接下来N行XiYi描述第i个白点的坐标 再接下来N行XjYj描述第j个黑点的坐标输出文件 两个数依次为漂亮三