NOIP2017普及組解題報告非官方

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