|
一、倍增算法：
定義：用f[i][j]表示從i位置出發(fā)的2j個(gè)位置的信息綜合（狀態(tài)） 一個(gè)小小的問題：為什么是2j而不是3j,5j,…？因?yàn)?，假設(shè)為kj，整個(gè)算法的時(shí)間復(fù)雜度為(k-1)logk，當(dāng)k=2時(shí)，時(shí)間復(fù)雜度最小。 這個(gè)算法的三個(gè)應(yīng)用：
1.倍增ST表：
應(yīng)用：這個(gè)ST表是用來解決RMQ問題（給你n個(gè)數(shù)，m次詢問，每次詢問[l,r]這個(gè)區(qū)間的最大值），當(dāng)然，解決RMQ問題是可以用線段樹來做的，但是比較麻煩，NOIP 80%是不會(huì)用線段樹來做，還是用ST表方便。 定義：f[i][j]表示：從i到i+2j-1這2j個(gè)位置的元素最大值 初始化：f[i][0]=z[i]（第i個(gè)位置到第i+20-1個(gè)位置的最大值，對(duì)應(yīng)只有一個(gè)元素的區(qū)間） 轉(zhuǎn)移：f[i][j]=max(f[i][j-1],f[i+2(j-1)][j-1])（把[i,i+2j-1]這個(gè)區(qū)間分治為兩個(gè)區(qū)間，這兩個(gè)區(qū)間拼在一起就成了原來一個(gè)大的區(qū)間，兩個(gè)區(qū)間長(zhǎng)度都為2j-1）
//建立ST表，引自P2O5dalao的blog：https:///P2Oileen/note/816892#應(yīng)用1-st表 for(inta=1;a<=n;a++) f[a][0]=z[a];//z[]為源數(shù)據(jù)區(qū)間數(shù)組 for(intj=1;j<=logn;j++) { for(int i=1;i+z^j-1<=n;i++) f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]); //乘方是偽代碼！ } //solve ans=max(f[l][k],f[r-2^k+1][k]);
所以就有兩種情況： ①假如區(qū)間長(zhǎng)度(r-l+1)正好是2k，那么就直接訪問f[l][k]； ②假如區(qū)間長(zhǎng)度(r-l+1)是2k+p(p<2k)，也就說明2k≤(r-l+1)<2k+1，我們可以慢慢地分治下去，利用前綴和，就形成了樹狀數(shù)組那樣的東西，一段區(qū)間的最大值為劃分成兩段區(qū)間最大值max1,max2相比取較大，但是這樣太慢。 有一種更好的方法：其實(shí)我們可以用兩個(gè)長(zhǎng)度為2k的區(qū)間就一定能把這段[l,r]區(qū)間完美覆蓋起來，會(huì)有重復(fù)，但是對(duì)求最大值這件事情沒有影響，所以這段區(qū)間的最大值=max(f[l][k],f[r-2k+1][k])。 限制：不能用來計(jì)算區(qū)間和，因?yàn)橹虚g有重復(fù)部分，還有就是：不支持修改ST表！
2.樹上倍增LCA（最近公共祖先）：
一般是用線性Tarjan算法來求解（這個(gè)Tarjan算法和圖論中求有向圖強(qiáng)連通分量的Tarjan不同，都是一個(gè)人發(fā)明的），但是很難用到這個(gè)算法，原因有倆：①沒遇到這樣的題目②不會(huì)?。ㄐ弈槪?，有興趣可以了解一下。 下面介紹倍增的算法： 定義：f[i][j]表示：從樹上編號(hào)為i的節(jié)點(diǎn)向上走2j步會(huì)走到哪個(gè)節(jié)點(diǎn)。 初始化：從j=0開始考慮，也就是從i號(hào)節(jié)點(diǎn)向上走1步到達(dá)的節(jié)點(diǎn)，就是i節(jié)點(diǎn)的父親，所以：f[i][0]=father[i]。 轉(zhuǎn)移：f[i][j]=f[f[i][j-1]][j-1]，表示：從i節(jié)點(diǎn)往上走2j-1步后，再往上走2j-1步到達(dá)的點(diǎn)，等價(jià)于向上走2j步，因?yàn)?/span>2j-1+2j-1=2j。（j的范圍大概[20,30)≈nlogn，只要保證2j>節(jié)點(diǎn)數(shù)目n即可）
現(xiàn)在我們構(gòu)造出來這個(gè)f數(shù)組，下面介紹如何求兩個(gè)點(diǎn)的LCA： 定義數(shù)組depth[i]表示i這個(gè)節(jié)點(diǎn)的深度，有以下兩種情況： ①depth[p1]==depth[p2]，具有一個(gè)重要的性質(zhì)：兩個(gè)節(jié)點(diǎn)同時(shí)向上走同樣地步數(shù)，深度仍然相等，也就是說，我們讓p1,p2一步一步地往上走，當(dāng)走到同一個(gè)點(diǎn)時(shí)候，這個(gè)點(diǎn)一定是LCA！
for(intx=19;x>=0;x--) { if(f[p1][x]!=f[p2][x])//如果沒有走到同一個(gè)點(diǎn)，繼續(xù)往上走 { p1=f[p1][x];//p1往上跳 p2=f[p2][x];//p2往上跳 } } if(p1!=p2)//為什么要加這個(gè)判斷？有可能p1=p2么？是有可能的！這個(gè)判斷是防止一開始跳之前p1=p2這種情況 { p1=f[p1][0];//因?yàn)樯厦娴难h(huán)p1，p2只是走到了LCA的下方，這個(gè)判斷只是處理最后一步：把p1或p2往上跳到它的父親，就是LCA，返回即可 } return p1;//p1為LCA，返回
②depth[p1]!=depth[p2]，假如p1比較深，就讓p1往上跳到和p2深度一樣的地方。 利用倍增f數(shù)組p1往上跳的方法：定義往上走步數(shù)step=depth[p1]-depth[p2]，再利用二進(jìn)制轉(zhuǎn)換！ 舉個(gè)栗子：假如step=13，轉(zhuǎn)為二進(jìn)制=1101，可以得出13=8+4+1,：先走8步，再走4步，再走1步就好了。
int get_lca(int p1,intp2) { if(dpeth[p1] for(int x=19;x>=0;x--) { if((2^x)<=depth[p1]-depth[p2])p1=f[p1][x]; } } 下面是另一種寫法思路就不多講，YY一下就可以出來的啦~
int x=0; while (p1!=p2) { if(!x||f[p1][x]!=f[p2][x]) { p1=f[p1][x]; p2=f[p2][x]; x++; } else x--; }
3.快速冪：
按照一般思路，我們要計(jì)算ax的話，要寫一個(gè)for循環(huán)，計(jì)算a×a×a×a…這樣太?麻煩并且浪費(fèi)時(shí)間！ 這里運(yùn)用倍增來實(shí)現(xiàn)快速冪，這也是運(yùn)用到了分治的思想。 我們要求出x(x=2×k)個(gè)a的乘積，就可以分解為x/2個(gè)a的乘積的平方，這樣就省去一半計(jì)算量，如果x是奇數(shù)，就在原先的基礎(chǔ)上×a就可以了。
int pow(int a,int x)//求a^x的快速冪時(shí)間復(fù)雜度：O(logx) { int ans=1; while(x) { if(x&1) ans=(ans*a);//位運(yùn)算：x&1==1則x為奇數(shù) a=a*a; x=x>>1;//位運(yùn)算：右移一位，即將X除以2 } return ans; } 二、分治算法：
定義：將一個(gè)規(guī)模為N的問題分解為K個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。 這個(gè)算法的三個(gè)應(yīng)用：
1.二分查找：
定義：給定排序數(shù)組，查詢某個(gè)數(shù)是否在數(shù)組中 算法描述：在查找所要查找的元素時(shí)，首先與序列中間的元素進(jìn)行比較，如果大于這個(gè)元素，就在當(dāng)前序列的后半部分繼續(xù)查找，如果小于這個(gè)元素，就在當(dāng)前序列的前半部分繼續(xù)查找，直到找到相同的元素，或者所查找的序列范圍為空為止。
bool find(int x)//二分查找x是否在序列z[]中 { left=0,right=n; while(left+1!=right) { middle=(left+right)>>1; if(z[middle]>=x) right=middle; else left=middle; } } 還可以用lower_bound和upper_bound函數(shù)進(jìn)行優(yōu)化，用法詳見下：
#include #include using namespace std; int main() { int point[5]={1,3,7,7,9}; int ans; /*兩個(gè)函數(shù)傳入的：(數(shù)組名，數(shù)組名+數(shù)組長(zhǎng)度，要查找的數(shù)字)，返回的是一個(gè)地址，減去數(shù)組名即可得到數(shù)字在數(shù)組中的下標(biāo)*/ ans=upper_bound(point,point+5,7)-point;//按從小到大，7最多能插入數(shù)組point的哪個(gè)位置 printf('%d ',ans);//輸出數(shù)字在數(shù)組中的下標(biāo) ans=lower_bound(point,point+5,7)-point;////按從小到大，7最少能插入數(shù)組point的哪個(gè)位置 printf('%d\n',ans);//輸出數(shù)字在數(shù)組中的下標(biāo) return 0; } /* output： 4 2 */ 2.歸并排序（nlogn）：
是分治法的典型應(yīng)用。 歸并過程：比較a[i]和b[j]的大小，若a[i]≤b[j]，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1； 否則，將第二個(gè)有序表中的元素b[j]復(fù)制到r[k]中，并令j和k分別加上1。 如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。 歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。
3.快速排序（nlogn）：
一般在使用時(shí)候直接調(diào)用快排函數(shù)。 sort（快速排序，是C++特有的，不會(huì)退化為n2，比下面三個(gè)都要快，一般使用這個(gè)） qsort（最壞情況下為n2，最好是n，期望為nlogn） merge_sort（歸并排序，穩(wěn)定為nlongn） heap_sort（堆排序，穩(wěn)定為nlongn）
三、貪心算法：
算法思想：在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。 貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個(gè)狀態(tài)以前的過程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。 經(jīng)典例題：選最大（野題） 給你N個(gè)數(shù)，要求你選出K個(gè)數(shù)使他們的和最大。 思路：我們進(jìn)行K次貪心，每次我們都“貪”剩下的所有數(shù)中最大的，選擇后拿走，這樣就能保證我選的K個(gè)數(shù)總和最大。做法就是把N個(gè)數(shù)從大到小排序選擇前K個(gè)即可。 經(jīng)典例題：國(guó)王游戲（Luogu1080） 恰逢 H 國(guó)國(guó)慶，國(guó)王邀請(qǐng) n 位大臣來玩一個(gè)有獎(jiǎng)游戲。首先，他讓每個(gè)大臣在左、右手上面分別寫下一個(gè)整數(shù)，國(guó)王自己也在左、右手上各寫一個(gè)整數(shù)。然后，讓這 n 位大臣排成一排，國(guó)王站在隊(duì)伍的最前面。排好隊(duì)后，所有的大臣都會(huì)獲得國(guó)王獎(jiǎng)賞的若干金幣，每位大臣獲得的金幣數(shù)分別是：排在該大臣前面的所有人的左手上的數(shù)的乘積除以他自己右手上的數(shù)，然后向下取整得到的結(jié)果。 國(guó)王不希望某一個(gè)大臣獲得特別多的獎(jiǎng)賞，所以他想請(qǐng)你幫他重新安排一下隊(duì)伍的順序，使得獲得獎(jiǎng)賞最多的大臣，所獲獎(jiǎng)賞盡可能的少。注意，國(guó)王的位置始終在隊(duì)伍的最前面。 思路：此題要用到高精度，考慮最后一個(gè)大臣，顯然他很可能是金幣最多的人。我們要讓他的金幣盡量的少。之前的大臣左手的數(shù)肯定會(huì)乘起來，所以我們要使S/A/B盡量的大。（設(shè)S是左手所有數(shù)的乘積），即讓A*B盡量的大。選完最后一個(gè)后，我們把他踢掉，然后再找一個(gè)最后的大臣。如此往復(fù)，相當(dāng)于就是對(duì)A*B排序。
基于交換的證明：假設(shè)兩個(gè)相鄰的大臣i,j，而前面的人總乘積為S。 當(dāng)i在j前面時(shí)，設(shè)ans1=max(s/i.b,s*i.a/j.b); 當(dāng)j在i前面時(shí)，設(shè)ans2=max(s/j.b,s*j.a/i.b); 所以要使得i在j前面，必須要ans1
Tip：
當(dāng)我們做貪心時(shí)候不知道按照什么來排序，這時(shí)候就可以慢慢試，按照a×b、a+b、ab…這些條件來排序，看看哪個(gè)計(jì)算出來的結(jié)果最符合標(biāo)答^_^，真。。。是個(gè)有用的Tip??！
四、搜索算法：
1.三種不同的搜索問題：
①最優(yōu)性問題：例如：有N個(gè)數(shù)，從中選出K個(gè)數(shù)滿足和最大。 ②計(jì)數(shù)問題：例如：有N個(gè)數(shù)，從中選出K個(gè)數(shù)的方案數(shù)目有多少。 ③方案問題：例如：有N個(gè)數(shù)，從中選出K個(gè)數(shù)滿足已知條件，輸出其中M種方案，一般這第三類問題可以在第二類問題中解決。
2.兩種不同的搜索方法：
①BFS（廣度優(yōu)先搜索）：目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。 ②DFS（深度優(yōu)先搜索）：其過程簡(jiǎn)要來說是對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問一次。
3.搜索優(yōu)化技巧：
①剪枝：當(dāng)搜索到一個(gè)狀態(tài)時(shí)候，發(fā)現(xiàn)當(dāng)前狀態(tài)不滿足條件，就不繼續(xù)往下搜，而不是等到搜索完畢才判斷是否滿足條件。 ②BFS—meetin the middle：雙向搜索（前提是要知道最終狀態(tài)的樣子） 舉個(gè)栗子：我們有一個(gè)滿三叉樹，深度為k，我們搜索到最后一層的狀態(tài)數(shù)為3k-1，這樣要花費(fèi)的時(shí)間非常多。 已知了起始狀態(tài)和最終狀態(tài)，要用BFS求出起始到最終所經(jīng)過的那些狀態(tài)，其實(shí)可以從起始狀態(tài)往后走k/2個(gè)狀態(tài)（k為初末總狀態(tài)數(shù)），再?gòu)淖罱K的N個(gè)狀態(tài)往前走k/2個(gè)狀態(tài)，一定會(huì)在中間某個(gè)節(jié)點(diǎn)相遇，這樣聯(lián)通起了整個(gè)狀態(tài)。 時(shí)間、空間復(fù)雜度從O(X)變?yōu)?/span>O(sprt(X))。 ③卡時(shí)（最優(yōu)化問題）：我們?cè)诿鎸?duì)求最優(yōu)值問題的時(shí)候，如果找到一個(gè)更優(yōu)的值，更新一下ans的值，但是如果你還沒搜索完畢，時(shí)間已經(jīng)快要到達(dá)上限了，這時(shí)候就會(huì)爆0，意思就是要在程序運(yùn)行時(shí)間快要到達(dá)題目限制時(shí)候，把當(dāng)前我們找到的ans輸出來！這樣你就會(huì)從“得0分”變成“至少得0分”！超級(jí)有用啊啊?。?/span>
#include #include #include int t;//程序開始運(yùn)行時(shí)候當(dāng)前系統(tǒng)時(shí)間 void dfs() { /*假如題目限制時(shí)間為2000ms*/ if(clock()-t>=1995)//程序運(yùn)行時(shí)間=程序執(zhí)行到此當(dāng)前系統(tǒng)時(shí)間-程序開始系統(tǒng)時(shí)間（以ms為單位） { shuchujie();//輸出答案（保守一點(diǎn)可能需要5ms傳入輸出函數(shù)并輸出） exit(0);//直接銷毀程序！ } else { ;//繼續(xù)往下搜 } } int main() { t=clock();//記錄一下當(dāng)前時(shí)間 return 0; } 另：為感謝各位家長(zhǎng)一直以來對(duì)融科信息學(xué)的信任與支持，在雙十二來臨之際，特推出雙十二底價(jià)團(tuán)購(gòu)信息學(xué)課程，詳情點(diǎn)擊鏈接→融科教育雙十二同學(xué)“惠”，信息學(xué)課程底價(jià)瘋狂搶！（←點(diǎn)擊鏈接，了解活動(dòng)詳情吧） |
|
|
