1、2015海曙區(qū)中小學(xué)生計(jì)算機(jī)奧賽解題報(bào)告1. 抗戰(zhàn)閱兵(parade.pas/c/cpp)【問題描述】2015年9月3日，是首個(gè)決定放假的抗戰(zhàn)勝利紀(jì)念日。為隆重紀(jì)念中國(guó)人民抗日戰(zhàn)爭(zhēng)暨世界反法西斯戰(zhàn)爭(zhēng)勝利70周年，在9月3日當(dāng)天，在天安門廣場(chǎng)舉行了規(guī)模宏大的閱兵儀式。當(dāng)天全國(guó)放假一天，以便全國(guó)人民能夠觀看閱兵儀式的盛況，為我們偉大的祖國(guó)喝彩。這一天，小NN終于可以擺脫繁重的課業(yè)壓力，在家里認(rèn)真的觀看閱兵儀式。他發(fā)現(xiàn)，閱兵儀式是由很多個(gè)方陣組成（方陣是矩形），長(zhǎng)寬一般固定是25*14，外加兩個(gè)領(lǐng)隊(duì)的將軍?，F(xiàn)在，小NN想要知道，如果每個(gè)方陣的長(zhǎng)寬以及將軍的人數(shù)不固定的時(shí)候，所有方陣的總?cè)藬?shù)是多少，平

2、均每個(gè)方陣有多少人?！据斎搿康谝恍幸粋€(gè)整數(shù)N，表示方陣的個(gè)數(shù)。接下來N行，每行3個(gè)正整數(shù)a，b，c，中間用一個(gè)空格隔開，a和b分別表示方陣的長(zhǎng)和寬，c表示領(lǐng)隊(duì)的將軍數(shù)量。【輸出】輸出有兩行，第一行是一個(gè)整數(shù)，表示所有方陣的總?cè)藬?shù)，第二行是一個(gè)實(shí)型（四舍五入到2位小數(shù)），表示平均每個(gè)方陣的人數(shù)?！据斎胼敵鰳永?】parade.inparade.out23 4 32 5 12613.00【樣例1解釋】 第一個(gè)方陣有3*4+3=15人，第二個(gè)方陣有2*5+1=11人?！据斎胼敵鰳永?】parade.inparade.out210 10 27 8 115979.50【樣例2解釋】第一個(gè)方陣有10*10

3、+2=102人，第二個(gè)方陣有7*8+1=57人?！緮?shù)據(jù)范圍】 50%的數(shù)據(jù)，1=a,b=10。100%的數(shù)據(jù)，N=100，1=a,b=50,1=c=3。Readln(n);For i:=1 to n doBegin Readln(a,b,c); S:=s+a*b+c;End;Writeln(s);Writeln(s/n:0:2);End.2. 摘蘋果(apple.pas/c/cpp)【問題描述】秋天到了，小NN所在的學(xué)校組織小朋友們?nèi)デ镉?。這次他們?nèi)サ牡胤绞且粋€(gè)果園，果園里有很多很多的果樹。由于小NN和他的小伙伴們總共N個(gè)人最喜歡吃蘋果，所以他們都跑到了一棵蘋果樹下，這棵蘋果樹總共結(jié)出了M個(gè)蘋

4、果，管理果園的叔叔允許小朋友們自己摘蘋果吃。但是現(xiàn)在問題來了，每個(gè)蘋果都有一個(gè)固定的高度。每個(gè)小朋友每次跳躍高度也都是一個(gè)固定值（跳一次花費(fèi)的體力等于這個(gè)高度值），只要他們的跳躍高度大于等于某個(gè)蘋果的高度的時(shí)候，就可以把那個(gè)蘋果摘下來，跳一次最多只能摘一個(gè)蘋果。由于小朋友們還小，體力上可能跟不上，所以規(guī)定每個(gè)小朋友最多只能跳一次。現(xiàn)在小NN和他的小伙伴想要知道最少需要花費(fèi)多少的體力才能將這些蘋果全部摘完，現(xiàn)在請(qǐng)你來幫助他們吧?！据斎搿康谝恍袃蓚€(gè)正整數(shù)N和M，分別表示小朋友的數(shù)量和蘋果的數(shù)量。第二行N個(gè)正整數(shù)，兩個(gè)整數(shù)間用一個(gè)空格分開，第i個(gè)數(shù)Hi表示第i個(gè)小朋友的跳躍高度。第三行M個(gè)正整數(shù)，兩

5、個(gè)整數(shù)間用一個(gè)空格分開，第i個(gè)數(shù)Pi表示第i個(gè)蘋果的高度?！据敵觥咳绻軌蛘晁械奶O果，就輸出最小的體力花費(fèi)，如果不能摘完，就輸出“Bad luck”（不包括引號(hào)）?！据斎胼敵鰳永?】apple.inapple.out3 25 3 64 611【樣例解釋】首先讓跳躍高度為5的小朋友去摘高度為4的蘋果，花費(fèi)的體力值是5,然后讓跳躍高度為6的小朋友去摘高度為6個(gè)蘋果，花費(fèi)的體力值是6，所以總共花費(fèi)體力值11?！据斎胼敵鰳永?】apple.inapple.out3 34 2 33 3 4Bad luck【樣例解釋】由于是3個(gè)小朋友摘3個(gè)蘋果，第2個(gè)小朋友的跳躍高度不足以摘到任何一個(gè)蘋果，所以不能摘

6、下所有的蘋果。【數(shù)據(jù)范圍】60%的數(shù)據(jù)，1=N,M=1000，1=Hi,Pi=1000。100%的數(shù)據(jù)，1=N,M=, 1=Hi,Pi=。貪心 兩組數(shù)據(jù)按照從小到大排序，用最小的人，配最小的樹，當(dāng)然人的高度要大于等于樹的高度。最后看2個(gè)下標(biāo)，i爆掉還是j爆掉。滿分要快排。核心代碼 i:=1; j:=1; while (i=n)and(j=bj then begin ans:=ans+a; inc(i); inc(j); end else inc(i); end; if jm then writeln(ans) else writeln(you lie);end.3. 奇怪排列(sort.pas

7、/c/cpp)【問題描述】小NN是一個(gè)活潑好動(dòng)的小朋友，他特別喜歡上體育課，他喜歡的運(yùn)動(dòng)項(xiàng)目有很多，比如跑步、打籃球、踢毽子等等，所以每次上體育課的時(shí)候他都特別的開心。班里有N個(gè)學(xué)生，學(xué)生的編號(hào)從1-N編號(hào)，男生的學(xué)號(hào)恰好都是偶數(shù)，女生的學(xué)號(hào)恰好都是奇數(shù)。體育課一開始，體育老師就讓小朋友們把隊(duì)伍排成一條直線，并且為了防止小朋友們竊竊私語，老師要求男生和女生必須交錯(cuò)排列，既不能同時(shí)讓兩個(gè)女生站在一起，也不能同時(shí)讓兩個(gè)男生站在一起。由于小NN是一個(gè)非常擅于思考的學(xué)生，他很想知道這樣的排法有多少種，現(xiàn)在請(qǐng)你來幫助他吧?！据斎搿枯斎胫挥幸恍幸粋€(gè)正整數(shù)N，表示學(xué)生的數(shù)量?！据敵觥枯敵雠帕械目倲?shù)?！据斎胼?/p>

8、出樣例1】sort.insort.out22【樣例解釋】由于只有兩個(gè)學(xué)生，學(xué)號(hào)1和2，分別是一個(gè)女生和一個(gè)男生，所以只有兩種排法，要么是12，要么是21。【輸入輸出樣例2】sort.insort.out32【樣例解釋】由于是兩個(gè)女生一個(gè)男生（女生是1和3，男生是2），只能是123或者321?！緮?shù)據(jù)范圍】70%的數(shù)據(jù)，N=10。100%的數(shù)據(jù)，N=40。70分算法暴力搜索，遞歸回溯算法，枚舉全排列procedure try(c:integer);var i:integer;begin if c=n+1 then begin /相鄰位不同奇偶性 inc(ans); exit; end; /回溯 e

9、nd;end;begin readln(n); try(1); writeln(ans);end.另一種70分遞推算法男生的全排列*女生的全排列,判斷奇偶性，偶數(shù)還要乘二100分算法:遞推算法的基礎(chǔ)上，寫個(gè)高乘單的高精度乘法。 for i:=1 to b do begin for j:=1 to s0 do begin sj:=sj*i+jw; jw:=sj div 10; sj:=sj mod 10; end; while jw0 do begin inc(s0); ss0:=jw mod 10; jw:=jw div 10; end;4. 畫圈圈（初中生做，小學(xué)生不做）【輸入】第一行一個(gè)正

10、整數(shù)N，表示圓的數(shù)量。第二行有N個(gè)正整數(shù)，第i個(gè)數(shù)Xi，表示第i個(gè)圓的水平位置。第三行有N個(gè)正整數(shù)，第i個(gè)數(shù)Ri，表示第i個(gè)圓的半徑?！据敵觥枯敵鍪Ｓ鄨A的最大總面積（結(jié)果四舍五入到整數(shù)）。【輸出輸出樣例1】circle.incircle.out25 33 328【樣例解釋】由于兩個(gè)圓相交了，只能取一個(gè)?！据敵鲚敵鰳永?】circle.incircle.out23 1310 1314【樣例解釋】 由于小圓被大圓遮住了，所以留下大圓是最優(yōu)選擇?！緮?shù)據(jù)范圍】60%的數(shù)據(jù)，N=20。100%的數(shù)據(jù)，N=1000，1=Xi,Ridi+1,1-di,1 then exit; t:=0; for i:=1 to xb do t:=t+pi*di,2*di,2; if tans then ans:=t; exit; end;滿分算法思想：這道題目其實(shí)就是codevs的線段覆蓋5，只是把數(shù)軸上的線段隱射到圓上。區(qū)間型的dp無疑。首先需要把所有線段根據(jù)右端點(diǎn)升序排序，這樣的話，找與第i條線段不重合的線段j，就只需要往前找一個(gè)線段j，使得j的右端點(diǎn)小于等于i的左端點(diǎn)坐標(biāo)，然后開一個(gè)數(shù)組f進(jìn)行動(dòng)規(guī)