精選文檔寧波2014小學(xué)程序解題分析

寧波市第29屆中小學(xué)生計(jì)算機(jī)程序設(shè)計(jì)競賽復(fù)賽試題（小學(xué)組）比賽時(shí)間：2014年3月29日下午1:30—4:00題目一覽試題名稱小李數(shù)星星小李打臺(tái)球小李發(fā)獎(jiǎng)金小李打怪獸英文代號(hào)starballmoneymonster程序名star.cpp/pas/cball.cpp/pas/cmoney.cpp/pas/cmonster.cpp/pas/c輸入文件名star.inball.inmoney.inmonster.in輸出文件名star.outball.outmoney.outmonster.out內(nèi)存限制128MB128MB128MB128MB時(shí)限1S1S1S1S注意：一、關(guān)于競賽中編程語言使用的規(guī)定參照中國計(jì)算機(jī)學(xué)會(huì)公布的《關(guān)于NOI系列賽編程語言使用限制的規(guī)定》。二、評(píng)測環(huán)境為windows。小李數(shù)星星【題目描述】小李在農(nóng)村長大，那時(shí)候大家喜歡晚飯過后在院子里納涼，聽不懂大人在說什么的小李喜歡抬頭看天空，尤其是夏天的夜晚，天上的星星又多又亮。長大后小李進(jìn)城打工，每當(dāng)想家的時(shí)他還是喜歡抬頭看看天，尋找另一邊故鄉(xiāng)的記憶?？墒谴蟪鞘欣锟諝赓|(zhì)量太差了，霧靈天氣橫行，天上能看到的星星也越來越少了。小李每次用一個(gè)正方形去覆蓋自己所能看到的星星，隨著日子的推移，這個(gè)正方形越來越小了，悲傷的小李希望你能告訴他這個(gè)正方形的面積。為了讓問題變得筒單，小李毎次只會(huì)使用水平放置的正方形來覆蓋（不會(huì)旋轉(zhuǎn)），具體參照樣例解釋。【輸入】第一行一個(gè)整數(shù)n，表示星星的數(shù)量。接下來共n行，每行2個(gè)正整數(shù)(a,b),表示該星星到X軸距離為b，到Y(jié)軸距離為a，這些星星只會(huì)位于X軸的上方，Y軸的右方。輸入數(shù)據(jù)保證存在一個(gè)合法的正方形(面積非零)去覆蓋這些星星【輸出】一個(gè)整數(shù)，表示能覆蓋所有星星的最小正方形的面積。【樣例輸入】3112122【樣例輸出】1【樣例說明】【數(shù)據(jù)規(guī)?！?0%的數(shù)據(jù)，3<=n<=20,1<=x<=100,1<=y<=100100%的數(shù)據(jù)，3<=n<=1000,1<=x<=100000,1<=y<=100000解題思路：首先找到X軸上最大的一個(gè)坐標(biāo)跟最小的一個(gè)坐標(biāo)，我們可以用max1和min1表示，然后找到Y(jié)軸上最大的一個(gè)坐標(biāo)跟最小的一個(gè)坐標(biāo)，我們可以用max2和min2表示，用max1-min1表示X軸上的邊長aa，用max2-min2表示Y軸上的邊長bb,比較aa跟bb的長度，因?yàn)槭钦叫?，所以用較長的計(jì)算面積，這樣可以覆蓋整個(gè)星星的區(qū)域。注意：由于數(shù)據(jù)比較大，所以我們采用int64的數(shù)據(jù)類型，不然就會(huì)出現(xiàn)超范圍的錯(cuò)誤提示。源程序如下：varn,a,b,aa,bb,max1,min1,max2,min2:int64;i:longint;beginassign(input,'star.in');reset(input);assign(output,'star.out');rewrite(output);readln(n);max1:=0;min1:=maxlongint;max2:=0;min2:=maxlongint;fori:=1tondobeginreadln(a,b);ifa>max1thenmax1:=a;ifa<min1thenmin1:=a;ifb>max2thenmax2:=b;ifb<min2thenmin2:=b;end;aa:=max1-min1;bb:=max2-min2;ifaa>bbthenwrite(aa*aa)elsewrite(bb*bb);close(input);close(output);end.小李打臺(tái)球【題目描述】在異鄉(xiāng)打拼的小李同志迷上了一款叫諾斯克的臺(tái)球游戲，而且隨著練習(xí)的深入，他總是能在某些神奇的時(shí)刻開啟外掛模式，此時(shí)小李將指哪打哪，直至無球可打?，F(xiàn)在小李想讓你幫他計(jì)算下當(dāng)他開啟外掛模式的時(shí)候最多可以取得多少分?jǐn)?shù)。注意：臺(tái)面上的球數(shù)經(jīng)常會(huì)異于傳統(tǒng)斯諾克。斯諾克比賽的基本規(guī)則如下：一、彩球共分8種顏色，紅（1分）、黃（2分）、綠（3分）、掠（4分）、藍(lán)（5分）、粉（6分）、黑（7分）、白（主球，控制白球來打其余球二、當(dāng)臺(tái)面上有紅球的時(shí)候你必須先擊打一個(gè)紅球，然后能且只能擊打一個(gè)彩球（不包括紅球），此時(shí)落袋的彩球?qū)?huì)被放回桌面，一直重復(fù)該過程。三、當(dāng)打完規(guī)則二的彩球（不包括紅球）發(fā)現(xiàn)己經(jīng)沒有紅球時(shí)，按照彩球的分值從低到高將其依次擊入袋中?！据斎搿枯斎雰H有一行，共7個(gè)用空格隔開的整數(shù)，分別為當(dāng)前臺(tái)面上紅、黃、綠、掠、藍(lán)、粉、黑球的數(shù)目?！据敵觥枯敵鰞H有一行，共1個(gè)整數(shù)，表示小李可以得到的最高分。【樣例輸入】2 010302【樣例輸出】48【樣例說明】臺(tái)面上共有紅球2個(gè)、綠球1個(gè)、藍(lán)球3個(gè)、黑球2個(gè)，獲得最高分的打法是紅-黑-紅-黑-綠-藍(lán)-藍(lán)-藍(lán)-黑-黑，共可以獲得48分?！緮?shù)據(jù)規(guī)?！勘ＷC最后得分不會(huì)超過231-1。解題思路：這題主要是模擬取球得分的過程，總共七種球，如果有紅色球，那么紅色的個(gè)數(shù)乘以有其他顏色球的最高分得出結(jié)果，再把除紅色球外的其他顏色球按球的數(shù)量乘以分值累加就可以完成。我們?cè)谧x入數(shù)據(jù)完成后可以把七種顏色球中沒有的球排除掉，統(tǒng)計(jì)出球桌上有幾種顏色的存在，如果桌面上只有紅色球，那分?jǐn)?shù)只能得1分。源程序如下：vars,t,i:longint;a:array[1..7]oflongint;beginassign(input,'ball.in');reset(input);assign(output,'ball.out');rewrite(output);fori:=1to7doread(a[i]);t:=7;whilea[t]=0dodec(t);ift=1thens:=1elses:=s+t*a[1]+a[1];fori:=2to7dos:=s+i*a[i];write(s);close(input);close(output);end.

小李發(fā)獎(jiǎng)金【題目描述】當(dāng)然打臺(tái)球只是小李的休閑娛樂活動(dòng)，對(duì)待他的本職工作，他還是非常兢兢業(yè)業(yè)的。但是小李的老板是個(gè)周機(jī)皮，每次都想克扣小李的工資和獎(jiǎng)金，甚至制定出非常奇葩的規(guī)則。又到了每年發(fā)年終獎(jiǎng)的時(shí)候了，今年老板的規(guī)則是這樣的：給你n個(gè)數(shù),每次你可以對(duì)任意一個(gè)數(shù)加1,直到所有的數(shù)都不相等為止，每加一次都要花費(fèi)一定數(shù)額的費(fèi)用。為了小李的幸福生活，聰明的你可否幫助小李，讓他盡量少扣錢。【輸入】第一行n,表示共有n個(gè)數(shù)。第二行共n個(gè)用空格隔開的非負(fù)整數(shù)ai?！据敵觥績H一個(gè)整數(shù)，表示加到讓每個(gè)數(shù)都不相等的最少次數(shù)。【樣例輸入】41132【樣例輸出】3【樣例說明】讓1+1+1+1=4,給定的數(shù)字變成4,1,3,2?！緮?shù)據(jù)規(guī)模】30%的數(shù)據(jù)，1<=n<=1060%的數(shù)據(jù),1<=n<=100080%的數(shù)據(jù),1<=n<=30000,ai<=1000,100%的數(shù)據(jù),1<=n<=30000,ai<=1000000。解題思路：首先我們要了解n個(gè)數(shù)要變成不一樣并且要自動(dòng)加1的話進(jìn)行變化的話，先要對(duì)n個(gè)數(shù)進(jìn)行從小到大的排序，因?yàn)閿?shù)據(jù)比較大，我們可以選擇用快排或者桶排的方法進(jìn)行排序（注意，不能用選擇跟冒泡排序，因?yàn)檫@兩種排序數(shù)據(jù)大會(huì)產(chǎn)生超時(shí)），我這里用的是桶排序，在排序的同時(shí)找到數(shù)據(jù)的最大值跟最小值，作用是不用從1開始，也不用到最后結(jié)束，只要在最小值跟最大值之間（只有桶排序的情況可以這樣）。接下來就是自動(dòng)加1的過程了，如果數(shù)據(jù)只有一個(gè)或沒有，那就不用加1了，如果大于1的，我們就要進(jìn)行自動(dòng)加1的過程了，加的過程統(tǒng)計(jì)加的次數(shù)。源程序如下：vari,a,p,n,q,ans,lmt:longint;f:array[1..1100001]oflongint;beginassign(input,'money.in');reset(input);assign(output,'money.out');rewrite(output);read(n);fori:=1tondobeginread(a);f[a]:=f[a]+1;ifa<pthenp:=a;ifa>lmtthenlmt:=a;end;fori:=ptolmtdobeginifq<=ithenq:=i+1;if(f[i]=1)or(f[i]=0)thencontinue;whilef[i]>1dobeginwhilef[q]<>0doq:=q+1;f[q]:=1;ans:=ans+q-i;f[i]:=f[i]-1;end;end;write(ans);close(input);close(output);end.小李打怪獸【題目描述】小李對(duì)故鄉(xiāng)的思念全部化作了對(duì)霧靈天氣的怨念，這引起了掌控霧靈的邪神的極大不滿，邪神派去了一只小怪獸去對(duì)付小李，由于這只怪獸擁有極高的IQ,它覺得直接消滅小李太沒有難度了，它決定要和小李在智力水平上一較高下。我們可否幫助小李來戰(zhàn)勝強(qiáng)大的怪獸呢？問題是這樣的：給定一堆正整數(shù)，要求你分成兩堆，兩堆數(shù)的和分別為S1和S2,誰分的方案使得S1*S1-S2*S2的結(jié)果?。ㄒ?guī)定S1>=S2),誰就將獲得勝利。注：S2可以等于0?！据斎搿康谝恍衝，表示共有n個(gè)數(shù)第二行共n個(gè)用空格隔開的正整數(shù)ai，表示給定的一堆正整數(shù)?！据敵觥枯敵鼍鸵粋€(gè)整數(shù)，表示S1*S1-S2*S2的最小值?！緲永斎搿?1234【樣例輸出】0【樣例說明】1和4一堆，2和3—堆，5*5-5*5=0【數(shù)據(jù)規(guī)?！?0%的數(shù)據(jù)，1<=n<=2080%的數(shù)據(jù)，1<=n<=50，ai<=20100%的數(shù)據(jù)，1<=n<=100，ai<=100解題分析：這首題就是很典型的0/1背包問題，我們可以用DP(動(dòng)態(tài)規(guī)劃)的方法來做，本問題的數(shù)學(xué)模型如下：設(shè)f(x)表示取的數(shù)不超過x的最大數(shù)，則f(x)=max{f(x-w[i])+v[i]}

最后要兩堆數(shù)相乘后再相減，sqr(f[x])-sqr(s-f[x])源程序如下：vari,x,n,m,s:longint;f:array[0..10000]oflongint;w,v:array[1..10000]oflongint;beginassign(input,'monster.in');reset(input);assign(output,'monster.out');rewrite(output);fillchar(f,sizeof(f),0);readln(n);//讀入數(shù)量fori:=1tondobeginread(w[i]);v[i]:=w[i];s:=s+w[i];end;ifodd(s)thenm:=sdiv2+1//總數(shù)是奇數(shù)，一半+1elsem:=sdiv2;//偶數(shù)