下面是范文網(wǎng)小編收集的算法總結(jié)3篇 基本算法語(yǔ)句總結(jié)，供大家參閱。

算法總結(jié)1

　　源程序代碼：

}

　　一、自然數(shù)拆分（遞歸）

} #include<>

　　二、快速排序（遞歸）int a[100];void spilt(int t)#include<> { int k,j,l,i;main()for(k=1;k<=t;k++){int i,a[11]={0,14,12,5,6,32,8,9,15,7,10};{ printf(“%d+”,a[k]);} for(i=0;i<11;printf(“%4d”,a[i]),++i);printf(“n”);printf(“n”);j=t;l=a[j];quicksort(a,10);for(i=a[j-1];i<=l/2;i++)for(i=0;i<11;printf(“%4d”,a[i]),++i);{ a[j]=i;a[j+1]=l-i;printf(“n”);}

　　spilt(j+1);} } int partitions(int a[],int from,int to)void main(){ { int n,i;

　　int value=a[from];printf(“please enter the number:”);

　　while(from

　　a[from]=a[to];

　　while(from

++from;

　　a[to]=a[from];

}

　　a[from]=value;

　　return from;

}

　　void qsort(int a[],int from,int to){ int pivottag;if(from

{pivottag=partitions(a,from,to);qsort(a,from,pivottag-1);qsort(a,pivottag+1,to);

} scanf(“%d”,&n);

　　for(i=1;i<=n/2;i++){ a[1]=i;a[2]=n-i;spilt(2);

　　三、刪數(shù)字（貪心）

#include<> #include<> void main(){

　　int a[11]={3,0,0,0,9,8,1,4,7,5,1};

　　int k=0,i=0,j;

　　int m;

　　while(i<11)

{

　　printf(“%d ”,a[i]);

　　i++;}

　　printf(“n please input delete number:”);

　　四、全排列（遞歸）#include<> A(char a[],int k,int n){

　　int i;char temp;if(k==n)

　　for(i=0;i<=3;i++)

{printf(“%c ”,a[i]);} else {

　　for(i=k;i<=n;i++)

{ temp=a[i];

　　a[i]=a[k];

　　a[k]=temp;

　　a(a,k+1,n);

} } } main(){

　　int n;

　　char a[4]={'a','b','c','d'},temp;

　　a(a,0,3);

　　getch();

　　return 0;}

　　五、多段圖（動(dòng)態(tài)規(guī)劃）#include “”

#define n 12 //圖的頂點(diǎn)數(shù)

{ while(from=value)--to;

　　scanf(“%d”,&m);for(k=0;k

{

　　for(i=0;i<=11-k;i++)

{

　　if(a[i]>a[i+1])

{

　　for(j=i;j<10;j++)

{a[j]=a[j+1];}

　　break;//滿(mǎn)足條件就跳轉(zhuǎn)

}

} }

　　int quicksort(int a[],int n){

　　qsort(a,0,n);}

}

　　printf(“the change numbers:”);

　　for(i=0;i<11-m;i++)

{

　　if(a[i]!=0)

{ printf(“%d ”,a[i]);}

}

}

#define k 4 //圖的段數(shù) #define MAX int cost[n][n];//成本值數(shù)組

　　int path[k];//存儲(chǔ)最短路徑的數(shù)組

　　void creatgraph()//創(chuàng)建圖的(成本)鄰接矩陣 { int i,j;

　　for(i=0;i

　　for(j=0;j

　　scanf(“%d”,&cost[i][j]);//獲取成本矩陣數(shù)據(jù) }

　　void printgraph()//輸出圖的成本矩陣 { int i,j;

　　printf(“成本矩陣:n”);

　　for(i=0;i

{ for(j=0;j

　　printf(“%d ”,cost[i][j]);

　　printf(“n”);

} }

//使用向前遞推算法求多段圖的最短路徑 void FrontPath(){ int i,j,length,temp,v[n],d[n];

　　for(i=0;i

　　v[i]=0;for(i=n-2;i>=0;i--){ for(length=MAX,j=i+1;j<=n-1;j++)

　　if(cost[i][j]>0 &&(cost[i][j])+v[j]

{length=cost[i][j]+v[j];temp=j;}

　　v[i]=length;

　　d[i]=temp;

}

　　path[0]=0;//起點(diǎn)

　　path[k-1]=n-1;//最后的目標(biāo)

　　for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//將最短路徑存入數(shù)組中 }

//使用向后遞推算法求多段圖的最短路徑

　　void BackPath(){ int i,j,length,temp,v[n],d[n];

　　for(i=0;i

　　for(i=1;i<=n-1;i++)

{ for(length=MAX,j=i-1;j>=0;j--)

　　if(cost[j][i]>0 &&(cost[j][i])+v[j]

{length=cost[j][i]+v[j];temp=j;}

　　v[i]=length;

　　d[i]=temp;

}

　　path[0]=0;

　　path[k-1]=n-1;

　　for(i=k-2;i>=1;i--)(path[i])=d[path[i+1]];}

//輸出最短路徑序列 void printpath(){ int i;

　　for(i=0;i

　　printf(“%d ”,path[i]);}

　　main(){ freopen(“E:”,“r”,stdin);

　　creatgraph();

　　printgraph();

　　frontPath();

　　printf(“輸出使用向前遞推算法所得的最短路徑:n”);

　　printpath();

　　printf(“n輸出使用向后遞推算法所得的最短路徑:n”);

　　backPath();

　　printpath();printf(“n”);}

　　六、背包問(wèn)題（遞歸）int knap(int m, int n){

　　int x;

　　x=m-mn;

　　if x>0

　　sign=1;

　　else if x==0

　　sign=0;

　　else

　　sign=-1;

　　switch(sign){

　　case 0: knap=1;break;

　　case 1: if(n>1)

　　if knap(m-mn,n-1)

　　knap=1;

　　else

　　knap= knap(m,n-1);

　　else

　　knap=0;

　　case-1: if(n>1)

　　knap= knap(m,n-1);

　　else

　　knap=0;

} }

　　七、8皇后（回溯）#include <> #include <> #define N 4 int place(int k, int X[N+1]){

　　int i;

　　i=1;

　　while(i

　　if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))

　　return 0;

　　i++;

}

　　return 1;}

　　void Nqueens(int X[N+1]){

　　int k, i;

　　x[1]=0;k=1;

　　while(k>0){

　　x[k]=X[k]+1;

　　while((X[k]<=N)&&(!place(k,X)))

　　x[k]=X[k]+1;

　　if(X[k]<=N)

　　if(k==N){ for(i=1;i<=N;i++)

　　printf(“%3d”,X[i]);printf(“n”);

}

　　else{ k=k+1;

　　x[k]=0;

}

　　else k=k-1;

} }

　　void main(){

　　int n, i;

　　int X[N+1]={0};

　　clrscr();

　　Nqueens(X);

　　printf(“The end!”);}

　　八、圖著色（回溯）#include<> #define N 5 int X[N]={0,0,0,0,0};int GRAPH[N][N]={ {0,1,1,1,0}，{1,0,1,1,1}，{1,1,0,1,0}，{1,1,1,0,1}，{0,1,0,1,0} };int M=4;int count=0;int mcoloring(int k){

　　int j,t;

　　while(1){

　　NextValue(k);

　　if(X[k]==0)

　　return 0;

　　if(k==(N-1)){

　　for(t=0;t

　　printf(“%3d”,X[t]);

　　printf(“n”);

　　count++;

}

　　else

　　mcoloring(k+1);

} } int nextValue(int k){

　　int j;

　　while(1){

　　x[k]=(X[k]+1)%(M+1);

　　if(X[k]==0)

　　return 0;

　　for(j=0;j

　　if((GRAPH[k][j]==1)&&(X[k]==X[j]))

　　break;

}

　　if(j==N){

　　return 0;

}

} } void main(){

　　int k;

　　clrscr();

　　k=0;

　　mcoloring(k);

　　printf(“ncount=%dn”,count);}

　　矩陣鏈乘法（動(dòng)態(tài)規(guī)劃）? 符號(hào)S[i, j]的意義：

　　符號(hào)S(i, j)表示，使得下列公式右邊取最小值的那個(gè)k值

　　public static void matrixChain(int [ ] p, int [ ][ ] m, int [ ][ ] s)

{

　　int n=;

　　for(int i = 1;i <= n;i++)m[i][i] = 0;

　　for(int r = 2;r <= n;r++)

　　for(int i = 1;i <= n-r+1;i++){

　　int j=i+r-1;

　　m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];

　　s[i][j] = i;

　　for(int k = i+1;k < j;k++){

　　int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

　　if(t < m[i][j]){

　　m[i][j] = t;

　　s[i][j] = k;}

}

}

}

　　O的定義：

　　如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0時(shí)，有：

　　|f(n)|≤c|g(n)|，稱(chēng)函數(shù)f(n)當(dāng)n充分大時(shí)的階比g(n)低，記為

　　f(n)=O(g(n))。計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù) Ω的定義：

　　如果存在正常數(shù)c和n0，對(duì)于所有n≥n0時(shí)，有：

　　|f(n)|≥c|g(n)|，則稱(chēng)函數(shù)f(n)當(dāng)n充分大時(shí)下有界，且g(n)是它的一個(gè)下界，即f(n)的階不低于g(n)的階。記為：

　　f(n)=Ω(g(n))。Θ的定義：

　　如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n>n0，有：

　　c1|g(n)|≤f(n)≤c2|g(n)|，則記f(n)=Θ(g(n))意味著該算法在最好和最壞的情況下計(jì)算時(shí)間就一個(gè)常因子范圍內(nèi)而言是相同的。(1)多項(xiàng)式時(shí)間算法：

　　O(1)

(2)指數(shù)時(shí)間算法：

　　O(2n)

　　move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1)

　　貪心方法基本思想：

　　貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇

　　所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。

　　多段圖：

　　cOST[j]=c(j,r)+COST[r];

　　回溯法：

(假定集合Si的大小是mi)不斷地用修改過(guò)的規(guī)范函數(shù)Pi(x1,…,xi)去測(cè)試正在構(gòu)造中的n-元組的部分向量(x1,…,xi)，看其是否可能導(dǎo)致最優(yōu)解。如果判定(x1,…,xi)不可能導(dǎo)致最優(yōu)解，那么就將可能要測(cè)試的mi+1…mn個(gè)向量略去。約束條件：

(1)顯式約束：限定每一個(gè)xi只能從給定的集合Si上取值。

(2)解

　　空

　　間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿(mǎn)足顯式

　　約束條件的所有多元組，構(gòu)成了該實(shí)例

　　的一個(gè)解空間。

(3)隱式約束：規(guī)定解空間中實(shí)際上滿(mǎn)足規(guī)范函數(shù)的元

　　組，描述了xi必須彼此相關(guān)的情況?；咀龇ǎ?/p>

　　在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解：如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。

　　8皇后問(wèn)題

　　約束條件

　　限界函數(shù)：

　　子集和數(shù)問(wèn)題：

　　約束條件

　　限界函數(shù)：

　　回溯法－－術(shù)語(yǔ)：

　　活結(jié)點(diǎn)：已生成一個(gè)結(jié)點(diǎn)而它的所有兒子結(jié)點(diǎn)還沒(méi)有

　　全部生成的結(jié)點(diǎn)稱(chēng)為活結(jié)點(diǎn)。

　　e-結(jié)點(diǎn)：當(dāng)前正在生成其兒子結(jié)點(diǎn)的活結(jié)點(diǎn)叫E-結(jié)點(diǎn)。

　　死結(jié)點(diǎn)：不再進(jìn)一步擴(kuò)展或其兒子結(jié)點(diǎn)已全部生成的結(jié)點(diǎn)稱(chēng)為死結(jié)點(diǎn)。

　　使用限界函數(shù)的深度優(yōu)先節(jié)點(diǎn)生成的方法成為回溯法；E-結(jié)點(diǎn)一直保持到死為止的狀態(tài)生成的方法 稱(chēng)之為分支限界方法

　　且用限界函數(shù)幫助避免生成不包含答案結(jié)點(diǎn)子樹(shù)的狀態(tài)空間的檢索方法。區(qū)別：

　　分支限界法本質(zhì)上就是含有剪枝的回溯法，根據(jù)遞歸的條件不同，是有不同的時(shí)間復(fù)雜度的。

　　回溯法深度優(yōu)先搜索堆?；蚬?jié)點(diǎn)的所有子節(jié)點(diǎn)被遍歷后才被從棧中彈出找出滿(mǎn)足約束條件的所有解

　　分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊(duì)列，優(yōu)先隊(duì)列每個(gè)結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會(huì)找出滿(mǎn)足約束條件下的一個(gè)解或特定意義下的最優(yōu)解

　　一般如果只考慮時(shí)間復(fù)雜度二者都是指數(shù)級(jí)別的

　　可是因?yàn)榉种藿绶ù嬖谥鞣N剪枝，用起來(lái)時(shí)間還是很快的int M, W[10],X[10];void sumofsub(int s, int k, int r){

　　int j;

　　x[k]=1;

　　if(s+W[k]==M){

　　for(j=1;j<=k;j++)

　　printf(“%d ”,X[j]);

　　printf(“n”);

}

　　else

　　if((s+W[k]+W[k+1])<=M){

　　sumofsub(s+W[k],k+1,r-W[k]);

}

　　if((s+r-W[k]>=M)&&(s+W[k+1]<=M)){

　　x[k]=0;

　　sumofsub(s,k+1,r-W[k]);

} } void main(){

　　m=30;

　　w[1]=15;

　　w[2]=9;

　　w[3]=8;

　　w[4]=7;

　　w[5]=6;

　　w[6]=5;

　　w[7]=4;

　　w[8]=3;

　　w[9]=2;

　　w[10]=1;

　　sumofsub(0,1,60);}

　　p是所有可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問(wèn)題的集合。NP是所有可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問(wèn)題的集合 如果可滿(mǎn)足星月化為一個(gè)問(wèn)題L，則此問(wèn)題L是NP-難度的。如果L是NP難度的且L NP，則此問(wèn)題是NP-完全的

算法總結(jié)2

　　1.去掉超鏈接的下畫(huà)線： 在 //添加這句就行。 2.格式為：你需要添加下畫(huà)線的文字 3.獲取時(shí)間

　　我們可以通過(guò)使用DataTime這個(gè)類(lèi)來(lái)獲取當(dāng)前的時(shí)間。通過(guò)調(diào)用類(lèi)中的各種方法我們可以獲取不同的時(shí)間：如：日期（2008-09-04）、時(shí)間（12：12：12）、日期+時(shí)間（2008-09-04 12：11：10）等。

//獲取日期+時(shí)間

();

// 2008-9-4 20:02:10 ().ToString();

// 2008-9-4 20:12:12 //獲取日期

().ToString();

// 2008年9月4日 ().ToString();

// 2008-9-4 (“yyyy-MM-dd”);

// 2008-09-04 ();

// 2008-9-4 0:00:00 //獲取時(shí)間 ().ToString();

// 20:16:16 ().ToString();

// 20:16 (“hh:mm:ss”);

// 08:05:57 ();

// 20:33:50. //其他

().ToString();

// ***000 ().ToString();

// ***750 ().ToString();

// . ().ToString();

// 2008-9-4 12:19:14 ();

　　獲取年份

// 2008 ();

　　獲取月份

// 9 ();獲取星期

// Thursday ();獲取第幾天

// 248 ();

　　獲取小時(shí)

// 20 ();

　　獲取分鐘

// 31 ();

　　獲取秒數(shù)

// 45 //n為一個(gè)數(shù),可以數(shù)整數(shù),也可以事小數(shù) (n).ToString();

//時(shí)間加n年 (n).ToString();

//加n天 (n).ToString();

//加n小時(shí) (n).ToString();

//加n個(gè)月 (n).ToString();

//加n秒 (n).ToString();

//加n分 SQL語(yǔ)句使用時(shí)間和日期的函數(shù)

　　getdate():獲取系統(tǒng)當(dāng)前時(shí)間

　　dateadd(datepart,number,date):計(jì)算在一個(gè)時(shí)間的基礎(chǔ)上增加一個(gè)時(shí)間后的新時(shí)間值,比如：dateadd(yy,30,getdate())datediff(datepart,startdate,enddate):計(jì)算兩個(gè)時(shí)間的差值,比如：datediff(yy,getdate(),'2008-08-08')dataname(datepart,date):獲取時(shí)間不同部分的值，返回值為字符串 datepart(datepart,date):和datename相似，只是返回值為整型 day(date):獲取指定時(shí)間的天數(shù) month(date):獲取指定時(shí)間的月份 year(date):獲取指定時(shí)間的年份 select year(getdate())：當(dāng)前年份

算法總結(jié)3

　　算法分塊總結(jié)

　　為備戰(zhàn)2005年11月4日成都一戰(zhàn)，特將已經(jīng)做過(guò)的題目按算法分塊做一個(gè)全面詳細(xì)的總結(jié)，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設(shè)計(jì)中，時(shí)刻都要牢記要減少冗余，要以簡(jiǎn)潔高效為追求目標(biāo)。另外當(dāng)遇到陌生的問(wèn)題時(shí)，要想方設(shè)法進(jìn)行模型簡(jiǎn)化，轉(zhuǎn)化，轉(zhuǎn)化成我們熟悉的東西。

　　圖論模型的應(yīng)用

　　分層圖思想的應(yīng)用：

　　用此思想可以建立起更簡(jiǎn)潔、嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型，進(jìn)而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質(zhì)： 由于層是由復(fù)制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進(jìn)行新層的存儲(chǔ)，甚至幾乎不需要花時(shí)間去處理。由于層之間的相似性，很多計(jì)算結(jié)果都是相同的。所以我們只需對(duì)這些計(jì)算進(jìn)行一次，把結(jié)果存起來(lái)，而不需要反復(fù)計(jì)算。如此看來(lái)，雖然看起來(lái)圖變大了，但實(shí)際上問(wèn)題的規(guī)模并沒(méi)有變大。層之間是拓?fù)溆行虻摹＿@也就意味著在層之間可以很容易實(shí)現(xiàn)遞推等處理，為發(fā)現(xiàn)有效算法打下了良好的基礎(chǔ)。

　　這些特點(diǎn)說(shuō)明這個(gè)分層圖思想還是很有潛力的，尤其是各層有很多公共計(jì)算結(jié)果這一點(diǎn)，有可能大大消除冗余計(jì)算，進(jìn)而降低算法時(shí)間復(fù)雜度。二分圖最大及完備匹配的應(yīng)用： ZOJ place the robots: 二分圖最優(yōu)匹配的應(yīng)用：

　　最大網(wǎng)絡(luò)流算法的應(yīng)用：典型應(yīng)用就求圖的最小割。最小費(fèi)用最大流的應(yīng)用：

　　容量有上下界的最大流的應(yīng)用：

　　歐拉路以及歐拉回路的應(yīng)用：主要利用求歐拉路的套圈算法。最小生成樹(shù)：

　　求最小生成樹(shù)，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復(fù)雜度降為O(Vlog2V+E)，后者一般應(yīng)用于稀疏圖，其時(shí)間復(fù)雜度為O(Elog2V)。最小K度限制生成樹(shù)：

　　抽象成數(shù)學(xué)模型就是：

　　設(shè)G=(V,E,ω)是連通的無(wú)向圖，v0 ∈V是特別指定的一個(gè)頂點(diǎn),k為給定的一個(gè)正整數(shù)。首先考慮邊界情況。先求出問(wèn)題有解時(shí)k 的最小值：把v0點(diǎn)從圖中刪去后，圖中可能會(huì)出 現(xiàn)m 個(gè)連通分量，而這m 個(gè)連通分量必須通過(guò)v0來(lái)連接，所以，在圖G 的所有生成樹(shù)中 dT(v0)≥m。也就是說(shuō)，當(dāng)k

　　首先，將 v0和與之關(guān)聯(lián)的邊分別從圖中刪去，此時(shí)的圖可能不再連通，對(duì)各個(gè)連通分量，分別求最小生成樹(shù)。接著，對(duì)于每個(gè)連通分量V’，求一點(diǎn)v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過(guò)邊(v1,v0)與v0相連。于是，我們就得到了一個(gè)m度限制生成樹(shù)，不難證明，這就是最小m度限制生成樹(shù)。這一步的時(shí)間復(fù)雜度為O(Vlog2V+E)我們所求的樹(shù)是無(wú)根樹(shù)，為了解題的簡(jiǎn)便，把該樹(shù)轉(zhuǎn)化成以v0為根的有根樹(shù)。

　　假設(shè)已經(jīng)得到了最小p度限制生成樹(shù)，如何求最小p+1 度限制生成樹(shù)呢？在原先的樹(shù)中加入一條與v0相關(guān)聯(lián)的邊后，必定形成一個(gè)環(huán)。若想得到一棵p+1 度限制生成樹(shù)，需刪去一條在環(huán)上的且與v0無(wú)關(guān)聯(lián)的邊。刪去的邊的權(quán)值越大，則所得到的生成樹(shù)的權(quán)值和就越小。動(dòng)態(tài)規(guī)劃就有了用武之地。設(shè)Best(v)為路徑v0—v上與v0無(wú)關(guān)聯(lián)且權(quán)值最大的邊。定義father(v)為v的父結(jié)點(diǎn)，動(dòng)態(tài)轉(zhuǎn)移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

　　狀態(tài)共|V|個(gè)，狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度O(1)，所以總的時(shí)間復(fù)雜度為O(V)。故由最小p度限制生成樹(shù)得到最小p+1度限制生成樹(shù)的時(shí)間復(fù)雜度為O(V)。1 先求出最小m度限制生成樹(shù)；

　　2由最小m度限制生成樹(shù)得到最小m+1度限制生成樹(shù);3 當(dāng)dT(v0)=k時(shí)停止。

　　加邊和去邊過(guò)程，利用動(dòng)態(tài)規(guī)劃優(yōu)化特別值得注意。

　　次小生成樹(shù)：

　　加邊和去邊很值得注意。

　　每加入一條不在樹(shù)上的邊，總能形成一個(gè)環(huán)，只有刪去環(huán)上的一條邊，才能保證交換后仍然是生成樹(shù)，而刪去邊的權(quán)值越大，新得到的生成樹(shù)的權(quán)值和越小。具體做法：

　　首先做一步預(yù)處理，求出樹(shù)上每?jī)蓚€(gè)結(jié)點(diǎn)之間的路徑上的權(quán)值最大的邊，然后，枚舉圖中不在樹(shù)上的邊，有了剛才的預(yù)處理，我們就可以用O(1)的時(shí)間得到形成的環(huán)上的權(quán)值最大的邊。如何預(yù)處理呢？因?yàn)檫@是一棵樹(shù)，所以并不需要什么高深的算法，只要簡(jiǎn)單的BFS 即可。

　　最短路徑的應(yīng)用：

　　dijkstra 算法應(yīng)用： Folyed 算法應(yīng)用：

　　bellman-Ford 算法的應(yīng)用：

　　差分約束系統(tǒng)的應(yīng)用：

　　搜索算法

　　搜索對(duì)象和搜索順序的選取最為重要。一些麻煩題，要注意利用數(shù)據(jù)有序化，要找一個(gè)較優(yōu)的搜索出發(fā)點(diǎn)，凡是能用高效算法的地方盡量爭(zhēng)取用高效算法?；镜倪f歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應(yīng)用： 枚舉思想的應(yīng)用： ZOJ 1252 island of logic A*算法的應(yīng)用：

　　iDA*算法的應(yīng)用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索：

　　部分搜索+高效算法（比如二分匹配，動(dòng)態(tài)規(guī)劃）： ZOJ milk bottle data: 剪枝優(yōu)化探索：

　　可行性剪枝，最優(yōu)性剪枝，調(diào)整搜索順序是常用的優(yōu)化手段。

　　動(dòng)態(tài)規(guī)劃

　　動(dòng)態(tài)規(guī)劃最重要的就是狀態(tài)的選取，以及狀態(tài)轉(zhuǎn)移方程，另外還要考慮高效的預(yù)處理（以便更好更快的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移）。最常用的思想就是用枚舉最后一次操作。

　　狀態(tài)壓縮DP，又叫帶集合的動(dòng)態(tài)規(guī)劃：題目特點(diǎn)是有一維的維數(shù)特別小。類(lèi)似TSP問(wèn)題的DP：

　　狀態(tài)劃分比較困難的題目： 樹(shù)形DP：

　　四邊形不等式的應(yīng)用探索：四邊形不等式通常應(yīng)用是把O(n^3)復(fù)雜度O(n^2)

　　高檔數(shù)據(jù)結(jié)構(gòu)的應(yīng)用

　　并查集的應(yīng)用：

　　巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹(shù)的應(yīng)用：

　　總結(jié)用線段樹(shù)解題的方法

　　根據(jù)題目要求將一個(gè)區(qū)間建成線段樹(shù)，一般的題目都需要對(duì)坐標(biāo)離散。建樹(shù)時(shí)，不要拘泥于線段樹(shù)這個(gè)名字而只將線段建樹(shù)，只要是表示區(qū)間，而且區(qū)間是由單位元素(可以是一個(gè)點(diǎn)、線段、或數(shù)組中一個(gè)值)組成的，都可以建線段樹(shù)；不要拘泥于一維，根據(jù)題目要求可以建立面積樹(shù)、體積樹(shù)等等

　　樹(shù)的每個(gè)節(jié)點(diǎn)根據(jù)題目所需，設(shè)置變量記錄要求的值

　　用樹(shù)形結(jié)構(gòu)來(lái)維護(hù)這些變量：如果是求總數(shù)，則是左右兒子總數(shù)之和加上本節(jié)點(diǎn)的總數(shù)，如果要求最值，則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時(shí)，都只對(duì)O(logL)個(gè)節(jié)點(diǎn)修改這個(gè)特點(diǎn)，在O(logL)的時(shí)間內(nèi)維護(hù)修改后相關(guān)節(jié)點(diǎn)的變量。

　　在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中，要靈活的運(yùn)用子樹(shù)的收縮與葉子節(jié)點(diǎn)的釋放，避免重復(fù)操作。

　　Trie的應(yīng)用：；

　　Trie圖的應(yīng)用探索： 后綴數(shù)組的應(yīng)用研究：

　　在字符串處理當(dāng)中，后綴樹(shù)和后綴數(shù)組都是非常有力的工具，其中后綴樹(shù)了解得比較多，關(guān)于后綴數(shù)組則很少見(jiàn)于國(guó)內(nèi)的資料。其實(shí)后綴數(shù)組是后綴樹(shù)的一個(gè)非常精巧的替代品，它比后綴樹(shù)容易編程實(shí)現(xiàn)，能夠?qū)崿F(xiàn)后綴樹(shù)的很多功能而時(shí)間復(fù)雜度也不太遜色，并且，它比后綴樹(shù)所占用的空間小很多。

　　樹(shù)狀數(shù)組的應(yīng)用探索：；

　　計(jì)算幾何

　　掌握基本算法的實(shí)現(xiàn)。凸包的應(yīng)用：；

　　半平面交算法的應(yīng)用：；

　　幾何+模擬類(lèi)題目：幾何設(shè)計(jì)好算法，模擬控制好精度。掃描法：；

　　轉(zhuǎn)化法：ZOJ 1606 將求所圍的格子數(shù)，巧妙的轉(zhuǎn)化為求多邊形的面積。離散法思想的應(yīng)用：；

　　經(jīng)典算法：找平面上的最近點(diǎn)對(duì)。

　　貪心

　　矩形切割

　　二分思想應(yīng)用

　　活用經(jīng)典算法

　　利用歸并排序算法思想求數(shù)列的逆序?qū)?shù)：

　　利用快速排序算法思想，查詢(xún)N個(gè)數(shù)中的第K小數(shù)：

　　博弈問(wèn)題

　　博弈類(lèi)題目通常用三類(lèi)解法：第一類(lèi)推結(jié)論； 第二類(lèi)遞推，找N位置，P位置； 第三類(lèi)SG函數(shù)的應(yīng)用。第四類(lèi)極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類(lèi)極大極小法。

　　第一類(lèi)：推結(jié)論。典型題目： 第二類(lèi)：遞推。典型題目：

　　比如有向無(wú)環(huán)圖類(lèi)型的博弈。在一個(gè)有向圖中，我們把選手I有必勝策略的初始位置稱(chēng)為N位置(Next player winning)，其余的位置被稱(chēng)為P位置(Previous player winning)。很顯然，P位置和N位置應(yīng)該具有如下性質(zhì)：

　　1． 所有的結(jié)束位置都是P位置。

　　2． 對(duì)于每一個(gè)N位置，至少存在一種移動(dòng)可以將棋子移動(dòng)到一個(gè)P位置。3． 對(duì)于每一個(gè)P位置，它的每一種移動(dòng)都會(huì)將棋子移到一個(gè)N位置。

　　這樣，獲勝的策略就是每次都把棋子移動(dòng)到一個(gè)P位置，因?yàn)樵谝粋€(gè)P位置，你的對(duì)手只能將棋子移動(dòng)到一個(gè)N位置，然后你總有一種方法再把棋子移動(dòng)到一個(gè)P位置。一直這樣移動(dòng)，最后你一定會(huì)將棋子移動(dòng)到一個(gè)結(jié)束位置（結(jié)束位置是P位置），這時(shí)你的對(duì)手將無(wú)法在移動(dòng)棋子，你便贏得了勝利。

　　與此同時(shí)，得到了這些性質(zhì)，我們便很容易通過(guò)倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為：

　　1． 將所有的結(jié)束位置標(biāo)為P位置。

　　2． 將所有能一步到達(dá)P位置的點(diǎn)標(biāo)為N位置。

　　3． 找出所有只能到達(dá)N位置的點(diǎn)，將它們標(biāo)為P位置。

　　4． 如果在第三步中沒(méi)有找到新的被標(biāo)為P位置的點(diǎn)，則算法結(jié)束，否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置，對(duì)于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類(lèi)：SG函數(shù)的應(yīng)用。

　　關(guān)于SG函數(shù)的基本知識(shí)：對(duì)于一個(gè)有向圖(X, F)來(lái)說(shuō)，SG函數(shù)g是一個(gè)在X上的函數(shù)，并且它返回一個(gè)非負(fù)整數(shù)值，具體定義為

　　g(x)?min{n?0,n?g(y)對(duì)于所有y?F(x)}

　　1． 對(duì)于所有的結(jié)束位置x，g(x)= 0。

　　2． 對(duì)于每一個(gè)g(x)≠ 0的位置x，在它可以一步到達(dá)的位置中至少存在一個(gè)位置y使得g(y)= 0。

　　3．對(duì)于每一個(gè)g(x)＝ 0的位置x，所有可以由它一步到達(dá)的位置y都有g(shù)(y)≠ 0。

　　定理 如果g(xi)是第i個(gè)有向圖的SG函數(shù)值，i = 1,…,n，那么在由這n個(gè)有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

　　第四類(lèi)：極大極小法。

　　典型題目：ZOJ 1155：Triangle War

　　ZOJ 1993：A Number Game

　　矩陣妙用

　　矩陣最基本的妙用就是利用快速乘法O（logn）來(lái)求解遞推關(guān)系（最基本的就是求Fibonacci數(shù)列的某項(xiàng)）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目：

　　數(shù)學(xué)模型舉例

　　向量思想的應(yīng)用：

　　UVA ：注意降維和向量的規(guī)范化 ；

　　利用復(fù)數(shù)思想進(jìn)行向量旋轉(zhuǎn)。

　　UVA ：

　　遞推

　　數(shù)代集合

　　數(shù)代集合的思想：

　　aCM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數(shù)代集合思想優(yōu)化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個(gè)數(shù)不會(huì)超過(guò)100，因此可以考慮用一個(gè)數(shù)代替一個(gè)集合，首先把所有的運(yùn)算結(jié)果都用預(yù)處理算出來(lái)，到計(jì)算的時(shí)候只要用O(1)的復(fù)雜度就可以完成一次運(yùn)算。

　　組合數(shù)學(xué)

　　polya定理則是解決同構(gòu)染色計(jì)數(shù)問(wèn)題的有力工具。

　　補(bǔ)集轉(zhuǎn)化思想

　　ZOJ 單色三角形：

　　字符串相關(guān)

　　擴(kuò)展的KMP算法應(yīng)用：；最長(zhǎng)回文串； 最長(zhǎng)公共子串； 最長(zhǎng)公共前綴；

　　填充問(wèn)題

　　高精度運(yùn)算

　　三維空間問(wèn)題專(zhuān)題

　　無(wú)論什么問(wèn)題，一旦擴(kuò)展到三難空間，就變得很有難度了。三維空間的問(wèn)題，很考代碼實(shí)現(xiàn)能力。

　　其它問(wèn)題的心得

　　解決一些判斷同構(gòu)問(wèn)題的方法：同構(gòu)的關(guān)鍵在于一一對(duì)應(yīng)，而如果枚舉一一對(duì)應(yīng)的關(guān)系，時(shí)間復(fù)雜度相當(dāng)?shù)母?，利用最小表示，就能把一個(gè)事物的本質(zhì)表示出來(lái)。求最小表示時(shí)，我們一定要仔細(xì)分析，將一切能區(qū)分兩個(gè)元素的條件都在最小表示中體現(xiàn)，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當(dāng)?shù)?、高效的匹配算法（例如KMP字符匹配之類(lèi)的），來(lái)比較最小表示是否相同，這里常常要將我們熟悉的高效算法進(jìn)行推廣

算法總結(jié)3篇 基本算法語(yǔ)句總結(jié)相關(guān)文章：

★ 排序算法總結(jié)3篇 十大經(jīng)典排序算法總結(jié)

★ 算法總結(jié)材料3篇 常用算法總結(jié)