|
一、預(yù)處理 所謂預(yù)處理,，顧名思義,，就是事先計(jì)算好需要的值或事先處理某些東西，有時(shí)候你會(huì)發(fā)現(xiàn)你做一個(gè)題目出現(xiàn)了TLE,，原因就是重復(fù)的計(jì)算會(huì)導(dǎo)致效率不高（或者說(shuō)你的預(yù)處理不夠“優(yōu)雅”）,。 A、直接把結(jié)果預(yù)處理 XTUOJ 1052 題意：某一個(gè)數(shù)字集合定義如下： 1.0屬于這個(gè)集合,； 2.如果x屬于這個(gè)集合,，那么2x+1,3x+1也屬于這個(gè)集合； 3.集合只包含按增序排列的前100000個(gè)元素,。 集合按增序排列,，根據(jù)輸入的元素序號(hào)，輸出對(duì)應(yīng)的元素值,。 輸入 每行一個(gè)整數(shù)n（n<100000）,，表示元素的序號(hào)（從0開(kāi)始記數(shù)），如果是-1,，則輸入結(jié)束,。 輸出 每行輸出對(duì)應(yīng)元素的值。 Sample Input 0 1 2 3 4 5 -1 Sample Output 0 1 3 4 7 9 分析：很明顯,，不能也不好直接判斷是否存在于這個(gè)集合中,，只需要把所有存在于這個(gè)集合中標(biāo)記，并且預(yù)處理這些元素的序號(hào),，之后輸出就行了,，那么一次預(yù)處理便可以知道所有序號(hào)對(duì)應(yīng)的元素了,。 #include #define MAX 2000001 using name space std; int a[100010], b[3*MAX]; int main() { int n, i, j; b[0] = 1; for (i = 0; i < MAX; i++) if (b[i] == 1) b[2*i+1] = b[3*i+1] =1; for (i = 0, j = 0; i < 100000; j++) if (b[j] == 1) a[i++] = j; while (cin >> n, n != 1) cout < return 0; }
POJ 1426 題意：有k個(gè)壞人k個(gè)好人坐成一圈，前k個(gè)為好人（編號(hào)1~k）,，后k個(gè)為壞人(編號(hào)k+1~2k),，給定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è),，那么直接把答案交上去就行了。 #include int ans[15] = {0, 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657,2504881, 13482720}; int main() { int n; while (scanf('%d', &n), n)printf('%d\n', ans[n]); return 0; }
UVA 12716 題意：給定一個(gè)整數(shù)n,，求出有多少對(duì)整數(shù)a,b滿足1<=b<=a<=n且gcd(a,b)=aXOR b. 分析：最容易想到的方法是枚舉a,，b，雙重循環(huán)加上求gcd,，總復(fù)雜度為O(n*n*logn),絕對(duì)無(wú)法承受,。如何減少枚舉呢？注意到亦或運(yùn)算的性質(zhì),，如果a^b=c,那么a^c=b,既然c為a,，b的最大公約數(shù)的話，那么我們可以從枚舉a和c出發(fā),，那么就是枚舉所有因子c及其可能的倍數(shù)a,，和素?cái)?shù)篩法一樣，這樣復(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)的答案了。
#include #include #include #include using name space std; const int N = 30000000; int a[N+5]; void pretreat() { for (int i = 1; i <= 15000000; i++){ for (int j = i<<1; j <= N; j+= i) { if ((j ^ (j-i)) == i) a[j]++; } } for (int i = 2; i <= N; i++) a[i] +=a[i-1]; } int main() { pretreat(); int t, ca = 0; scanf('%d', &t); while (t--) { int n; scanf('%d', &n); printf('Case %d: %d\n', ++ca,a[n]); } return 0; }
B,、把需要用的預(yù)處理 比較常見(jiàn)的基本就是三個(gè)：預(yù)處理素?cái)?shù),、預(yù)處理組合數(shù)、預(yù)處理前綴和,。 首先舉個(gè)比較經(jīng)典的例子：素?cái)?shù)打表 判斷是否素?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ù)。
XTUOJ 1237 題目描述：如果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ù)K(K≤ 10000)，表示樣例的個(gè)數(shù),。以后每行一個(gè)樣例,，為兩個(gè)整數(shù)，a和b,，1≤a≤b≤5000000,。 輸出 每行輸出一個(gè)樣例的結(jié)果。 樣例輸入 5 13 110 1100 11000 15000000 樣例輸出 0 2 8 35 32463 分析：計(jì)算區(qū)間內(nèi)個(gè)數(shù)的題目一般滿足區(qū)間減法性質(zhì),，但是不能一概而論,，具體題目具體分析，就像這題一對(duì)孿生素?cái)?shù)是跨越了3個(gè)數(shù),，要分情況考慮,。 首先直接標(biāo)記出所有的素?cái)?shù)，令g[x]為1到x+2這個(gè)區(qū)間內(nèi)孿生素?cái)?shù)的對(duì)數(shù),，要統(tǒng)計(jì)出數(shù)量,，遍歷一次即可,，只需要一次預(yù)處理就可以計(jì)算出所有的g[x],之后便可以O(1)計(jì)算出所有1到x+2這個(gè)區(qū)間內(nèi)孿生素?cái)?shù)的對(duì)數(shù)了。 如果輸入的區(qū)間長(zhǎng)度小于2,，那么必定沒(méi)有,，如果長(zhǎng)度大于2，稍加思考便可以得知答案即為g[b-2]-g[a-1],。
#include #include const int N = 5000001; int f[N], g[N]; int main() { int up = sqrt(N); for (int i = 2; i <= up; i++) if(!f[i]) for (int j = i*i; j <= N; j+= i) f[j] = 1; for (int i = 3; i < N-1; i += 2) g[i+1] = g[i] = g[i-1] + !(f[i]||f[i+2]); int t; scanf('%d', &t); while (t--) { int a, b; scanf('%d %d', &a,&b); b-a < 2 ? puts('0') :printf('%d\n', g[b-2] -g[a-1]); } return 0; }
CF 231C 題意：給定一個(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)到最后一個(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 #include using name space std; typedef long long LL; const int INF = 0x3f3f3f3f; const int N = 100010; LL a[N], sum[N]; int main() { int n; LL k; while (~scanf('%d %I64d', &n,&k)) { for (int i = 1; i <= n; i++)scanf('%I64d', &a[i]); sort(a + 1, a + 1+n); int r = INF, l = 0; sum[1] = a[1]; for (int i = 2; i <= n; i++) sum[i] =a[i] + sum[i-1]; LL ans; while (r - l > 1) { int m = (r+l) / 2; if (m > n) { r = m; continue;} int flag = 0; for (int i = m; i <= n; i++){ if ((m-1)*a[i] - sum[i-1]+sum[i-m] <= k){ flag = 1; ans = a[i]; break; } } flag ? l = m : r = m; } printf('%d %I64d\n', l,ans); } return 0; }
C,、關(guān)于預(yù)處理的總結(jié) 預(yù)處理的目的是為了減少重復(fù)的計(jì)算從而減少時(shí)間復(fù)雜度，有時(shí)一個(gè)簡(jiǎn)單的預(yù)處理能使得算法性能顯著提高,。首先我們可以按思路直接寫(xiě)一個(gè)程序,，如果復(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í), 就要用前綴思想.
HDU 4223 思路 : 目的是找一個(gè)子串, 其和的絕對(duì)值最小. 其實(shí)不用前綴思想也好寫(xiě)出來(lái), 但是我一下就想了下前綴, 因?yàn)?/span>子串還是一個(gè)區(qū)間賽. 所以求一個(gè)前綴和, 并排序, 然后一個(gè)一個(gè)相減, 這樣的差值就是某一個(gè)子串的最小值。 因?yàn)槭桥藕眯蛄说?/span>, 所以要最小一定是在某一個(gè)前綴和差值里, 然后加上一個(gè)絕對(duì)值就是了. 總之：看到區(qū)間就要聯(lián)想的前綴思想,。
#include #include #include #include using name space std; const int maxn=1e3+5; int cas=1; int ans[maxn]; int a[maxn]; int main() { int t; scanf('%d',&t); while(t--){ int n; memset(ans,0,sizeof(ans)); scanf('%d',&n); for(int i=1;i<=n;i++){ scanf('%d',&a[i]); } for(int i=1;i<=n;i++) ans[i]=ans[i-1]+a[i]; sort(ans,ans+n+1); for(int i=0;i<=n;i++) printf('%d ',ans[i]); printf('\n'); int res=ans[1]-ans[0]; for(int i=1;i<=n;i++){ if(abs(ans[i]-ans[i-1]) res = abs(ans[i]-ans[i-1]); } printf('Case %d: ',cas++); printf('%d\n',res); } }
題目描述 : 給你n個(gè)數(shù)(n < 1e5),，問(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。 思路：前綴和思想. 如果后面的數(shù)字如果大于前綴和+1 說(shuō)明他和區(qū)間沒(méi)有交集前綴和+1 這個(gè)數(shù)字就達(dá)不到就不連續(xù)了, 就輸出此時(shí)的前綴和+1,。
#include #include using name space std; const int maxn=1e5+5; int a[maxn]; int main() { int n; while(~scanf('%d',&n)){ for(int i=0;i scanf('%d',&a[i]); } sort(a,a+n); //記得排序哦. int ans = 0; for(int i=0;i if(a[i] > ans + 1) //如上面所說(shuō). 主要原因是連續(xù)的數(shù)之間是有一定的聯(lián)系的. break; ans += a[i]; } printf('%d\n',ans+1); } }
HDU 6025 思想：因?yàn)槭且獎(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 #define CLR(x) memset(x,0,sizeof(x)) using name space std; const int maxn=1e5+5; const int inf=1e9; int qian[maxn],hou[maxn]; int a[maxn]; int main() //思路求前綴和后綴GCD這樣刪數(shù)的復(fù)雜度是n. { int t; scanf('%d',&t); while(t--){ CLR(qian); CLR(hou); int n; scanf('%d',&n); for(int i=1;i<=n;i++){ scanf('%d',&a[i]); } qian[1]=a[1]; hou[1]=a[n]; for(int i=2;i<=n;i++){ qian[i]=__gcd(qian[i-1],a[i]); } for(int i=2;i<=n;i++){ hou[i]=__gcd(hou[i-1],a[n-i+1]); } int maxx=max(qian[n-1],hou[n-1]); for(int i=2;i<=n-1;i++){ int m=__gcd(qian[i-1],hou[n-i]); if(m>maxx) maxx=m; } printf('%d\n',maxx); } }
SHU 1952 已知一個(gè)長(zhǎng)度為N的數(shù)列A[1..N],。 現(xiàn)在給出Q次查詢,，每次查詢一個(gè)區(qū)間[L, R]。 對(duì)于每一個(gè)區(qū)間,，求使得(A[i] + A[j])為奇數(shù)的(i, j)的對(duì)數(shù) (L <= i< j <= R),。 Input 多組數(shù)據(jù)，第一行有一個(gè)整數(shù)T表示數(shù)據(jù)組數(shù),。(T <= 5) 之后有T組數(shù)據(jù),，每組數(shù)據(jù)第一行為兩個(gè)整數(shù)N和Q，表示數(shù)列長(zhǎng)度及查詢數(shù)量,。 (1<= N, Q <= 100000) 接著有一行N個(gè)元素的數(shù)列A[1..N],。(1 <= A[i]<= 1000) 接下來(lái)Q行，每行有兩個(gè)整數(shù)L, R,，表示查詢的區(qū)間,。(1 <= L<= R <= N) Output 對(duì)于每次詢問(wèn)，輸出一行數(shù)字,，表示區(qū)間”O(jiān)dd Pair”的對(duì)數(shù). SampleInput 1 52 15 3 4 2 15 23 SampleOutput 6 0 思路：只有當(dāng)一個(gè)奇數(shù)加一個(gè)偶數(shù)時(shí)才滿足題目要求. 所以知道該區(qū)間中奇數(shù)和偶數(shù)的個(gè)數(shù)就可以直接算,。
#include #include #include #include using name space std; const int maxn=1e5+5; int cas=1; struct math{ int odd; //結(jié)構(gòu)體中的變量會(huì)自動(dòng)付初值. int ans; }s[maxn]; int main() { int t; scanf('%d',&t); while(t--){ int n,q; scanf('%d%d',&n,&q); for(int i=1;i<=n;i++){ int x; scanf('%d',&x); if(x&1){ s[i].odd += s[i-1].odd +1; //每一個(gè)繼承前面那個(gè)的奇數(shù)和偶數(shù)個(gè)數(shù). s[i].ans += s[i-1].ans; } else{ s[i].ans += s[i-1].ans + 1; s[i].odd += s[i-1].odd; } } while(q--){ int l,r; scanf('%d%d',&l,&r); int a = s[r].odd - s[l-1].odd; int b = s[r].ans - s[l-1].ans; printf('%d\n',a*b); } } }
FZU 2129 思維題，也可以用前綴和思想,，只是有點(diǎn)難理解,。所以這兒就不給這種解法了，給一種易理解的解法,。 思路：設(shè)ans(k)為k長(zhǎng)度的子序列的個(gè)數(shù),,a[k]為第k個(gè)子序列,，那么如果a[k]和前面的數(shù)都不相同的情況下,，ans(k)]=ans(k-1)*2+1；如果前面的數(shù)字出現(xiàn)過(guò)的話,，那么就要減去最近一次出現(xiàn)a[k]這個(gè)數(shù)值的地方-1的子序列個(gè)數(shù),，因?yàn)檫@些算重復(fù)的了，而且+1也沒(méi)有了,，因?yàn)?/span>ans(a[k]上次出現(xiàn)的位置)包括了a[k]單獨(dú)算一次的情況,。
#include #include #include #include #define mod 1000000007 using name space std; const int maxn=1e6+5; int cas=1; int ans[maxn],a[maxn]; int vis[maxn]; int main() { int n; while(~scanf('%d',&n)){ memset(ans,0,sizeof(ans)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ scanf('%d',&a[i]); } for(int i=1;i<=n;i++){ if(vis[a[i]]==0){ ans[i] = (ans[i-1]*2+1)%mod; } else{ ans[i] = ((ans[i-1]*2 -ans[vis[a[i]]-1])%mod+mod)%mod; //這樣做的目的是為了防止出現(xiàn)負(fù)數(shù)(我是試出來(lái)的)因?yàn)槲艺也坏骄唧w樣列會(huì)出現(xiàn)負(fù)數(shù).所以必須這才能A。 } vis[a[i]] = i; } printf('%d\n',ans[n]%mod); } }
|
|
|
來(lái)自： 長(zhǎng)沙7喜 > 《信息課》
