NOIP2016普及組復賽試題講解c版本[通用]

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

2、g namespace std;int main()long n,i,s,mins=100000000;/n鉛筆數量，i循環(huán)變量，s費用，mins最小費用 long c4,p4;/三種鉛筆的數量和價格 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題 “回文日期”簡述牛牛習慣用8位數字表示一個日期，其中，前4位代表年份，接下來2位代表月 份，最后2位代表日期。顯然：一個日期只有一種表示方法，而

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

4、構造出相應的年份第三步：判斷這個年份和日期在不在區(qū)間內例如：8月15日，日期寫成0815 對應回文的年份是：5180年判斷51800815這一天在不在（指定的起始日期）到（指定的終止日期）之間程序時間復雜度為O(366)5主程序#includeusing namespace std;int main()long i,j,y,m,d,t,date1,date2,sum=0;/i,j循環(huán)變量，y對應日期,m月倒置的數值,d日倒置的數值long ms13=0,31,29,31,30,31,30,31,31,30,31,30,31; cindate1date2;/輸入起始結束日期 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+;/判斷這個日期在不在查詢范圍內 coutsumendl; return 0;7確定解題思路（解法2）如果從日期入手，一天一天往上加，每一天都要判斷是不是合法的日期，是不是回文。容易出錯，遇到極限數據還會超時題目里還有更重要的一點是“回文”位數是確定的，八位，很容易“組合”例如：2014，可以組成 20144102我們只要判斷20144102是不是合法的日期就可以了就算年份的范圍是 10009999，也只要計算9000次就可以了8程序框架輸入數據fo

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

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

8、的一段時間的統(tǒng)計結果。從數據結構的角度看，是“隊列”：先進先出所有 ki之和=300000，也就是總人數少于30萬隊列中記錄時間和國籍，到達的入隊，超過86400秒的出隊，時間復雜度 O(kt) 如何統(tǒng)計“總共有多少個不同的數” 呢？1=Xi,j=100000 ，當然用Hash (桶)12數據結構隊列：用數組qt：時間，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、法師認為，當且僅當四個編號為a,b,c,d的魔法物品滿足Xa Xb Xc Xd，Xb-Xa=2(Xd-Xc)，并且Xb-Xa(Xc-Xb)/3時，這四個魔法物品形成了一個魔法陣，他稱這四個魔法物品分別為這個魔法陣的A物品，B物品，C物品，D物品。現在，大魔法師想要知道，對于每個魔法物品，作為某個魔法陣的A物品出現的次數，作為B物品的次數，作為C物品的次數，和作為D物品的次數。15確定解題思路【分析】壓軸題，當然要難這題幾乎是個數學題首先要會畫“線段圖”其次，“加法原理”“乘法原理”要熟練最后，是“膽大心細”編程能力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的長度不會超過全長的九分之一17確定解題思路2乘法原理：如果魔法值為A的物品有Ya個，B的有Yb個，C的有Yc個，那么，D中的一個物品作為D物品的次數是多少呢？根據乘法原理，次數=YaYbYc對于A,B,C,D的做法是一樣的18確定解題思路3數據范圍：1=n=15000 1=m=40000直接求解，連O(n2) 的算法都不能用極限的情況下n=15000，m=40000，說明有很多數據是重復的，可以