NOI普及組復賽解題報告

1、N O I P 2 0 1 5 普 及 組 解 題 報 告南京師范大學附屬中學樹人學校 CT1. 金幣 （coin.cpp/c/pas）【問題描述】 國王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金幣；之 后兩天（第二天和第三天），每天收到兩枚金幣；之后三天（第四、五、六 天），每天收到三枚金幣；之后四天 （第七、八、九、十天） ，每天收到四枚 金幣 ；這種工資發(fā)放模式會一直這樣延續(xù)下去：當連續(xù)N天每天收到N枚金幣后，騎士會在之后的連續(xù) N+1天里，每天收到N+1枚金幣。請計算在前K天里，騎士一共獲得了多少金幣。【輸入格式】輸入文件名為 coin.in 。輸入文件只有1行，包含一個

2、正整數K,表示發(fā)放金幣的天數?！据敵龈袷健枯敵鑫募麨?coin.out 。輸出文件只有 1 行，包含一個正整數，即騎士收到的金幣數?！緮祿f明】對于 100%的數據，1 K 10,000?！舅悸贰磕M【時空復雜度】O(k) ， O(1)2 、掃雷游戲（ mine.cpp/c/pas ）【問題描述】掃雷游戲是一款十分經典的單機小游戲。 在n行m列的雷區(qū)中有一些格子含有地 雷（稱之為地雷格），其他格子不含地雷（稱之為非地雷格）。玩家翻開一個非地雷格時，該格將會出現一個數字提示周圍格子中有多少個是地雷格。 游戲的目標是在不翻出任何地雷格的條件下，找出所有的非地雷格?，F在給出n行m列的雷區(qū)中的地雷分

3、布，要求計算出每個非地雷格周圍的地雷格 數。注：一個格子的周圍格子包括其上、下、左、右、左上、右上、左下、右下八 個方向上與之直接相鄰的格子?！据斎敫袷健枯斎胛募麨?mine.in 。輸入文件第一行是用一個空格隔開的兩個整數 n和m分別表示雷區(qū)的行數和列 數。接下來n行，每行m個字符，描述了雷區(qū)中的地雷分布情況。字符* 表示相 應格子是地雷格， 字符表示相應格子是非地雷格。 相鄰字符之間無分隔符。 【輸出格式】輸出文件名為 mine.out 。輸出文件包含n行，每行m個字符，描述整個雷區(qū)。用* 表示地雷格，用周圍的地雷個數表示非地雷格。相鄰字符之間無分隔符?！緮祿f明】對于 100%的數據，

4、1 nW 100, 1 me 100?！舅悸贰磕M【技巧】 可將數組多開一圈，省去邊界條件的判斷 【時空復雜度】O(mn)，O(mn)3. 求和 (sum.cpp/c/pas)【問題描述】一條狹長的紙帶被均勻劃分出了n個格子，格子編號從1到n。每個格子上都染了一種顏色color i (用1，m當中的一個整數表示)，并且寫了一個數字 numberi 。定義一種特殊的三元組： (x,y,z) ，其中 x， y， z 都代表紙帶上格子的編號， 這里的三元組要求滿足以下兩個條件：1. x,y,z 都是整數,xyz,y?x二二z?y2. color x=color z滿足上述條件的三元組的分數規(guī)定為(x

5、+z)*(number x+number)。整個紙帶的 分數規(guī)定為所有滿足條件的三元組的分數的和。這個分數可能會很大，你只 要輸出整個紙帶的分數除以 10,007 所得的余數即可。【輸入格式】輸入文件名為 sum.in 。第一行是用一個空格隔開的兩個正整數 n和m，n代表紙帶上格子的個數，m 代表紙帶上顏色的種類數。第二行有 n 個用空格隔開的正整數，第 i 個數字 numberi 代表紙帶上編號為 i 的格子上面寫的數字。第三行有m個用空格隔開的正整數，第i個數字color i代表紙帶上編號為i 的格子染的顏色。【輸出格式】輸出文件名為 sum.out。共一行，一個整數，表示所求的紙帶分數除

6、以 10,007 所得的余數?！緮祿f明】對于第1組至第2組數據，K nW 100,1 mic 5;對于第3組至第4組數據，1c nc 3000,1 c mW 100;對于第5組至第6組數據，1c nc 100000,1 c mW 100000,且不存在出現次數超過 20 的顏色;對于全部 10 組數據,1c nc100000,1 c mc100000,1 c color icm,1 c numberic100000?！舅悸贰?先分析一下,我們的任務是什么。題目的要求是求分數和,我們就得把所有 符合條件的三元組“找”出來。至少需要枚舉三元組(x,y,z)中的一個元素，這里枚舉的是z(當然x也可

7、以， 不過不要選y，因為y對分數沒什么用)。1、因為xyz，所以只需向前枚舉x,y2、因為 y-x=z-y ,所以 x+z=2y, x、 z 同奇偶,且分數與 y 無關,只需枚舉 z 和 x。3、 因為colour x二二colour z，所以只需枚舉z之前同奇偶且同色的x。這樣的話時間復雜度是 O(n2)，能得40分。如何快速枚舉x呢？其實不是快速枚舉x，是快速枚舉分數和。觀察三元組分數：(x+z) (numberx+ nu mbeiz)顯然我們不方便處理多項式乘法，那就把它拆開(事實上很多人到這步都放棄了，其實試一試立刻就明白了)=x numbeix+x numberz+z numbeix

8、+z numbeiz那么對于z的所有合法決策x1,x2, .,xk根據乘法分配率，分數 二二藝(xi*number力力)+)+藝(xi)*number z+藝(numbew)*z+藝 (z*number z)(1=i=k)由于z是枚舉的，所以只需快速得到藝(xnumber)，藝x,藝number和k(注意最后一項被算了 k 次，要乘 k)這樣我們就可以開 4 個累加器,分別記錄這四個量。而對于不同奇偶性、不同顏色的z有不同的決策X，所以要開一個s2m4的累加器。【時空復雜度】0(n)，0(n+m)【注意】題目數據較大，每次計算一定要模10007，否則很容易出錯?！緲永绦颉?includeco

9、nstintmaxn=100000;constintmaxm=100000;constintp=10007;intn,m,ans;intnumbermaxn+1,colourmaxn+1;ints2maxm+14;voidinit()freopen(sum.in,r,stdin);freopen(sum.out,w,stdout);scanf(%d%d,&n,&m);for(inti=1;i=n;i+)scanf(%d,&numberi);for(inti=1;i=n;i+)scanf(%d,&colouri);voidsolve()for(inti=1;i=n;i+)intz=i%p,num

10、z=numberi%p,c=colouri,t=i%2;intcount=stc0%=p,x=stc1%=p,numx=stc2%=p,x_numx=stc3%=p; ans=(ans+(count*z)%p*numz)%p)%p; ans=(ans+x_numx)%p; ans=(ans+x*numz)%p; ans=(ans+z*numx)%p;stc0+;stc1+=z;stc2+=numz;stc3+=z*numz;voidoutput()printf(%dn,ans);fclose(stdin);fclose(stdout);intmain()init();solve();outpu

11、t();return0;4. 推銷員 (salesman.cpp/c/pas)【問題描述】 阿明是一名推銷員，他奉命到螺絲街推銷他們公司的產品。螺絲街是一條死胡 同，出口與入口是同一個，街道的一側是圍墻，另一側是住戶。螺絲街一共有N家住戶，第i家住戶到入口的距離為S米。由于同一棟房子里可以有多家住戶，所以可能有多家住戶與入口的距離相等。阿明會從入口進入，依次向螺絲 街的X家住戶推銷產品，然后再原路走出去。阿明每走 1米就會積累 1點疲勞值，向第 i 家住戶推銷產品會積累 Ai 點疲勞值。 阿明是工作狂，他想知道，對于不同的 X,在不走多余的路的前提下，他最多 可以積累多少點疲勞值?！据斎敫袷健?/p>

12、輸入文件名為 salesman.in 。第一行有一個正整數N,表示螺絲街住戶的數量。接下來的一行有N個正整數，其中第i個整數S表示第i家住戶到入口的距離。 數據保證 SS2-S n108o接下來的一行有N個正整數，其中第i個整數A表示向第i戶住戶推銷產品會 積累的疲勞值。數據保證 Ai103?！据敵龈袷健枯敵鑫募麨?salesman.out 。輸出N行，每行一個正整數，第i行整數表示當X=i時，阿明最多積累的疲勞 值?！緮祿f明】對于20%勺數據，1 N 20;對于40%勺數據，1 N 100;對于60%勺數據，1 N 1000;對于 100%勺數據，1 N 100000?！舅悸贰款}目要求每

13、一個X的情況，顯然不能每個X專門推一遍，要充分利用已知的X勺情況，那么很可能會是 DP。定義 fi 為 X=i 時勺最大疲勞值。 關鍵是怎么建立狀態(tài)轉移方程呢？考試時觀察了兩組樣例數據，直覺告訴我 fi+1 勺決策應該會包含 fi 勺決策(此處勺決策指住戶下標)。事實上也確 實如此。證明：設fi的決策為k1,k2,ki(k1k2kj , fi+1的決策將fi決策中的 ks換成j并增加了一個決策ki+1 , fi+1的決策k中最大的為maxi。fi=2*ski+ 藝 akt(1=t=i)fi+1=2*smaxk+ 藝 ak t(1=t=s-1)+ 藝 ak t(s+1=t=i)+aj+aki+1

14、 v 2*smaxk+ 藝 akt(1=t=s-1)+ 藝 akt(s+1=t=i)+aj是 X=i 時的一種決策的疲勞值(即決策為 k1,k 2, ks-1,k s+1, ki,k j 時)2*smaxk+ 藝 akt(1=t=s-1)+ 藝 akt(s+1=t=i)+aj=fi2*smaxk+ 藝 akt(1=t=s-1)+ 藝 akt(s+1=t=i)+aj+aki+1=fi+aki+1 (即決策為 k1,k 2, ,k s, ,k i,k i+1 時的疲勞值)若小于，說明保留ks更優(yōu)；若等于，對于兩個目前疲勞值相等的決策序列 k, maxk越小越好(就是說目前 走的路程越短越好)，因為

15、在 maxk左邊的決策I只能增加al的疲勞值，而 對于 maxk 右邊的決策 r 則可以增加 2*(sr-smaxk)+ar ，對于左邊，maxk沒有影響，而對于右邊，maxk越小，后面的f增加疲勞值的空間越大。根據以上原則，雖然決策ki,k2, .,ks,.,ki與決策ki,k2,.ks-i,ks+i,.ki,k j 疲勞值相等，但 fi 選擇了前者，說明前者更優(yōu)。綜上，無論小于或等于，決策 ki,k2, .,ks,.,ki都比決策ki,k2,.ks-i ,k s+1,.ki ,k j 更優(yōu)。 fi+1的最優(yōu)決策一定包含了 fi的最優(yōu)決策，證畢.也就是說，對于 fi ，只需在 fi-1 的基

16、礎上加一個最優(yōu)決策就可以了。易得出狀態(tài)轉移方程：fi=fi-1+maxmaxak|1=kmaxi,max2*(sk-smaxi)+ak|maxik=n其中k表示待選決策(已經選過的不能再選)，maxi表示fi-1的決策序列中最大的一個決策。解釋一下：因為maxi左邊的決策k不會增加距離，只增加推銷的疲勞值ak；而maxi右邊的決策k不僅會增加疲勞值，還會使距離從 smaxi增加到sk，來回還要x 2,也就是增加了 2*(sk-smaxi)+ak枚舉k的話時間復雜度是0(n2)的，只能得60分。做到這里，優(yōu)化已經很明顯了。對于maxi的左邊，我們需要動態(tài)求區(qū)間ak最值，無論是堆、線段樹、優(yōu)先級隊

17、列、集合，時間復雜度都是logzn級別的；而對于maxi右邊,由于所有決策疲勞值都要減去 smaxi ,所以我們只要求區(qū)間 2*sk+ak 的最 值,而且可用決策必然是不斷減少的,可以預處理排個遞減序,每次找第一個合法決 策。當然，左邊的方法對于右邊同樣適用。同時，如果選擇了右邊的決策k，還需要將 maxi 到 k 之間的決策加入到左邊的待選決策中。（因為它們的身份已經從右邊的點 變成了左邊的點)。 由于每個決策最多從右邊出一次，從左邊進一次、出一次，均攤時間復雜度是 O(nlog 2n) ， 能得 100 分。(可惜考試時多寫了一個“ ”，編譯錯誤， 400變成了 300) 【時空復雜度】O

18、(nlog 2n) ，O(n) (取決于使用的數據結構)【樣例程序】heap:#include#include usingnamespacestd;constintmaxn=100000;intn; intsmaxn+1,amaxn+1,fmaxn+1;intleftmaxn+1,rightmaxn+1,l,r=1,maxi; boolcmpl(constinti,constintj)if(ai!=aj) returnaij; boolcmpr(constinti,constintj)if(2*si+ai!=2*sj+aj) return2*si+ai2*sj+aj;elsereturnij;

19、voidinit() freopen(salesman.in,r,stdin); freopen(salesman.out,w,stdout);scanf(%d,&n);for(inti=1;i=n;i+)scanf(%d,&si);for(inti=1;i=n;i+) scanf(%d,&ai); righti=i; sort(right+1,right+n+1,cmpr); voidchoose_left(constinti)fi=fi-1+aleft1;pop_heap(left+1,left+l-+1,cmpl); voidchoose_right(constinti) fi=fi-1

20、+2*(srightr-smaxi)+arightr; for(inti=maxi+1;irightr;i+) left+l=i; push_heap(left+1,left+l+1,cmpl); maxi=rightr+;while(r=n&rightr=maxi) r+;voidsolve() for(inti=1;in)choose_left(i); elseif(aleftl=2*(srightr-smaxi)+arightr) choose_left(i);elsechoose_right(i);voidoutput()for(inti=1;i=n;i+) printf(%dn,fi

21、);fclose(stdin); fclose(stdout);intmain()init();solve();output();return0;set:#include#includeusingnamespacestd;constintmaxn=100000;intn;intsmaxn+1,amaxn+1,fmaxn+1;intleftmaxn+1,rightmaxn+1,l,r=1,maxi;boolcmpl(constinti,constintj)if(ai!=aj)returnaij;boolcmpr(constinti,constintj)if(2*si+ai!=2*sj+aj) r

22、eturn2*si+ai2*sj+aj;elsereturnij;voidinit()freopen(salesman.in,r,stdin); freopen(salesman.out,w,stdout); scanf(%d,&n);for(inti=1;i=n;i+)scanf(%d,&si);for(inti=1;i=n;i+)scanf(%d,&ai);righti=i;sort(right+1,right+n+1,cmpr);voidchoose_left(constinti)fi=fi-1+aleft1;pop_heap(left+1,left+l-+1,cmpl); voidch

23、oose_right(constinti)fi=fi-1+2*(srightr-smaxi)+arightr;for(inti=maxi+1;irightr;i+)left+l=i; push_heap(left+1,left+l+1,cmpl);maxi=rightr+;while(r=n&rightr=maxi)r+;voidsolve()for(inti=1;in) choose_left(i);elseif(aleftl=2*(srightr-smaxi)+arightr) choose_left(i);elsechoose_right(i);voidoutput()for(inti=

24、1;i=n;i+)printf(%dn,fi);fclose(stdin);fclose(stdout);intmain()init();solve();output();return0;priority_queue:#include#includeconstintmaxn=100000;usingnamespacestd;intn;intsmaxn+1,amaxn+1,fmaxn+1,maxi; classcmplpublic:booloperator()(constinti,constintj)returnaiaj;classcmprpublic:booloperator()(consti