NOIP復(fù)賽復(fù)習(xí)13預(yù)處理與前綴和

1、NOIP復(fù)賽復(fù)習(xí)13預(yù)處理與前綴和一、預(yù)處理所謂預(yù)處理，顧名思義，就是事先計(jì)算好需要的值或事先處理某些東西，有時(shí)候你會(huì)發(fā)現(xiàn)你做一個(gè)題目出現(xiàn)了TLE，原因就是重復(fù)的計(jì)算會(huì)導(dǎo)致效率不高（或者說(shuō)你的預(yù)處理不夠優(yōu)雅）。A、直接把結(jié)果預(yù)處理XTUOJ1052題意：某一個(gè)數(shù)字集合定義如下：1.0屬于這個(gè)集合；.如果X屬于這個(gè)集合，那么2X+1,3X+1也屬于這個(gè)集合；.集合只包含按增序排列的前100000個(gè)元素。集合按增序排列，根據(jù)輸入的元素序號(hào)，輸出對(duì)應(yīng)的元素值。輸入每行一個(gè)整數(shù)n（n100000），表示元素的序號(hào)（從0開(kāi)始記數(shù)），如果是-1,則輸入結(jié)束。輸出每行輸出對(duì)應(yīng)元素的值。SampleInput

2、04put4分析：很明顯，不能也不好直接判斷是否存在于這個(gè)集合中，只需要把所有存在于這個(gè)集合中標(biāo)記，并且預(yù)處理這些元素的序號(hào)，之后輸出就行了，那么一次預(yù)處理便可以知道所有序號(hào)對(duì)應(yīng)的元素了。#include#defineMAX2000001usingnamespacestd;inta100010,b3*MAX;intmain()intn,i,j;b0=1;for(i=0;iMAX;i+)if(bi=1)b2*i+1=b3*i+1=1;for(i=0,j=0;in,n!=1)coutanendl;return0;POJ1426題意：有k個(gè)壞人k個(gè)好人坐成一圈，前k個(gè)為好人(編號(hào)1k),后k個(gè)為壞人

3、(編號(hào)k+12k),給定m,從編號(hào)為1的人開(kāi)始報(bào)數(shù)，報(bào)到m的人就要自動(dòng)死去，之后從下一個(gè)人繼續(xù)開(kāi)始新一輪的報(bào)數(shù)。問(wèn)當(dāng)m為什么值時(shí)，k個(gè)壞人會(huì)在好人死亡之前全部死掉？分析：遇到存在環(huán)的題目的時(shí)候，可以直接直線化處理。當(dāng)然也可以直接利用循環(huán)鏈表或者數(shù)組進(jìn)行環(huán)的模擬，不過(guò)這樣的程序?qū)懫饋?lái)有點(diǎn)復(fù)雜。這個(gè)題目直接暴力模擬求解必定TLE，需要一點(diǎn)數(shù)學(xué)的知識(shí)，這在里就不詳細(xì)說(shuō)了，即使這樣，還是會(huì)超時(shí)，正確的方法便是預(yù)處理出僅有的14個(gè)答案，但既然已經(jīng)知道了所有答案，而且又只有14個(gè)，那么直接把答案交上去就行了。#includeintans15=0,2,7,5,30,169,441,1872,7632,174

4、0,93313,459901,1358657,2504881,13482720;intmain()intn;while(scanf(%d,&n),n)printf(%dn,ansn);return0;UVA12716題意：給定一個(gè)整數(shù)n,求出有多少對(duì)整數(shù)a,b滿足1=b=a=n且gcd(a,b)=aXORb.分析：最容易想到的方法是枚舉a,尻雙重循環(huán)加上求gcd,總復(fù)雜度為O(n*n*logn),絕對(duì)無(wú)法承受。如何減少枚舉呢？注意到亦或運(yùn)算的性質(zhì)，如果aW=c,那么a他二b,既然c為a，b的最大公約數(shù)的話，那么我們可以從枚舉a和c出發(fā)，那么就是枚舉所有因子c及其可能的倍數(shù)a，和素?cái)?shù)篩法一樣，這

5、樣復(fù)雜度為O(nlogn*logn),n最大為30000000，復(fù)雜度還是有點(diǎn)高，怎么減少?gòu)?fù)雜度呢？這就要通過(guò)一點(diǎn)數(shù)學(xué)知識(shí)或者找規(guī)律發(fā)現(xiàn)了，通過(guò)打印出所有滿足條件的a,b,c可以發(fā)現(xiàn)a+b=c，所以可以將復(fù)雜度降為O(n*logn)，但是題目是多樣例輸入，如果每次都需要O(n*logn)計(jì)算答案的話，還是會(huì)超時(shí)，觀察便可得知其實(shí)在計(jì)算n以內(nèi)滿足條件的a，b對(duì)數(shù)時(shí)比n小的數(shù)以內(nèi)的對(duì)數(shù)都已經(jīng)計(jì)算出來(lái)了，也就是說(shuō)不需要重復(fù)計(jì)算了，那么我們可以通過(guò)一次預(yù)處理，在計(jì)算的過(guò)程中統(tǒng)計(jì)每個(gè)a組合時(shí)的對(duì)數(shù)，之后循環(huán)遍歷一次全部加起來(lái)就可以知道每個(gè)n以內(nèi)的答案了。while(t-)while(t-)#includ

6、e#include#include#includeusingnamespacestd;constintN=30000000;intaN+5;voidpretreat()for(inti=1;i=15000000;i+)for(intj=i1;j=N;j+=i)if(j八(j-i)=i)aj+;aintmain()pretreat。;intt,ca=0;scanf(%d,&t);intn;scanf(%d,&n);printf(Case%d:%dn,+ca,an);return0;、把需要用的預(yù)處理比較常見(jiàn)的基本就是三個(gè)：預(yù)處理素?cái)?shù)、預(yù)處理組合數(shù)、預(yù)處理前綴和。首先舉個(gè)比較經(jīng)典的例子：素?cái)?shù)打表判

7、斷是否素?cái)?shù)有3種方式：O(sqrt(n)的簡(jiǎn)單素性測(cè)試、埃氏篩法，以及Miller_Rabin算法進(jìn)行素?cái)?shù)測(cè)試。如果需要進(jìn)行大量的用到素?cái)?shù)或者判斷素?cái)?shù)，則可以埃氏篩法打表出所有的素?cái)?shù)。XTUOJ1237題目描述：如果n和n+2都是素?cái)?shù)，我們稱其為孿生素?cái)?shù)，比如3和5,5和7都是孿生素?cái)?shù)。給你一個(gè)區(qū)間a,b,請(qǐng)問(wèn)期間有多少對(duì)孿生素?cái)?shù)？輸入第一行是一個(gè)整數(shù)(10000)表示樣例的個(gè)數(shù)。以后每行一個(gè)樣例，為兩個(gè)整數(shù)，a和b，1ab5000000輸出每行輸出一個(gè)樣例的結(jié)果。樣例輸入1311011001100015000000樣例輸出0283532463分析：計(jì)算區(qū)間內(nèi)個(gè)數(shù)的題目一般滿足區(qū)間減法性質(zhì)，但

8、是不能一概而論，具體題目具體分析，就像這題一對(duì)孿生素?cái)?shù)是跨越了3個(gè)數(shù)，要分情況考慮。首先直接標(biāo)記出所有的素?cái)?shù)，令gx為1到X+2這個(gè)區(qū)間內(nèi)孿生素?cái)?shù)的對(duì)數(shù)，要統(tǒng)計(jì)出數(shù)量，遍歷一次即可，只需要一次預(yù)處理就可以計(jì)算出所有的gx,之后便可以0(1)計(jì)算出所有1到X+2這個(gè)區(qū)間內(nèi)孿生素?cái)?shù)的對(duì)數(shù)了。如果輸入的區(qū)間長(zhǎng)度小于2,那么必定沒(méi)有，如果長(zhǎng)度大于2,稍加思考便可以得知答案即為gb-2-gaT。#include#includeconstintN=5000001;intfN,gN；intmain()intup=sqrt(N);for(inti=2;i=up;i+)if(!fi)for(intj=i*i;j

9、=N;j+=i)fj=1;for(inti=3;iN-1;i+=2)gi+1=gi=gi1+!(fillfi+2T);intt;scanf(%d,&t);while(t-)inta,b;scanf(%d%d,&a,&b);b-a2?p-gn0;CF231C題意：給定一個(gè)數(shù)組，每次可以給任意元素加1這樣的操作不能超過(guò)k次，求操作不超過(guò)k次后數(shù)組中一個(gè)數(shù)能夠出現(xiàn)的最多次數(shù)，以及能夠以這個(gè)次數(shù)出現(xiàn)的最小的數(shù)。分析：這個(gè)題目明顯具有單調(diào)性，這樣的話就可以進(jìn)行二分搜索求取最大次數(shù)了。怎么判斷假定的解是否可行呢？既然只能是加1，而且又不超過(guò)k次，那么首先將數(shù)組排序，假設(shè)搜索的次數(shù)為m，那么i從第m個(gè)數(shù)循環(huán)

10、到最后一個(gè)數(shù)，只要滿足了次數(shù)不小于k就立即退出循環(huán)，這樣找到的便一定是出現(xiàn)m次的最小的數(shù)，但是這個(gè)判斷的過(guò)程就是第m個(gè)數(shù)與其之前的m-1個(gè)數(shù)的差之和要不大于k，如果每次都直接加上差進(jìn)行判斷必定超時(shí)，因?yàn)槎炙阉骷友h(huán)判斷的時(shí)間復(fù)雜度太高，那么最好的優(yōu)化就是直接之前預(yù)處理，求出第1個(gè)數(shù)到第m個(gè)數(shù)區(qū)間的和，后面判斷的時(shí)候直接就是o(1)計(jì)算區(qū)間的和了。#include#include#includeusingnamespacestd;typedeflonglongLL;constintINF=0 x3f3f3f3f;constintN=100010;LLaN,sumN;intmain()intn;

11、LLk;while(scanf(%d%I64d,&n,&k)for(inti=1;i=n;i+)scanf(%I64d,&ai);sort(a+1,a+1+n);intr=INF,l=0;sum1=a1;for(inti=2;i1)intm=(r+l)/2;if(mn)r=m;continue;intflag=0;for(inti=m;i=n;i+)if(m-1)*ai-sumi-1+sumi-m=k)flag=1;ans=ai;return0;C、關(guān)于預(yù)處理的總結(jié)預(yù)處理的目的是為了減少重復(fù)的計(jì)算從而減少時(shí)間復(fù)雜度，有時(shí)一個(gè)簡(jiǎn)單的預(yù)處理能使得算法性能顯著提高。首先我們可以按思路直接寫(xiě)一個(gè)程序，

12、如果復(fù)雜度太大，那么算法的優(yōu)化可以從這個(gè)過(guò)程出發(fā)，思考可以對(duì)哪個(gè)算法的部分進(jìn)行改進(jìn)，而預(yù)處理便是一種對(duì)應(yīng)的非常重要的技巧。像預(yù)處理區(qū)間和便是非常常見(jiàn)的，而且正如上面所示的幾個(gè)題一樣，一次預(yù)處理出全部的答案也是很常見(jiàn)的，要注意思考每個(gè)部分的聯(lián)系。二、前綴和有前綴和，前綴GCD,前綴奇數(shù)個(gè)數(shù)，前綴偶數(shù)個(gè)數(shù)，前綴差，等等，都要根據(jù)自己的思想來(lái)去解決!，前綴思想真的還是挺考人的，如果想不到的話.記?。阂话闵婕暗絽^(qū)間的什么值時(shí)，就要用前綴思想.HDU4223思路：目的是找一個(gè)子串，其和的絕對(duì)值最小.其實(shí)不用前綴思想也好寫(xiě)出來(lái)，但是我一下就想了下前綴，因?yàn)樽哟€是一個(gè)區(qū)間賽.所以求一個(gè)前綴和，并排序，然后

13、一個(gè)一個(gè)相減，這樣的差值就是某一個(gè)子串的最小值。因?yàn)槭桥藕眯蛄说模砸钚∫欢ㄊ窃谀骋粋€(gè)前綴和差值里，然后加上一個(gè)絕對(duì)值就是了.總之：看到區(qū)間就要聯(lián)想的前綴思想。#include#include#include#includeusingnamespacestd;constintmaxn=1e3+5;intcas=1;intansmaxn;intamaxn;intt;scanf(%d,&t);while(t-)intn;memset(ans,0,sizeof(ans);scanf(%d,&n);for(inti=1;i=n;i+)，for(inti=1;i=n;i+)ansi=ansi-1+a

14、i;sort(ans,ans+n+1);for(inti=0;i=n;i+)printf(%d,ansi);printf(n);intres=ans1-ans0;for(inti=1;i=n;i+)if(abs(ansi-ansi-1)res)res=abs(ansi-ansi-1);printf(Case%d:,cas+);printf(%dn,res);題目描述：給你n個(gè)數(shù)(n1e5)，問(wèn)不能拼出的最小數(shù)是多少(從1開(kāi)始算)，比如：1,2,3,4,5不能拼出最小的數(shù)16。1,2,4,5不能拼出的最小數(shù)為13。2,3,4,5不能拼出的數(shù)為1。輸入的n有多組數(shù)據(jù)，每一個(gè)數(shù)1e9。思路:前綴和思

15、想.如果后面的數(shù)字如果大于前綴和+1說(shuō)明他和區(qū)間沒(méi)有交集前綴和+1這個(gè)數(shù)字就達(dá)不到就不連續(xù)了，就輸出此時(shí)的前綴和+1。#include#includeusingnamespacestd;constintmaxn=1e5+5;intamaxn;intmain()intn;while(scanf(%d,&n)for(inti=0;in;i+)scanf(%d,&ai);sort(a,a+n);/記得排序哦.intans=0;for(inti=0;ians+1)如上面所說(shuō).主要原因是連續(xù)的數(shù)之間是有一定的聯(lián)系的.break;ans+=ai;printf(%dn,ans+1);HDU6025思想：因?yàn)?/p>

16、是要?jiǎng)h除其中一個(gè)數(shù)，然后是總Gcd最大，一個(gè)個(gè)刪肯定會(huì)T,所以刪除一個(gè)，相當(dāng)于求前一個(gè)區(qū)間和后一個(gè)區(qū)間的GCD，所以我們想到用求前綴GCD和后綴GCD的方法，這樣我們只需要掃一遍就可以求出來(lái)最后答案。#include#include#include#defineCLR(x)memset(x,0,sizeof(x)usingnamespacestd;constintmaxn=1e5+5;constintinf=1e9;intqianmaxn,houmaxn;intamaxn;GCD這樣刪nintt;scanf(%d,&t);while(t-)CLR(qian);CLR(hou);intn;sca

17、nf(%d,&n);for(inti=1;i=n;i+)，qian1=a1;hou1=an;for(inti=2;i=n;i+)for(inti=2;i=n;i+)houi=_gcd(houi-1,an-i+1);intmaxx=max(qiann-1,houn-1);for(inti=2;imaxx)maxx=m;printf(%dn,maxx);SHU1952已知一個(gè)長(zhǎng)度為N的數(shù)列A1.N。現(xiàn)在給出Q次查詢，每次查詢一個(gè)區(qū)間L,R。對(duì)于每一個(gè)區(qū)間，求使得(Ai+Aj)為奇數(shù)的(i,j)的對(duì)數(shù)(L=ij=R)。Input多組數(shù)據(jù)，第一行有一個(gè)整數(shù)T表示數(shù)據(jù)組數(shù)。(T=5)之后有T組數(shù)據(jù)，每組

18、數(shù)據(jù)第一行為兩個(gè)整數(shù)N和Q，表示數(shù)列長(zhǎng)度及查詢數(shù)量。(1=N,Q=100000)接著有一行N個(gè)元素的數(shù)列A1.N。(1=Ai=1000)接下來(lái)Q行，每行有兩個(gè)整數(shù)L,R,表示查詢的區(qū)間。(1=L=R=N)Output對(duì)于每次詢問(wèn)，輸出一行數(shù)字，表示區(qū)間于的對(duì)數(shù).于Sampleinput152153421523SampleOutput60思路：只有當(dāng)一個(gè)奇數(shù)加一個(gè)偶數(shù)時(shí)才滿足題目要求所以知道該區(qū)間中奇數(shù)和偶數(shù)的個(gè)數(shù)就可以直接算。#include#include#include#includeusingnamespacestd;constintmaxn=1e5+5;intcas=1;structm

19、athintodd;/結(jié)構(gòu)體中的變量會(huì)自動(dòng)付初值.intans;sm.axn;intt;scanf(%d,&t);while(t-)intn,q;scanf(%d%d,&n,&q);for(inti=1;i=n;i+)intx;scanf(%d,&x);if(x&1)si.odd+=si-1.odd+1;每一個(gè)繼承前面那個(gè)的奇數(shù)和偶數(shù)個(gè)數(shù).si.ans+=si-1.ans;elsesi.ans+=si-1.ans+1;si.odd+=si-1.odd;while(q-)intl,r;scanf(%d%d,&l,&r);inta=sr.odd-sl-1.odd;intb=sr.ans-sl-1.ans;printf(%dn