1、NOIP2016普及組復(fù)賽題解NOIP2016普及組C+借鑒百度文庫PASCAL版本：https:/ “買鉛筆”簡述P老師需要去商店買n支鉛筆作為小朋友們參加NOIP的禮物。她發(fā)現(xiàn)商店一共有 3種包裝的鉛筆，不同包裝內(nèi)的鉛筆數(shù)量有可能不同，價(jià)格也有可能不同。為了公平起 見，P老師決定只買同一種包裝的鉛筆。商店不允許將鉛筆的包裝拆開，因此P老師可能需要購買超過n支鉛筆才夠給小朋 友們發(fā)禮物?，F(xiàn)在P老師想知道，在商店每種包裝的數(shù)量都足夠的情況下，要買夠至少n支鉛筆最少需要花費(fèi)多少錢?【分析】送分題，數(shù)據(jù)量少，直接模擬即可。當(dāng)然，“小心撐得萬年船”，“大意失荊州”2例程 C+#includeusin

2、g namespace std;int main()long n,i,s,mins=100000000;/n鉛筆數(shù)量，i循環(huán)變量，s費(fèi)用，mins最小費(fèi)用 long c4,p4;/三種鉛筆的數(shù)量和價(jià)格 cinn;for (i=1;icipi;if(n%ci=0) s=n/ci*pi;/正好整包 else s=(n/ci+1)*pi;/有多余，再來一包 if(minss) mins=s;/判斷那種買法最省錢 coutmins;return 0;3第2題 “回文日期”簡述牛牛習(xí)慣用8位數(shù)字表示一個(gè)日期，其中，前4位代表年份，接下來2位代表月 份，最后2位代表日期。顯然：一個(gè)日期只有一種表示方法，而

3、兩個(gè)不同的日期的表 示方法不會(huì)相同。牛牛認(rèn)為，一個(gè)日期是回文的，當(dāng)且僅當(dāng)表示這個(gè)日期的8位數(shù)字是回文的?，F(xiàn)在，牛牛想知道：在他指定的兩個(gè)日期之間（包含這兩個(gè)日期本身），有多少個(gè)真實(shí)存在的日期是回文的。一個(gè)8位數(shù)字是回文的，當(dāng)且僅當(dāng)從左向右讀和從右向左是相同的例如：2016年11月19日，表示為20161119，它不是回文的2010年1月2日，表示為20100102，它是回文的。求：在他指定的兩個(gè)日期之間包含這兩個(gè)日期本身），有多少個(gè)真實(shí)存在的日期是回文的。4確定解題思路一年是365天，如果閏年是366天。月日構(gòu)成的數(shù)字最多只有366個(gè)。第一步：構(gòu)造出所有的日期（后四位）第二步：利用回文的規(guī)則，

4、構(gòu)造出相應(yīng)的年份第三步：判斷這個(gè)年份和日期在不在區(qū)間內(nèi)例如：8月15日，日期寫成0815 對(duì)應(yīng)回文的年份是：5180年判斷51800815這一天在不在（指定的起始日期）到（指定的終止日期）之間程序時(shí)間復(fù)雜度為O(366)5主程序#includeusing namespace std;int main()long i,j,y,m,d,t,date1,date2,sum=0;/i,j循環(huán)變量，y對(duì)應(yīng)日期,m月倒置的數(shù)值,d日倒置的數(shù)值long ms13=0,31,29,31,30,31,30,31,31,30,31,30,31; cindate1date2;/輸入起始結(jié)束日期 for (i=1;i

5、=12;i+) m=i%10*10+i/10;/1-12月份倒置之后的值 t=msi; for (j=1;j=date1&y=date2)sum+;/判斷這個(gè)日期在不在查詢范圍內(nèi) coutsumendl; return 0;7確定解題思路（解法2）如果從日期入手，一天一天往上加，每一天都要判斷是不是合法的日期，是不是回文。容易出錯(cuò)，遇到極限數(shù)據(jù)還會(huì)超時(shí)題目里還有更重要的一點(diǎn)是“回文”位數(shù)是確定的，八位，很容易“組合”例如：2014，可以組成 20144102我們只要判斷20144102是不是合法的日期就可以了就算年份的范圍是 10009999，也只要計(jì)算9000次就可以了8程序框架輸入數(shù)據(jù)fo

6、r i=day_start div 10000 / 取年份 =day_end div 10000 /循環(huán)起始到結(jié)束年份if （check(i)） / 判斷i年對(duì)應(yīng)的日期是否符合要求特別注意：還要判斷這個(gè)日期是否在范圍內(nèi)9第3題 “海港”簡述小K按照時(shí)間記錄下了到達(dá)海港的每一艘船只情況；對(duì)于第i艘到達(dá)的船，他記錄了這艘船到達(dá)的時(shí)間ti (單位：秒)，船上的乘客數(shù)量ki，以及每名乘客的國籍 x(i,1), x(i,2),，x(i,k)。小K統(tǒng)計(jì)了n艘船的信息，希望你幫忙計(jì)算出以每一艘船到達(dá)時(shí)間為止的24小時(shí)(24小時(shí)=86400秒）內(nèi)所有乘船到達(dá)的乘客來自多少個(gè)不同的國家。形式化地講，你需要計(jì)算n

7、條信息。對(duì)于輸出的第i條信息，你需要統(tǒng)計(jì)滿足 ti - 86400 tp = ti的船只p，在所有的x(p,j)中，總共有多少個(gè)不同的數(shù)輸出n行，第i行輸出一個(gè)整數(shù)表示第i艘船到達(dá)后的統(tǒng)計(jì)信息。10暴力算法（預(yù)計(jì)分?jǐn)?shù)70分）h100001;hx表示國籍為x的乘客到港的最新時(shí)間。初始值為-86400.sum 100001；sum 1-n表示1-n個(gè)艘船到達(dá)海港對(duì)應(yīng)的國籍?dāng)?shù)量。每一艘船到達(dá)海港，更新對(duì)應(yīng)國籍乘客的到港時(shí)間數(shù)組h統(tǒng)計(jì)所有國籍的到港時(shí)間是否在24小時(shí)內(nèi)，t為當(dāng)前時(shí)間，t-hx86400，表示X國籍滿足條件。時(shí)間復(fù)雜度：O(kt+n*x) 11確定解題思路題目明確告訴我們，要計(jì)算的是中間

8、的一段時(shí)間的統(tǒng)計(jì)結(jié)果。從數(shù)據(jù)結(jié)構(gòu)的角度看，是“隊(duì)列”：先進(jìn)先出所有 ki之和=300000，也就是總?cè)藬?shù)少于30萬隊(duì)列中記錄時(shí)間和國籍，到達(dá)的入隊(duì)，超過86400秒的出隊(duì)，時(shí)間復(fù)雜度 O(kt) 如何統(tǒng)計(jì)“總共有多少個(gè)不同的數(shù)” 呢？1=Xi,j=100000 ，當(dāng)然用Hash (桶)12數(shù)據(jù)結(jié)構(gòu)隊(duì)列：用數(shù)組qt：時(shí)間，qx：國籍int qt300005, qx300005;頭指針: head，尾指針：tailHash表： int hs 100005;13參考程序#include#includeusing namespace std;int const maxn=300005;int qtma

9、xn,qxmaxn;int hs100005;int head=1,tail=1,n,i,j,ti,tic,ki,xi,cnt=0;int main()memset(hs,0,sizeof(hs);cinn;for(i=1;itiki;for(j=1;j=ki;j+) for(j=1;jxi;qttail=ti;qxtail=xi;if (hsxi=0) cnt+;hsxi+;tail+;tic=ti-86400;while(qthead=tic)xi=qxhead;hsxi-;if(hsxi=0) cnt-;head+;coutcntendl;return 0;14第4題 “魔法陣”簡述大魔

10、法師認(rèn)為，當(dāng)且僅當(dāng)四個(gè)編號(hào)為a,b,c,d的魔法物品滿足Xa Xb Xc Xd，Xb-Xa=2(Xd-Xc)，并且Xb-Xa(Xc-Xb)/3時(shí)，這四個(gè)魔法物品形成了一個(gè)魔法陣，他稱這四個(gè)魔法物品分別為這個(gè)魔法陣的A物品，B物品，C物品，D物品?，F(xiàn)在，大魔法師想要知道，對(duì)于每個(gè)魔法物品，作為某個(gè)魔法陣的A物品出現(xiàn)的次數(shù)，作為B物品的次數(shù)，作為C物品的次數(shù)，和作為D物品的次數(shù)。15確定解題思路【分析】壓軸題，當(dāng)然要難這題幾乎是個(gè)數(shù)學(xué)題首先要會(huì)畫“線段圖”其次，“加法原理”“乘法原理”要熟練最后，是“膽大心細(xì)”編程能力16確定解題思路1畫“線段圖”Xa Xb Xc XdXb-Xa=2(Xd-Xc)Xb-Xa(Xc-Xb)3 Xc-Xb6xAD=AB+BC+CD 9x x n div 9也就是說，CD的長度不會(huì)超過全長的九分之一17確定解題思路2乘法原理：如果魔法值為A的物品有Ya個(gè)，B的有Yb個(gè)，C的有Yc個(gè)，那么，D中的一個(gè)物品作為D物品的次數(shù)是多少呢？根據(jù)乘法原理，次數(shù)=YaYbYc對(duì)于A,B,C,D的做法是一樣的18確定解題思路3數(shù)據(jù)范圍：1=n=15000 1=m=40000直接求解，連O(n2) 的算法都不能用極限的情況下n=15000，m=40000，說明有很多數(shù)據(jù)是重復(fù)的，可以