NOIP考前沖刺考試練習(xí)-武森匯總課件

1、NOIP考前沖刺-考試練習(xí)武森ronaldosenNOIP考前沖刺-考試練習(xí)武森2022/10/10模擬試題一胖胖的陶陶tao懶懶的多多duo笨笨的金明ming郁悶的QQ輸入輸出統(tǒng)一為 文件名.in / 文件名.out時間限制統(tǒng)一為1s2022/10/9模擬試題一胖胖的陶陶tao2022/10/10胖胖的陶陶題目描述 陶陶家的院子里有一棵蘋果樹，每到秋天樹上就會結(jié)出N個蘋果，第i個蘋果離地面高度為ai。蘋果成熟的時候，陶陶就會跑去摘蘋果。陶陶有M個板凳，第i個板凳的高度為bi，當(dāng)她不能直接用手摘到蘋果的時候，就會踩到板凳上再試試。不過請注意，因為陶陶最近長胖了，所以每個板凳只能用一次。任務(wù) 陶

2、陶把手伸直的時候能夠達到的最大高度為H，站在第i個板凳上時能夠達到的最大高度為H+bi，請幫陶陶算一下她夠摘到的蘋果的數(shù)目。假設(shè)她碰到蘋果，蘋果就會掉下來。2022/10/9胖胖的陶陶題目描述2022/10/10胖胖的陶陶輸入文件第一行三個正整數(shù) N M H第二行 N個正整數(shù)ai第三行 M個正整數(shù)bi輸出文件一個數(shù)，最多摘到的蘋果的數(shù)目。2022/10/9胖胖的陶陶輸入文件2022/10/10胖胖的陶陶樣例輸入 4 2 2 2 3 5 7 1 4樣例輸出 3數(shù)據(jù)約定 60% N,M=1000 100% N,M=100000 1=ai,bi,H=10000 2022/10/9胖胖的陶陶樣例輸入2

3、022/10/10解法貪心將蘋果的高度按照從低到高的順序排序。將梯子的高度按照從低到高的順序排序。一直如果淘淘站在梯子i上夠不到蘋果j，則淘淘站在梯子i上也夠不到蘋果j+1.所以淘淘只能用梯子i+1去嘗試.以此類推。2022/10/9解法貪心2022/10/10懶懶的多多題目描述 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了N堆，第i堆果子重量為wi，坐標為(xi,yi)。多多決定把所有的果子合成一堆。 每一次，多多可以把第i堆果子移至第j堆，消耗的體力為wi*(|xi-xj|+|yi-yj|)，這樣兩堆果子就合并成一堆了?？梢钥闯?，所有的果子經(jīng)過N-1次合并之后，就

4、只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。 因為多多很懶，所以他不想消耗太多的體力。任務(wù) 請問將所有果子合并成一堆消耗的總體力最少是多少。2022/10/9懶懶的多多題目描述2022/10/10懶懶的多多輸入文件第一行 N。接下來N行 xi yi wi。輸出文件一個數(shù)，最少消耗的體力和。2022/10/9懶懶的多多輸入文件2022/10/10懶懶的多多樣例輸入 4 2 1 1 1 2 3 3 1 2 2 4 2樣例輸出14數(shù)據(jù)約定 60% N=1000 100% N=100000 1=xi,yi,wi,Ans=|xi-xk|+|yi-yk|則為了使的體力耗費最少，每

5、次將兩堆合并的時候，將最終目標作為一個合并對象較優(yōu)。則枚舉最終合并的目標地點，并且計算體力耗費值即可。2022/10/9解法根據(jù)體力耗費公式易知2022/10/10笨笨的金明題目描述 金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過M元錢就行”。今天一早，金明就開始做預(yù)算了。金明一共想買N件物品，第i件物品價格為ci，重要度為wi。物品1可以直接購買，其余的物品均從屬于一個主件pi，必須要先購買pi才能購買i（即構(gòu)成一棵以1為根的樹）。金明想要讓所購買的物品重要度之和盡

6、量大，但因為他是個笨小孩，所以求助于聰明的你。任務(wù)求出在購買物品總價格不超過M元（可以等于M元）的前提下，所購買物品的重要度之和最大為多少。2022/10/9笨笨的金明題目描述2022/10/10笨笨的金明輸入文件第一行 N M。接下來N行 pi ci wi （p1=0）。 保證輸入數(shù)據(jù)構(gòu)成一棵樹。輸出文件一個數(shù)，最大的重要度之和。2022/10/9笨笨的金明輸入文件2022/10/10笨笨的金明樣例輸入 5 7 0 1 3 1 5 5 1 4 2 3 2 4 3 1 3樣例輸出 9數(shù)據(jù)約定70% N,M=666 100% N,M=5000 1=ci=M 1=wi=10000 且為整數(shù)2022

7、/10/9笨笨的金明樣例輸入2022/10/10解法白板2022/10/9解法白板2022/10/10郁悶的Q題目描述 對于一個1-N的排列，第i個數(shù)為ai，若對于1=I,j=N滿足 (ij) and (aiaj) 那么我們稱(ai,aj)為一個順序?qū)?，且該順序?qū)Φ臋?quán)值為(aj-ai)。 該1-N的排列的權(quán)值則為其所有順序?qū)Φ臋?quán)值之和。任務(wù) 求出權(quán)值和最大的1-N的排列。2022/10/9郁悶的Q題目描述2022/10/10郁悶的Q輸入文件一個正整數(shù) N 輸出文件一個數(shù)，最大權(quán)值和。2022/10/9郁悶的Q輸入文件2022/10/10郁悶的Q樣例輸入 4樣例輸出 10數(shù)據(jù)約定30% N=12

8、60% N=30 100% N=402022/10/9郁悶的Q樣例輸入2022/10/10試題特點基本都是改編自歷年NOIP試題難度適中思維巧妙2022/10/9試題特點基本都是改編自歷年NOIP試題2022/10/10模擬試題二工件處理Job山頂問題Peaks生成樹Tree黑白三角形Triangle輸入輸出統(tǒng)一為 文件名.in / 文件名.out時間限制統(tǒng)一為1s2022/10/9模擬試題二工件處理Job2022/10/10工件處理題目描述 一個工廠所運行的生產(chǎn)線對每個工件有2道工序A和B，每道工序有一定數(shù)量的機器可以實現(xiàn)，分別定義為A類機和B類機。 對于每個工件，都必須先經(jīng)工序A處理，再經(jīng)

9、工序B處理，而每個機器可以獨立的，同時的工作，每個機器工作需要的時間不一樣。任務(wù)現(xiàn)有N個工件，找出最早的時間讓所有工件完成所有工序A和最早時間完成兩道工序。2022/10/9工件處理題目描述2022/10/10工件處理輸入文件第一行 N M1 M2 分別為工件數(shù)，A類機數(shù)量，B類機數(shù)量。第二行 M1個整數(shù)描述了每個A類機處理任一個工件的時間。第三行 M2個整數(shù)描述了每個B類機處理任一個工件的時間。輸出文件一行包含兩個整數(shù)，分別是最早的時間讓所有的工件完成工序A作與最早的時間完成兩道工序。2022/10/9工件處理輸入文件2022/10/10工件處理樣例輸入5 2 31 1 1 3 4樣例輸出3

10、 5數(shù)據(jù)約定 60% N=1000 1=M1,M2=30 T=20 Ans=maxint 100% N=100000 1=M1,M2=5000 T=10000 Ans=maxlongint評分方式本題有部分分，對于每一個測試點，若你僅有第一個輸出正確則得40%分數(shù)，若你僅有第二個輸出正確則得60%分數(shù)，若你兩個輸出均正確則得100%分數(shù)，否則不得分。2022/10/9工件處理樣例輸入2022/10/10解法貪心對于子問題A，我們可以每次選擇使添加任務(wù)后時間最小的機器來處理，直至安排完N個工件。這樣的話，子問題A的解是最優(yōu)的。對于子問題B，可以認為只要一有半成品完成就將其加工為成品，所以方法是記

11、錄子問題A的安排次數(shù)，構(gòu)建數(shù)組紀錄某時間半成品完成的數(shù)目，并依此從時間上由1到最后一個半成品出爐，選擇當(dāng)前最優(yōu)(添加任務(wù)后時間最小且當(dāng)前最空閑，即當(dāng)前狀態(tài)下時間最少)的B類機器加工。這個方法是較優(yōu)的，在數(shù)據(jù)較小時是最優(yōu)的。問題之所在，是子問題A的解是最優(yōu)的，但子問題A的安排次數(shù)不一定是最優(yōu)的。因為子問題A的解僅僅與最多耗時有關(guān)，在最多耗時不變的情況下，可能有多種可能。2022/10/9解法貪心2022/10/10解法？2022/10/9解法？2022/10/10山頂問題題目描述 話說某某在cj校運會上異軍突起，其實不是偶然，而是有歷史原因的。 時光回溯到XX年前，某某為了心中的理想，每天爬N里

12、山路上學(xué)。直到有一天mlj（也就是戰(zhàn)神Mars）來到這里，被某某所打動，于是決定幫某某一把。從某某家到學(xué)校中間的這N里山路在一條直線上，第i里山路的海拔高度為Hi，如果一段相同高度的山路兩邊都比它低或者是山的邊界，那么這段山路將被稱之為“山頂”。mlj想這連綿起伏的山路爬著多累啊，于是他決定動用神力，降低某些山路的海拔高度使得山頂?shù)膫€數(shù)不超過K。但mlj不想做得太明顯而被某某發(fā)現(xiàn)，于是他求助于你。任務(wù) 請求出要使“山頂”的數(shù)目不超過k，所有山路降低的高度之和至少是多少。2022/10/9山頂問題題目描述2022/10/10山頂問題輸入文件第一行兩個正整數(shù) N K。接下來一行N個正整數(shù)Hi。輸出

13、文件一個數(shù)，最小的所有山路減少的高度之和。2022/10/9山頂問題輸入文件2022/10/10樣例輸入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用了神力之后（-表示被mlj的神力OOXX掉了），只剩下一個山頂。數(shù)據(jù)約定100% K=25 1=

14、Hi=100000090% N=1000 100% N=1000002022/10/9樣例輸入2022/10/10解法2022/10/9解法2022/10/10生成樹題目描述 對于無向圖G,它的任一棵生成樹T的權(quán)值P(t)定義為T的所有邊權(quán)的最大公約數(shù)。任務(wù) 對于給定的圖G，求出其所有生成樹T1,T2的權(quán)值P(T1),P(T2)的最小公倍數(shù)。2022/10/9生成樹題目描述2022/10/10生成樹輸入文件第一行 N M 表示圖G的點數(shù)，邊數(shù)。接下來M行 Si Ti Di 描述一條邊（Si,Ti）權(quán)值為 Di。 保證圖連通，無自環(huán)。輸出文件一個數(shù)，所有生成樹權(quán)值的最小公倍數(shù)。2022/10/9

15、生成樹輸入文件2022/10/10生成樹樣例輸入 3 31 2 2 2 3 3 1 3 6樣例輸出6樣理解釋 有3棵生成樹，權(quán)值分別為1,2,3,它們的最小公倍數(shù)為6。數(shù)據(jù)約定20% M=N-1 30% M=N100% N=1000 M=100000 Di=215-1 AnsD，則白點黑點，否則黑點白點這里的Dij指的是曼哈頓（|xi-xj|+|yi-yj|)，D為給定值然后，mlj發(fā)現(xiàn)有很多三角形很漂亮，漂亮三角形的定義如下：1.三個頂點I J K顏色不完全相同2.它們之間的連的邊是 IJ JK KI（至于為什么mlj覺得這樣漂亮，大概是火星人審美觀與眾不同吧） mlj想知道這里面漂亮三角形的個數(shù)，但他視力很差，于是求助于你。任務(wù)求出漂亮三角形最少有多少個，最多有多少個。2022/10/9黑白三角形題目描述2022/10/10黑白三角形輸入文件 第一行兩個正整數(shù) N D 接下來N行Xi Yi描述第i個白點的坐標 再接下來N行Xj Yj描述第j個黑點的坐標輸出文件 兩個數(shù)依次為漂亮三角形最少的個數(shù)，最多的個數(shù)，中間用一個空格隔開。2022/10/9黑白三角形輸入文件2022/10/10黑