NOIP2017普及組解題報(bào)告非官方

NOIP2017普及組解題報(bào)告-by鄭佳睿1.成績(jī)(score.cpp/c/pas)【問(wèn)題描述】牛牛最近學(xué)習(xí)了C++入門(mén)課程，這門(mén)課程的總成績(jī)計(jì)算方法是：總成績(jī)=作業(yè)成績(jī)×20%+小測(cè)成績(jī)×30%+期末考試成績(jī)×50%牛牛想知道，這門(mén)課程自己最終能得到多少分。【輸入格式】輸入文件只有1行，包含三個(gè)非負(fù)整數(shù)A、B、C，分別表示牛牛的作業(yè)成績(jī)、小測(cè)成績(jī)和期末考試成績(jī)。相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)，三項(xiàng)成績(jī)滿(mǎn)分都是100分?！据斎霕永?】10010080【輸出樣例1】90【輸入樣例2】609080【輸出樣例2】79【數(shù)據(jù)說(shuō)明】30%的數(shù)據(jù)，A=B=0。對(duì)于另外30%的數(shù)據(jù)，A=B=100。對(duì)于100%的數(shù)據(jù)，0≤A、B、C≤100且A、B、C都是10的整數(shù)倍。【題解】超級(jí)水題，輸入數(shù)據(jù)都是10的倍數(shù)，不用考慮浮點(diǎn)的問(wèn)題，直接輸出答案?！敬a】#include<bits/stdc++.h>usingnamespacestd;inta,b,c;intmain(){cin>>a>>b>>c;cout<<(a*2+b*3+c*5)/10<<endl;return0;}2.圖書(shū)管理員(librarian.cpp/c/pas)【問(wèn)題描述】圖書(shū)館中每本書(shū)都有一個(gè)圖書(shū)編碼，可以用于快速檢索圖書(shū)，這個(gè)圖書(shū)編碼是一個(gè)正整數(shù)。每位借書(shū)的讀者手中有一個(gè)需求碼，這個(gè)需求碼也是一個(gè)正整數(shù)。如果一本書(shū)的圖書(shū)編碼恰好以讀者的需求碼結(jié)尾，那么這本書(shū)就是這位讀者所需要的。小D剛剛當(dāng)上圖書(shū)館的管理員，她知道圖書(shū)館里所有書(shū)的圖書(shū)編碼，她請(qǐng)你幫她寫(xiě)一個(gè)程序，對(duì)于每一位讀者，求出他所需要的書(shū)中圖書(shū)編碼最小的那本書(shū)，如果沒(méi)有他需要的書(shū)，請(qǐng)輸出-1【輸入格式】輸入文件的第一行，包含兩個(gè)正整數(shù)n和q，以一個(gè)空格分開(kāi)，分別代表圖書(shū)館里書(shū)的數(shù)量和讀者的數(shù)量。接下來(lái)的n行，每行包含一個(gè)正整數(shù)，代表圖書(shū)館里某本書(shū)的圖書(shū)編碼。接下來(lái)的q行，每行包含兩個(gè)正整數(shù)，以一個(gè)空格分開(kāi)，第一個(gè)正整數(shù)代表圖書(shū)館里讀者的需求碼的長(zhǎng)度，第二個(gè)正整數(shù)代表讀者的需求碼?！据敵龈袷健枯敵鑫募衠行，每行包含一個(gè)整數(shù)，如果存在第i個(gè)讀者所需要的書(shū)，則在第i行輸出第i個(gè)讀者所需要的書(shū)中圖書(shū)編碼最小的那本書(shū)的圖書(shū)編碼，否則輸出-1。【輸入樣例1】【輸出樣例1】552123112323242422331233124212212231123-1-1-1【數(shù)據(jù)規(guī)模與約定】對(duì)于20%的數(shù)據(jù)，1≤n≤2。另有20%的數(shù)據(jù)，q=1。另有20%的數(shù)據(jù)，所有讀者的需求碼的長(zhǎng)度均為1。另有20%的數(shù)據(jù)，所有的圖書(shū)編碼按從小到大的順序給出。對(duì)于100%的數(shù)據(jù)，1≤n≤1,000，1≤q≤1,000，所有的圖書(shū)編碼和需求碼均不超過(guò)10,000,000?！绢}解】還是水題，用數(shù)組保存輸入的n個(gè)圖書(shū)編碼；對(duì)于q個(gè)讀者，讀入長(zhǎng)度和需求碼，按長(zhǎng)度確定取模單元，然后對(duì)每本圖書(shū)取模判斷是否尾部匹配，匹配則記錄最小編碼。注意ans的初值應(yīng)該取大于等于10000000的值，輸出時(shí)判斷是否應(yīng)輸出-1?！敬a】#include<bits/stdc++.h>usingnamespacestd;intn,q,a[1005];intmain(){cin>>n>>q;for(inti=0;i<n;i++)cin>>a[i];for(intj=0;j<q;j++){ intlen,code,t=1,m=10000000; cin>>len>>code; for(inti=1;i<=len;i++)t*=10; for(inti=0;i<n;i++) if(a[i]%t==code)m=min(m,a[i]);if(m==10000000)cout<<-1<<endl;elsecout<<m<<endl; a[x][y]=c;}f[1][1]=0;q.push((node){1,1,a[1][1],1,0});while(!q.empty()){//廣搜 cur=q.front();q.pop(); expand(cur.x-1,cur.y); expand(cur.x+1,cur.y); expand(cur.x,cur.y-1); expand(cur.x,cur.y+1);}if(f[m][m]<20000)cout<<f[m][m]<<endl;elsecout<<-1<<endl;return0;}4.跳房子(jump.cpp/c/pas)【問(wèn)題描述】跳房子，也叫跳飛機(jī)，是一種世界性的兒童游戲，也是中國(guó)民間傳統(tǒng)的體育游戲之一。跳房子的游戲規(guī)則如下：在地面上確定一個(gè)起點(diǎn)，然后在起點(diǎn)右側(cè)畫(huà)n個(gè)格子，這些格子都在同一條直線(xiàn)上。每個(gè)格子內(nèi)有一個(gè)數(shù)字（整數(shù)），表示到達(dá)這個(gè)格子能得到的分?jǐn)?shù)。玩家第一次從起點(diǎn)開(kāi)始向右跳，跳到起點(diǎn)右側(cè)的一個(gè)格子內(nèi)。第二次再?gòu)漠?dāng)前位置繼續(xù)向右跳，依此類(lèi)推。規(guī)則規(guī)定：玩家每次都必須跳到當(dāng)前位置右側(cè)的一個(gè)格子內(nèi)。玩家可以在任意時(shí)刻結(jié)束游戲，獲得的分?jǐn)?shù)為曾經(jīng)到達(dá)過(guò)的格子中的數(shù)字之和?，F(xiàn)在小R研發(fā)了一款彈跳機(jī)器人來(lái)參加這個(gè)游戲。但是這個(gè)機(jī)器人有一個(gè)非常嚴(yán)重的缺陷，它每次向右彈跳的距離只能為固定的d。小R希望改進(jìn)他的機(jī)器人，如果他花g個(gè)金幣改進(jìn)他的機(jī)器人，那么他的機(jī)器人靈活性就能增加g，但是需要注意的是，每次彈跳的距離至少為1。具體而言，當(dāng)g<d時(shí)，他的機(jī)器人每次可以選擇向右彈跳的距離為d-g,d-g+1,d-g+2，…，d+g-2，d+g-1，d+g；否則（當(dāng)g≥d時(shí)），他的機(jī)器人每次可以選擇向右彈跳的距離為1，2，3，…，d+g-2，d+g-1，d+g?，F(xiàn)在小R希望獲得至少k分，請(qǐng)問(wèn)他至少要花多少金幣來(lái)改造他的機(jī)器人。【輸入格式】第一行三個(gè)正整數(shù)n，d，k，分別表示格子的數(shù)目，改進(jìn)前機(jī)器人彈跳的固定距離，以及希望至少獲得的分?jǐn)?shù)。相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。接下來(lái)n行，每行兩個(gè)正整數(shù)????,????，分別表示起點(diǎn)到第i個(gè)格子的距離以及第i個(gè)格子的分?jǐn)?shù)。兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。保證????按遞增順序輸入?！据敵龈袷健抗惨恍?，一個(gè)整數(shù)，表示至少要花多少金幣來(lái)改造他的機(jī)器人。若無(wú)論如何他都無(wú)法獲得至少k分，輸出-1?！据斎霕永?】7410265-310311-3131176202【輸出樣例1】2【數(shù)據(jù)規(guī)模與約定】本題共10組測(cè)試數(shù)據(jù)，每組數(shù)據(jù)10分。對(duì)于全部的數(shù)據(jù)滿(mǎn)足1≤n≤500000,1≤d≤2000,1≤????,??≤109,|si|<105。1，2組測(cè)試數(shù)據(jù)，n≤10；3，4，5n≤500【題解】根據(jù)題意，當(dāng)g固定時(shí)，獲得的得分可以根據(jù)動(dòng)規(guī)轉(zhuǎn)移方程f[i]=max(f[j]|dmin<=(x[i]-x[j])<=dmax)+s[i]得出，f[i]為調(diào)到每個(gè)格子時(shí)的最大得分，dmin=max(d-g,1)dmax=d+g那么當(dāng)g越大，dmin到dmax的范圍越大，越容易達(dá)到最大分，當(dāng)g的最大值取到x[n]時(shí)，可以跳到任何一個(gè)格子。因此二分答案0-x[n]，可以在小于32次判決的基礎(chǔ)上獲得正確的解。每次判決都是一次完整的動(dòng)規(guī)。F[i]的值從x[i]-dmax到x[i]-dmin的區(qū)間最大值轉(zhuǎn)移而來(lái)，所有的f[i]的計(jì)算的復(fù)雜度是O(n*n)，對(duì)于50%的數(shù)據(jù)，可以使用這個(gè)方法得出答案，但是n的取值范圍是500000，必須找到O(n)的算法。F[i]對(duì)應(yīng)的x[i]是單調(diào)增長(zhǎng)的，構(gòu)造一個(gè)單調(diào)隊(duì)列，上述狀態(tài)轉(zhuǎn)移的過(guò)程就可以在O(n)復(fù)雜度內(nèi)獲得。二分答案需要check函數(shù)返回是否可以取到得分>=K，整體的復(fù)雜度為O(nlog(Gmax))，時(shí)間上滿(mǎn)足題目的約定?！敬a】#include<bits/stdc++.h>usingnamespacestd;structnode{//單調(diào)隊(duì)列的元素x為和起點(diǎn)的距離intx,v;//v為x距離格的最大得分}q[500005];intn,d,k;intx[500005],s[500005],f[500005];//xs數(shù)組為每格的距離和分值intcheck(intg){//f為狀態(tài)數(shù)組，第i格的最大得分intqmin=d-g,qmax=d+g;//qmin和qmax是最小和最大跳躍距離inthead=0,tail=-1,cur=0;//head,tail為單調(diào)隊(duì)列的首尾指針if(qmin<=0)qmin=1;//cur為未處理完的格子memset(f,0,sizeof(f));for(inti=1;i<=n;i++){for(cur;(cur<i)&&(x[cur]<=x[i]-qmin);cur++){//把距離當(dāng)前格qmin內(nèi)的未添加到 //單調(diào)隊(duì)列的格子添加到單調(diào)隊(duì)列while((head<=tail)&&(q[tail].v<f[cur]))tail--;//值比要添加的小，壽命短的 //不會(huì)對(duì)以后的f有貢獻(xiàn)，可 //以從隊(duì)列中刪除if(f[cur]<=-1000000000)continue;//無(wú)法到達(dá)的格子不添加q[++tail].v=f[cur];q[tail].x=x[cur];//將cur格添加到隊(duì)列中}while((head<=tail)&&(x[i]-q[head].x>qmax))head++;//距離超過(guò)qmax的刪除f[i]=(head<=tail)?q[head].v+s[i]:-1000000000;//轉(zhuǎn)態(tài)轉(zhuǎn)移if(f[i]>=k)return1;//已達(dá)到要求的得分返回True}return0;//直到所有格子計(jì)算完畢也無(wú)法得到要求的得分，返回false}intmain(){cin>>n>>d>>k;for(inti=1;i<=n;i++)cin>>x[i]>>s[i];//輸入數(shù)