单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,NOIP,考前冲刺,-,考试练习,武森,NOIP考前冲刺-考试练习武森,2024/11/17,模拟试题一,胖胖的陶陶,tao,懒懒的多多duo,笨笨的金明ming,郁闷的QQ,输入输出统一为 文件名,.in/文件名.out,时间限制统一为1s,2023/10/6模拟试题一胖胖的陶陶tao,2024/11/17,胖胖的陶陶,题目描述,陶陶家的院子里有一棵苹果树，每到秋天树上就会结出,N,个苹果，第,i,个苹果离地面高度为,ai,。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有,M,个板凳，第,i,个板凳的高度为,bi,，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。不过请注意，因为陶陶最近长胖了，所以每个板凳只能用一次。,任务,陶陶把手伸直的时候能够达到的最大高度为,H,，站在第,i,个板凳上时能够达到的最大高度为,H+bi,，请帮陶陶算一下她够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。,2023/10/6胖胖的陶陶题目描述,2024/11/17,胖胖的陶陶,输入文件,第一行三个正整数,N M H,第二行 N个正整数ai,第三行 M个正整数bi,输出文件,一个数，最多摘到的苹果的数目。,2023/10/6胖胖的陶陶输入文件,2024/11/17,胖胖的陶陶,样例输入,4 2 2,2 3 5 7,1 4,样例输出,3,数据约定,60%N,M=1000,100%N,M=100000 1=ai,bi,H=10000,2023/10/6胖胖的陶陶样例输入,2024/11/17,解法,贪心,将苹果的高度按照从低到高的顺序排序。,将梯子的高度按照从低到高的顺序排序。,一直如果淘淘站在梯子,i上够不到苹果j，则淘淘站在梯子i上也够不到苹果j+1.,所以淘淘只能用梯子i+1去尝试.,以此类推。,2023/10/6解法贪心,2024/11/17,懒懒的多多,题目描述,在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了,N,堆，第,i,堆果子重量为,wi,，坐标为,(xi,yi),。多多决定把所有的果子合成一堆。,每一次，多多可以把第,i,堆果子移至第,j,堆，消耗的体力为,wi*(|xi-xj|+|yi-yj|),，这样两堆果子就合并成一堆了。可以看出，所有的果子经过,N-1,次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。,因为多多很懒，所以他不想消耗太多的体力。,任务,请问将所有果子合并成一堆消耗的总体力最少是多少。,2023/10/6懒懒的多多题目描述,2024/11/17,懒懒的多多,输入文件,第一行,N。,接下来N行 xi yi wi。,输出文件,一个数，最少消耗的体力和。,2023/10/6懒懒的多多输入文件,2024/11/17,懒懒的多多,样例输入,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,k,|+|yi-y,k,|,则为了使的体力耗费最少，每次将两堆合并的时候，将最终目标作为一个合并对象较优。,则枚举最终合并的目标地点，并且计算体力耗费值即可。,2023/10/6解法根据体力耗费公式易知,2024/11/17,笨笨的金明,题目描述,金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过M元钱就行”。,今天一早，金明就开始做预算了。金明一共想买N件物品，第i件物品价格为ci，重要度为wi。物品1可以直接购买，其余的物品均从属于一个主件pi，必须要先购买pi才能购买i（即构成一棵以1为根的树）。,金明想要让所购买的物品重要度之和尽量大，但因为他是个笨小孩，所以求助于聪明的你。,任务,求出在购买物品总价格不超过M元（可以等于M元）的前提下，所购买物品的重要度之和最大为多少。,2023/10/6笨笨的金明题目描述,2024/11/17,笨笨的金明,输入文件,第一行,N M。,接下来N行 pi ci wi（p1=0）。,保证输入数据构成一棵树。,输出文件,一个数，最大的重要度之和。,2023/10/6笨笨的金明输入文件,2024/11/17,笨笨的金明,样例输入,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/10/6笨笨的金明样例输入,2024/11/17,解法,白板,2023/10/6解法白板,2024/11/17,郁闷的Q,题目描述,对于一个1-N的排列，第i个数为ai，若对于1=I,j=N满足,(ij)and(aiaj),那么我们称(ai,aj)为一个顺序对，且该顺序对的权值为(aj-ai)。,该1-N的排列的权值则为其所有顺序对的权值之和。,任务,求出权值和最大的1-N的排列。,2023/10/6郁闷的Q题目描述,2024/11/17,郁闷的Q,输入文件,一个正整数,N,输出文件,一个数，最大权值和。,2023/10/6郁闷的Q输入文件,2024/11/17,郁闷的Q,样例输入,4,样例输出,10,数据约定,30%N=12,60%N=30,100%N=40,2023/10/6郁闷的Q样例输入,2024/11/17,试题特点,基本都是改编自历年,NOIP试题,难度适中,思维巧妙,2023/10/6试题特点基本都是改编自历年NOIP试题,2024/11/17,模拟试题二,工件处理,Job,山顶问题Peaks,生成树Tree,黑白三角形Triangle,输入输出统一为 文件名,.in/文件名.out,时间限制统一为1s,2023/10/6模拟试题二工件处理Job,2024/11/17,工件处理,题目描述,一个工厂所运行的生产线对每个工件有2道工序A和B，每道工序有一定数量的机器可以实现，分别定义为A类机和B类机。,对于每个工件，都必须先经工序A处理，再经工序B处理，而每个机器可以独立的，同时的工作，每个机器工作需要的时间不一样。,任务,现有N个工件，找出最早的时间让所有工件完成所有工序A和最早时间完成两道工序。,2023/10/6工件处理题目描述,2024/11/17,工件处理,输入文件,第一行,N M1 M2 分别为工件数，A类机数量，B类机数量。,第二行 M1个整数描述了每个A类机处理任一个工件的时间。,第三行 M2个整数描述了每个B类机处理任一个工件的时间。,输出文件,一行包含两个整数，分别是最早的时间让所有的工件完成工序,A作与最早的时间完成两道工序。,2023/10/6工件处理输入文件,2024/11/17,工件处理,样例输入,5 2 3,1 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%分数，若你仅有第二个输出正确则得60%分数，若你两个输出均正确则得100%分数，否则不得分。,2023/10/6工件处理样例输入,2024/11/17,解法,贪心,对于子问题,A，我们可以每次选择使添加任务后时间最小的机器来处理，直至安排完N个工件。这样的话，子问题A的解是最优的。对于子问题B，可以认为只要一有半成品完成就将其加工为成品，所以方法是记录子问题A的安排次数，构建数组纪录某时间半成品完成的数目，并依此从时间上由1到最后一个半成品出炉，选择当前最优(添加任务后时间最小且当前最空闲，即当前状态下时间最少)的B类机器加工。这个方法是较优的，在数据较小时是最优的。问题之所在，是子问题A的解是最优的，但子问题A的安排次数不一定是最优的。因为子问题A的解仅仅与最多耗时有关，在最多耗时不变的情况下，可能有多种可能。,2023/10/6解法贪心,2024/11/17,解法,？,2023/10/6解法？,2024/11/17,山顶问题,题目描述,话说某某在cj校运会上异军突起，其实不是偶然，而是有历史原因的。,时光回溯到XX年前，某某为了心中的理想，每天爬N里山路上学。直到有一天mlj（也就是战神Mars）来到这里，被某某所打动，于是决定帮某某一把。从某某家到学校中间的这N里山路在一条直线上，第i里山路的海拔高度为Hi，如果一段相同高度的山路两边都比它低或者是山的边界，那么这段山路将被称之为“山顶”。mlj想这连绵起伏的山路爬着多累啊，于是他决定动用神力，降低某些山路的海拔高度使得山顶的个数不超过K。但mlj不想做得太明显而被某某发现，于是他求助于你。,任务,请求出要使“山顶”的数目不超过k，所有山路降低的高度之和至少是多少。,2023/10/6山顶问题题目描述,2024/11/17,山顶问题,输入文件,第一行两个正整数,N K。,接下来一行N个正整数Hi。,输出文件,一个数，最小的所有山路减少的高度之和。,2023/10/6山顶问题输入文件,2024/11/17,样例输入,12 1,1 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用了神力之后（-表示被mlj的神力OOXX掉了），只剩下一个山顶。,数据约定,100%K=25 1=Hi=1000000,90%N=1000,100%N=100000,2023/10/6样例输入,2024/11/17,解法,2023/10/6解法,2024/11/17,生成树,题目描述,对于无向图G,它的任一棵生成树T的权值P(t)定义为T的所有边权的最大公约数。,任务,对于给定的图G，求出其所有生成树T1,T2的权值P(T1),P(T2)的最小公倍数。,2023/10/6生成树题目描述,2024/11/17,生成树,输入文件,第一行,N M 表示图G的点数，边数。,接下来M行 Si Ti Di 描述一条边（Si,Ti）权值为 Di。,保证图连通，无自环。,输出文件,一个数，所有生成树权值的最小公倍数。,2023/10/6生成树输入文件,2024/11/17