Noip考前冲刺-考试练习

《Noip考前冲刺-考试练习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP考前冲刺--考试练习武森ronaldosen@gmail.com2021/7/22模拟试题一胖胖的陶陶tao懒懒的多多duo笨笨的金明ming郁闷的QQ输入输出统一为文件名.in/文件名.out时间限制统一为1s2021/7/22胖胖的陶陶题目描述陶陶家的院子里有一棵苹果树，每到秋天树上就会结出N个苹果，第i个苹果离地面高度为ai。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有M个板凳，第i个板凳的高度为bi，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。不过请注意，因为陶陶最近长胖了，所以每个板凳只能用一次。任务

2、陶陶把手伸直的时候能够达到的最大高度为H，站在第i个板凳上时能够达到的最大高度为H+bi，请帮陶陶算一下她够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。2021/7/22胖胖的陶陶输入文件第一行三个正整数NMH第二行N个正整数ai第三行M个正整数bi输出文件一个数，最多摘到的苹果的数目。2021/7/22胖胖的陶陶样例输入422235714样例输出3数据约定60%N,M<=1000100%N,M<=1000001<=ai,bi,H<=100002021/7/22解法贪心将苹果的高度按照从低到高的顺序排序。将梯子的高度按照

3、从低到高的顺序排序。一直如果淘淘站在梯子i上够不到苹果j，则淘淘站在梯子i上也够不到苹果j+1.所以淘淘只能用梯子i+1去尝试.以此类推。。。2021/7/22懒懒的多多题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了N堆，第i堆果子重量为wi，坐标为(xi,yi)。多多决定把所有的果子合成一堆。每一次，多多可以把第i堆果子移至第j堆，消耗的体力为wi*(

4、xi-xj

5、+

6、yi-yj

7、)，这样两堆果子就合并成一堆了。可以看出，所有的果子经过N-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗

8、的体力等于每次合并所耗体力之和。因为多多很懒，所以他不想消耗太多的体力。任务请问将所有果子合并成一堆消耗的总体力最少是多少。2021/7/22懒懒的多多输入文件第一行N。接下来N行xiyiwi。输出文件一个数，最少消耗的体力和。2021/7/22懒懒的多多样例输入4211123312242样例输出14数据约定60%N<=1000100%N<=1000001<=xi,yi,wi,Ans<=maxlongint且为整数2021/7/22解法根据体力耗费公式易知

9、xi-xj

10、+

11、yi-yj

12、+

13、xj-xk

14、+

15、yj-yk

16、>=

17、xi

18、-xk

19、+

20、yi-yk

21、则为了使的体力耗费最少，每次将两堆合并的时候，将最终目标作为一个合并对象较优。则枚举最终合并的目标地点，并且计算体力耗费值即可。2021/7/22笨笨的金明题目描述金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过M元钱就行”。今天一早，金明就开始做预算了。金明一共想买N件物品，第i件物品价格为c[i]，重要度为w[i]。物品1可以直接购买，其余的物品均从属于一个主件p[i]，必须

22、要先购买p[i]才能购买i（即构成一棵以1为根的树）。金明想要让所购买的物品重要度之和尽量大，但因为他是个笨小孩，所以求助于聪明的你。任务求出在购买物品总价格不超过M元（可以等于M元）的前提下，所购买物品的重要度之和最大为多少。2021/7/22笨笨的金明输入文件第一行NM。接下来N行piciwi（p1=0）。保证输入数据构成一棵树。输出文件一个数，最大的重要度之和。2021/7/22笨笨的金明样例输入57013155142324313样例输出9数据约定70%N,M<=666100%N,M<=50001<=ci<=M1<=wi

23、<=10000且为整数2021/7/22解法白板2021/7/22郁闷的Q题目描述对于一个1-N的排列，第i个数为ai，若对于1<=I,j<=N满足(i

24、题特点基本都是改编自历年NOIP试题难度适中思维巧妙2021/7/22模拟试题二工件处理Job山顶问题Peaks生成树Tree黑白三角形Triangle输入输出统一为文件名.in/文件名.out时间限制统一为1s2021/7/22工件处理题目描述一个工厂所运行的生产线对每个工