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

《NOIP2016普及組復(fù)賽試題講解c版本[通用]》由會(huì)員分享，可在線閱讀，更多相關(guān)《NOIP2016普及組復(fù)賽試題講解c版本[通用]（20頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),-,*,-,2017.07.28,試題分析,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),NOIP2016,普及組復(fù)賽題解,NOIP2016,普及組,C+,借鑒百度文庫,PASCAL,版本：,https:/ 見，,P,老師決定只買同一種包裝的鉛筆。,商店不允許將鉛筆的包裝拆開，因此,P,老師可能需要購買超過,n,支鉛筆才夠給小朋 友們發(fā)禮物。,現(xiàn)在,P,老師想知道，在商店每種包裝的數(shù)量都足夠的情況下，要買夠至少,n,支鉛筆最少需要花費(fèi)多少錢,?,【,分析,】,送分題，數(shù)據(jù)量

2、少，直接模擬即可。,當(dāng)然，,“,小心撐得萬年船,”,，,“,大意失荊州,”,2,例程,C+,#include,using 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;/,判斷那種買法最省錢,coutdate1date2;/,輸入起始結(jié)束

3、日期,for(i=1;i=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,，可以組成,2014,4102,我們只要判斷,2014,4102,是不是合法的日期就可以了,就算年份的范圍

4、是,10009999,，也只要計(jì)算,9000,次就可以了,8,程序框架,輸入數(shù)據(jù),for 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í)間,t,i,(,單位：秒,),，船上的乘客數(shù)量,k,i,，以及每名乘客的國籍,x(i,1),x(i,2),，,x(i,k),。,小,K,統(tǒng)計(jì)了,

5、n,艘船的信息，希望你幫忙計(jì)算出以每一艘船到達(dá)時(shí)間為止的,24,小時(shí),(24,小時(shí),=86400,秒）內(nèi)所有乘船到達(dá)的乘客來自多少個(gè)不同的國家。,形式化地講，你需要計(jì)算,n,條信息。對(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ù)量。

6、,每一艘船到達(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(k,t,+n*x),11,確定解題思路,題目明確告訴我們，要計(jì)算的是中間的一段時(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(k,t,),如何統(tǒng)計(jì),“,總共有多少個(gè)不同的數(shù),”,呢？,1=X,i,j,n;,for(i=1;itiki;,for(j=1;

7、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,題,“,魔法陣,”,簡述,大魔法師認(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è)魔法物品

8、分別為這個(gè)魔法陣的,A,物品，,B,物品，,C,物品，,D,物品。,現(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 Xd,Xb-Xa=2(Xd-Xc),Xb-Xa(Xc-Xb),3 Xc-Xb6,x,AD=AB+BC+CD 9,x x,n div

9、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(n,2,),的算法都不能用,極限的情況下,n=15000,，,m=40000,，說明有很多數(shù)據(jù)是重復(fù)的，可以合并,采用,“,桶,”,來處理，把數(shù)據(jù)范圍降到,n=15000,加上,x,n div 9,，可以枚舉,x,nn/9=1500015000/9=2.510,7,也就是,說，可以采用,O(n,2,/9),的算法來做,19,數(shù)據(jù)結(jié)構(gòu),s:int s40005;/,存放原數(shù)據(jù),f:int f15005;/,桶，下標(biāo)為魔法值,fa,fb,fc,fd:int 15005;/,次數(shù),20,