下面是范文網(wǎng)小編收集的算法總結3篇 基本算法語句總結，供大家參閱。
算法總結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;} 五、多段圖（動態(tài)規(guī)劃）#include “” #define n 12 //圖的頂點數(shù) { while(from 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;//滿足條件就跳轉 } } } 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];//存儲最短路徑的數(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;//起點 path[k-1]=n-1;//最后的目標 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”);} 六、背包問題（遞歸）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);} 矩陣鏈乘法（動態(tài)規(guī)劃）? 符號S[i, j]的意義： 符號S(i, j)表示，使得下列公式右邊取最小值的那個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的定義： 如果存在兩個正常數(shù)c和n0，對于所有的n≥n0時，有： |f(n)|≤c|g(n)|，稱函數(shù)f(n)當n充分大時的階比g(n)低，記為 f(n)=O(g(n))。計算時間f(n)的一個上界函數(shù) Ω的定義： 如果存在正常數(shù)c和n0，對于所有n≥n0時，有： |f(n)|≥c|g(n)|，則稱函數(shù)f(n)當n充分大時下有界，且g(n)是它的一個下界，即f(n)的階不低于g(n)的階。記為： f(n)=Ω(g(n))。Θ的定義： 如果存在正常數(shù)c1，c2和n0，對于所有的n>n0，有： c1|g(n)|≤f(n)≤c2|g(n)|，則記f(n)=Θ(g(n))意味著該算法在最好和最壞的情況下計算時間就一個常因子范圍內而言是相同的。(1)多項式時間算法： O(1) (2)指數(shù)時間算法： O(2n) move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1) 貪心方法基本思想： 貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇 所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 多段圖： cOST[j]=c(j,r)+COST[r]; 回溯法： (假定集合Si的大小是mi)不斷地用修改過的規(guī)范函數(shù)Pi(x1,…,xi)去測試正在構造中的n-元組的部分向量(x1,…,xi)，看其是否可能導致最優(yōu)解。如果判定(x1,…,xi)不可能導致最優(yōu)解，那么就將可能要測試的mi+1…mn個向量略去。約束條件： (1)顯式約束：限定每一個xi只能從給定的集合Si上取值。 (2)解 空 間：對于問題的一個實例，解向量滿足顯式 約束條件的所有多元組，構成了該實例 的一個解空間。 (3)隱式約束：規(guī)定解空間中實際上滿足規(guī)范函數(shù)的元 組，描述了xi必須彼此相關的情況。基本做法： 在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解：如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 8皇后問題 約束條件 限界函數(shù)： 子集和數(shù)問題： 約束條件 限界函數(shù)： 回溯法－－術語： 活結點：已生成一個結點而它的所有兒子結點還沒有 全部生成的結點稱為活結點。 e-結點：當前正在生成其兒子結點的活結點叫E-結點。 死結點：不再進一步擴展或其兒子結點已全部生成的結點稱為死結點。 使用限界函數(shù)的深度優(yōu)先節(jié)點生成的方法成為回溯法；E-結點一直保持到死為止的狀態(tài)生成的方法 稱之為分支限界方法 且用限界函數(shù)幫助避免生成不包含答案結點子樹的狀態(tài)空間的檢索方法。區(qū)別： 分支限界法本質上就是含有剪枝的回溯法，根據(jù)遞歸的條件不同，是有不同的時間復雜度的。 回溯法深度優(yōu)先搜索堆棧或節(jié)點的所有子節(jié)點被遍歷后才被從棧中彈出找出滿足約束條件的所有解 分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊列，優(yōu)先隊列每個結點只有一次成為活結點的機會找出滿足約束條件下的一個解或特定意義下的最優(yōu)解 一般如果只考慮時間復雜度二者都是指數(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是所有可在多項式時間內用確定算法求解的判定問題的集合。NP是所有可在多項式時間內用不確定算法求解的判定問題的集合 如果可滿足星月化為一個問題L，則此問題L是NP-難度的。如果L是NP難度的且L NP，則此問題是NP-完全的 1.去掉超鏈接的下畫線： 在 我們可以通過使用DataTime這個類來獲取當前的時間。通過調用類中的各種方法我們可以獲取不同的時間：如：日期（2008-09-04）、時間（12：12：12）、日期+時間（2008-09-04 12：11：10）等。 //獲取日期+時間 (); // 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 //獲取時間 ().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 (); 獲取小時 // 20 (); 獲取分鐘 // 31 (); 獲取秒數(shù) // 45 //n為一個數(shù),可以數(shù)整數(shù),也可以事小數(shù) (n).ToString(); //時間加n年 (n).ToString(); //加n天 (n).ToString(); //加n小時 (n).ToString(); //加n個月 (n).ToString(); //加n秒 (n).ToString(); //加n分 SQL語句使用時間和日期的函數(shù) getdate():獲取系統(tǒng)當前時間 dateadd(datepart,number,date):計算在一個時間的基礎上增加一個時間后的新時間值,比如：dateadd(yy,30,getdate())datediff(datepart,startdate,enddate):計算兩個時間的差值,比如：datediff(yy,getdate(),'2008-08-08')dataname(datepart,date):獲取時間不同部分的值，返回值為字符串 datepart(datepart,date):和datename相似，只是返回值為整型 day(date):獲取指定時間的天數(shù) month(date):獲取指定時間的月份 year(date):獲取指定時間的年份 select year(getdate())：當前年份 算法分塊總結 為備戰(zhàn)2005年11月4日成都一戰(zhàn)，特將已經(jīng)做過的題目按算法分塊做一個全面詳細的總結，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設計中，時刻都要牢記要減少冗余，要以簡潔高效為追求目標。另外當遇到陌生的問題時，要想方設法進行模型簡化，轉化，轉化成我們熟悉的東西。 圖論模型的應用 分層圖思想的應用： 用此思想可以建立起更簡潔、嚴謹?shù)臄?shù)學模型，進而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質： 由于層是由復制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進行新層的存儲，甚至幾乎不需要花時間去處理。由于層之間的相似性，很多計算結果都是相同的。所以我們只需對這些計算進行一次，把結果存起來，而不需要反復計算。如此看來，雖然看起來圖變大了，但實際上問題的規(guī)模并沒有變大。層之間是拓撲有序的。這也就意味著在層之間可以很容易實現(xiàn)遞推等處理，為發(fā)現(xiàn)有效算法打下了良好的基礎。 這些特點說明這個分層圖思想還是很有潛力的，尤其是各層有很多公共計算結果這一點，有可能大大消除冗余計算，進而降低算法時間復雜度。二分圖最大及完備匹配的應用： ZOJ place the robots: 二分圖最優(yōu)匹配的應用： 最大網(wǎng)絡流算法的應用：典型應用就求圖的最小割。最小費用最大流的應用： 容量有上下界的最大流的應用： 歐拉路以及歐拉回路的應用：主要利用求歐拉路的套圈算法。最小生成樹： 求最小生成樹，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復雜度降為O(Vlog2V+E)，后者一般應用于稀疏圖，其時間復雜度為O(Elog2V)。最小K度限制生成樹： 抽象成數(shù)學模型就是： 設G=(V,E,ω)是連通的無向圖，v0 ∈V是特別指定的一個頂點,k為給定的一個正整數(shù)。首先考慮邊界情況。先求出問題有解時k 的最小值：把v0點從圖中刪去后，圖中可能會出 現(xiàn)m 個連通分量，而這m 個連通分量必須通過v0來連接，所以，在圖G 的所有生成樹中 dT(v0)≥m。也就是說，當k 首先，將 v0和與之關聯(lián)的邊分別從圖中刪去，此時的圖可能不再連通，對各個連通分量，分別求最小生成樹。接著，對于每個連通分量V’，求一點v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過邊(v1,v0)與v0相連。于是，我們就得到了一個m度限制生成樹，不難證明，這就是最小m度限制生成樹。這一步的時間復雜度為O(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡便，把該樹轉化成以v0為根的有根樹。 假設已經(jīng)得到了最小p度限制生成樹，如何求最小p+1 度限制生成樹呢？在原先的樹中加入一條與v0相關聯(lián)的邊后，必定形成一個環(huán)。若想得到一棵p+1 度限制生成樹，需刪去一條在環(huán)上的且與v0無關聯(lián)的邊。刪去的邊的權值越大，則所得到的生成樹的權值和就越小。動態(tài)規(guī)劃就有了用武之地。設Best(v)為路徑v0—v上與v0無關聯(lián)且權值最大的邊。定義father(v)為v的父結點，動態(tài)轉移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 狀態(tài)共|V|個，狀態(tài)轉移的時間復雜度O(1)，所以總的時間復雜度為O(V)。故由最小p度限制生成樹得到最小p+1度限制生成樹的時間復雜度為O(V)。1 先求出最小m度限制生成樹； 2由最小m度限制生成樹得到最小m+1度限制生成樹;3 當dT(v0)=k時停止。 加邊和去邊過程，利用動態(tài)規(guī)劃優(yōu)化特別值得注意。 次小生成樹： 加邊和去邊很值得注意。 每加入一條不在樹上的邊，總能形成一個環(huán)，只有刪去環(huán)上的一條邊，才能保證交換后仍然是生成樹，而刪去邊的權值越大，新得到的生成樹的權值和越小。具體做法： 首先做一步預處理，求出樹上每兩個結點之間的路徑上的權值最大的邊，然后，枚舉圖中不在樹上的邊，有了剛才的預處理，我們就可以用O(1)的時間得到形成的環(huán)上的權值最大的邊。如何預處理呢？因為這是一棵樹，所以并不需要什么高深的算法，只要簡單的BFS 即可。 最短路徑的應用： dijkstra 算法應用： Folyed 算法應用： bellman-Ford 算法的應用： 差分約束系統(tǒng)的應用： 搜索算法 搜索對象和搜索順序的選取最為重要。一些麻煩題，要注意利用數(shù)據(jù)有序化，要找一個較優(yōu)的搜索出發(fā)點，凡是能用高效算法的地方盡量爭取用高效算法。基本的遞歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應用： 枚舉思想的應用： ZOJ 1252 island of logic A*算法的應用： iDA*算法的應用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，動態(tài)規(guī)劃）： ZOJ milk bottle data: 剪枝優(yōu)化探索： 可行性剪枝，最優(yōu)性剪枝，調整搜索順序是常用的優(yōu)化手段。 動態(tài)規(guī)劃 動態(tài)規(guī)劃最重要的就是狀態(tài)的選取，以及狀態(tài)轉移方程，另外還要考慮高效的預處理（以便更好更快的實現(xiàn)狀態(tài)轉移）。最常用的思想就是用枚舉最后一次操作。 狀態(tài)壓縮DP，又叫帶集合的動態(tài)規(guī)劃：題目特點是有一維的維數(shù)特別小。類似TSP問題的DP： 狀態(tài)劃分比較困難的題目： 樹形DP： 四邊形不等式的應用探索：四邊形不等式通常應用是把O(n^3)復雜度O(n^2) 高檔數(shù)據(jù)結構的應用 并查集的應用： 巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹的應用： 總結用線段樹解題的方法 根據(jù)題目要求將一個區(qū)間建成線段樹，一般的題目都需要對坐標離散。建樹時，不要拘泥于線段樹這個名字而只將線段建樹，只要是表示區(qū)間，而且區(qū)間是由單位元素(可以是一個點、線段、或數(shù)組中一個值)組成的，都可以建線段樹；不要拘泥于一維，根據(jù)題目要求可以建立面積樹、體積樹等等 樹的每個節(jié)點根據(jù)題目所需，設置變量記錄要求的值 用樹形結構來維護這些變量：如果是求總數(shù)，則是左右兒子總數(shù)之和加上本節(jié)點的總數(shù)，如果要求最值，則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時，都只對O(logL)個節(jié)點修改這個特點，在O(logL)的時間內維護修改后相關節(jié)點的變量。 在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中，要靈活的運用子樹的收縮與葉子節(jié)點的釋放，避免重復操作。 Trie的應用：； Trie圖的應用探索： 后綴數(shù)組的應用研究： 在字符串處理當中，后綴樹和后綴數(shù)組都是非常有力的工具，其中后綴樹了解得比較多，關于后綴數(shù)組則很少見于國內的資料。其實后綴數(shù)組是后綴樹的一個非常精巧的替代品，它比后綴樹容易編程實現(xiàn)，能夠實現(xiàn)后綴樹的很多功能而時間復雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。 樹狀數(shù)組的應用探索：； 計算幾何 掌握基本算法的實現(xiàn)。凸包的應用：； 半平面交算法的應用：； 幾何+模擬類題目：幾何設計好算法，模擬控制好精度。掃描法：； 轉化法：ZOJ 1606 將求所圍的格子數(shù)，巧妙的轉化為求多邊形的面積。離散法思想的應用：； 經(jīng)典算法：找平面上的最近點對。 貪心 矩形切割 二分思想應用 活用經(jīng)典算法 利用歸并排序算法思想求數(shù)列的逆序對數(shù)： 利用快速排序算法思想，查詢N個數(shù)中的第K小數(shù)： 博弈問題 博弈類題目通常用三類解法：第一類推結論； 第二類遞推，找N位置，P位置； 第三類SG函數(shù)的應用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。 第一類：推結論。典型題目： 第二類：遞推。典型題目： 比如有向無環(huán)圖類型的博弈。在一個有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應該具有如下性質： 1． 所有的結束位置都是P位置。 2． 對于每一個N位置，至少存在一種移動可以將棋子移動到一個P位置。3． 對于每一個P位置，它的每一種移動都會將棋子移到一個N位置。 這樣，獲勝的策略就是每次都把棋子移動到一個P位置，因為在一個P位置，你的對手只能將棋子移動到一個N位置，然后你總有一種方法再把棋子移動到一個P位置。一直這樣移動，最后你一定會將棋子移動到一個結束位置（結束位置是P位置），這時你的對手將無法在移動棋子，你便贏得了勝利。 與此同時，得到了這些性質，我們便很容易通過倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為： 1． 將所有的結束位置標為P位置。 2． 將所有能一步到達P位置的點標為N位置。 3． 找出所有只能到達N位置的點，將它們標為P位置。 4． 如果在第三步中沒有找到新的被標為P位置的點，則算法結束，否則轉到步驟2。這樣我們便確定了所有位置，對于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數(shù)的應用。 關于SG函數(shù)的基本知識：對于一個有向圖(X, F)來說，SG函數(shù)g是一個在X上的函數(shù)，并且它返回一個非負整數(shù)值，具體定義為 g(x)?min{n?0,n?g(y)對于所有y?F(x)} 1． 對于所有的結束位置x，g(x)= 0。 2． 對于每一個g(x)≠ 0的位置x，在它可以一步到達的位置中至少存在一個位置y使得g(y)= 0。 3．對于每一個g(x)＝ 0的位置x，所有可以由它一步到達的位置y都有g(y)≠ 0。 定理 如果g(xi)是第i個有向圖的SG函數(shù)值，i = 1,…,n，那么在由這n個有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四類：極大極小法。 典型題目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩陣妙用 矩陣最基本的妙用就是利用快速乘法O（logn）來求解遞推關系（最基本的就是求Fibonacci數(shù)列的某項）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目： 數(shù)學模型舉例 向量思想的應用： UVA ：注意降維和向量的規(guī)范化 ； 利用復數(shù)思想進行向量旋轉。 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的元素個數(shù)不會超過100，因此可以考慮用一個數(shù)代替一個集合，首先把所有的運算結果都用預處理算出來，到計算的時候只要用O(1)的復雜度就可以完成一次運算。 組合數(shù)學 polya定理則是解決同構染色計數(shù)問題的有力工具。 補集轉化思想 ZOJ 單色三角形： 字符串相關 擴展的KMP算法應用：；最長回文串； 最長公共子串； 最長公共前綴； 填充問題 高精度運算 三維空間問題專題 無論什么問題，一旦擴展到三難空間，就變得很有難度了。三維空間的問題，很考代碼實現(xiàn)能力。 其它問題的心得 解決一些判斷同構問題的方法：同構的關鍵在于一一對應，而如果枚舉一一對應的關系，時間復雜度相當?shù)母撸米钚”硎?，就能把一個事物的本質表示出來。求最小表示時，我們一定要仔細分析，將一切能區(qū)分兩個元素的條件都在最小表示中體現(xiàn)，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當?shù)摹⒏咝У钠ヅ渌惴ǎɡ鏚MP字符匹配之類的），來比較最小表示是否相同，這里常常要將我們熟悉的高效算法進行推廣 算法總結3篇 基本算法語句總結相關文章：算法總結2
算法總結3