1、模塊目錄一、 排序1 選擇排序2 插入排序3 冒泡排序4 快速排序5 堆排序6 歸并排序7 線性時間排序二、 高精度1 高精度比較2 高精度加法3 高精度減法4 單精度乘法5 高精度乘法6 單精度除法7 高精度除法8 進制轉換三、 數論1 歐幾里德算法2 擴展歐幾里德3 求最小公倍數4 求解線形同余方程5 素數的判斷6 素數的生成四、 排列組合1 排列生成算法2 組合生成算法3 排列按序生成法4 排列字典序生成法五、 圖論1 圖的讀入2 深度優先搜索3 廣度優先搜索4 強連同分量5 拓撲排序6 最小生成樹7 最短路徑六、 背包問題1 裝滿背包2 一維價值最大背包3 二位價值最大背包Part1.

2、數學有關1.最大公約數Long gcd(long x,long y)return x%y=0?y:gcd(y,x%y);2.最小公倍數Long lcm(long x,long y) return x*y/gcd(x,y);3.判斷素數Bool prime(long p)long x=sqrt(p)+1;If(p=1|p=2|p=3)return true;If(p%2=0|p%3=0)return false;For(int i=5;i=x;i+=2)If(p%i=0)return false;Return true;4.暴力分解質因數Int record10000;Void Baoli(lo

3、ng p)Long x=sqrt(p)+1,i,lc=0,ok=true;If(prime(p)=1)Lc=1;recordlc=p;Return; for(i=2;(i=x)&ok;i+)While(p%i=0)lc+;Recordlc=i;P/=i;If(p=1)ok=false;Break;5.卡特蘭數long f1001=0;long CountCatalan(long n)f0=f1=1;for(long i=1;i=n;i+)fi=0;for(long j=1;j=p2)return;Int x=A(p1+p2)1,i=p1,j=p2;While(ij) while(Aix)j-;

4、If(i=j)Int Temp=Ai;Ai=Aj;Aj=Temp;i+; j-;QuickSort(A,p1,j);QuickSort(A,i,p2);2.冒泡排序Void BubbleSort(int *A,int n)Int temp;For(int i=1;in;i+)For(int j=i;jaj)temp=aj-1,aj-1=aj,aj=temp;3.堆排序Void MinHeapify(int p,const int HeapSize)Int Small=p;If(p*2=HeapSize&ap*2aSmall)Small=p*2;If(p*2+1=Heapsize&ap*2+1=

5、1;i-)MinHeapify(i,HeapSize);For(int i=1;i=n;i+)ExtraMin(HeapSize);Part3.圖論相關1.最小生成樹prim算法Const int maxint=(116)-1;Int g,dis,n,visit;int Prim()int mst=0;Int dex=1,temp=-1;For(int i=1;i=n;i+)disi=maxint;Disdex=0;For(int i=1;i=n-1;i+)Visitdex=1;For(int j=1;j=n;j+)If(visitj=0) If(gdexj!=0&gdexjdisj)disj

6、=gdexj;If(temp=-1|disjdistemp)temp=j;dex=temp;mst+=disdex;Return mst;/O(n2)2.最小生成樹prim算法利用最小堆優化且圖用鄰接表存儲const long maxint=(130-1);struct Hnodelong dis,v;Hnode()v=0;dis=maxint;struct Gnodelong v,w,pos,In;struct Gnode *next;Gnode()next=NULL;v=w=In=pos=0;G2001;long n,m,vis2001=0;long x,y,z;class HeapCla

7、sspublic:Hnode A2001;long Size;void MinHeapify(long dep)long Small=dep;struct Hnode Temp;if(2*depA2*dep.dis)Small=2*dep;if(2*dep+1A2*dep+1.dis)Small=2*dep+1;if(Small!=dep)Temp=ASmall;ASmall=Adep;Adep=Temp;GAdep.v.pos=dep;GASmall.v.pos=Small;MinHeapify(Small);struct Hnode ExtraMin()struct Hnode Ans=A

8、1;A1=ASize-;GASize+1.v.pos=Size+1;GA1.v.pos=1;MinHeapify(1);return Ans;void Decrease(long dep)Hnode x=Adep;long i;while(dep1)i=dep/2;if(Ai.dis=x.dis)break;Adep=Ai,GAdep.v.pos=dep;dep=i;Adep=x;GAdep.v.pos=dep;Heap;long Prim()long MST=0;Heap.A1.v=1;Heap.A1.dis=0;G1.pos=1;for(int i=2;i=1;i-)Heap.MinHea

9、pify(i);for(int k=1;kv.pos!=-1)&(T-w)v.pos.dis)Heap.AGT-v.pos.dis=T-w;Heap.Decrease(GT-v.pos);T=T-next;Retrun MST;/O(nlogn)3.最小生成樹kruskal算法利用并查集(的路徑壓縮)優化int f,m,n;/m表示邊數,n表示節點數Struct EdgeInt x,y,w;E,Temp,P;Int find(int x)If(fx!=x)fx=find(fx);Return fx;/并查集的性價比多高啊。就幾行代碼。Void Qsort(int p1,int p2)If(p1

10、=p2)return;P=Erand()%(p2-p1)+p1;Int i=p1,j=p2;While(ij)while(Ei.wP.w)j-;If(i=j)Temp=Ei,Ei=Ej,Ej=Temp;i+,j-;Qsort(p1,j),Qsort(i,p2);Int Kruskal()Int mst=0,cnt=0;/cnt用于記錄已經加入了多少條邊For(int i=1;i=n;i+)fi=i;Qsort(1,m);For(int i=1;i=m;i+)Int fx=find(Ei.x),fy=find(Ei.y);If(fx!=fy)ffx=fy;/并查集的合并操作。mst+=Ei.w;

11、cnt+;If(cnt=n-1)break;Return mst;/O(ElogE)4.求各點間最短距離的floyd算法Void Floyd()For(int k=1;k=n;k+)For(int i=1;i=n;i+)For(int j=1;j0&gkj0&gik+gkjgij)gij=gik+gkj;5.單源最短路的dijstra算法(寫出來跟prim的樣子差不多)Const int maxint=（116)-1;Int visit=0,dis,gVoid Dijstra()For(int i=1;i=n;i+)disi=maxint;Int dex=1,temp=-1;disdex=0;

12、for(int i=1;i=n;i+)Visitdex=1;For(int j=1;j=n;j+)if(visitj=0)If(disdex+gdexjdisj)disj=disdex+gdexj;If(temp=-1|disjdistemp)temp=j;dex=temp;/O(n2).跟prim差不多一模一樣。/加個堆呢？。也是跟prim差不多。自己寫吧。6.單源最短路的SPFA算法（用隊列優化的bellman-ford算法）Const int maxint=(116)-1;Int Inqueue=0,Queue,head=0,tail=1;Int dis,g,dex;Void SPFA(

13、)For(int i=1;i=n;i+)disi=maxint;Inqueue1=1,Queue1=1;Dohead+;InqueueQueuehead=0;dex=Queuehead;For(int i=1;i0&gdexi+disdexdisi)disi=gdexi+disdex;If(Inqueuei=0)Inqueuei=1;Queue+tail=i;while(headtail);/理想狀態下是O(E);7.BFS框架int g,Q,visit;int begin=0,end=0;void BFS()Qend+=1;visit1=true;while(beginend)int x=Q

14、begin+;for(int i=1;i=n;i+)if(gxi&!visitedi)Qend+=i;visiti=true;8.DFS框架Int g,visit;Void dfs(int dep)if(visitdep=1)return;Visitdep=1;For(int i=1;ikey=key;New-left=New-right=New-p=NULL;struct Tnode *F=NULL,*T=Root;while(T)F=T;if(T-key)key)T=T-left;else T=T-right;New-p=F;if(!F)Root=New;else if(F-key)key

15、)F-left=New; else F-right=New;struct Tnode *Search(int key)struct Tnode *T=Root;while(T)if(T-key)=key)return T;if(T-key)key)T=T-left;else T=T-right;struct Tnode *Min(struct Tnode *T)struct Tnode *F=NULL;while(T)F=T;T=T-left;return F;void Delete(int key)struct Tnode *T=Search(key);/NO SON;if(!T-left&

16、!T-right)if(T-p-left=T)T-p-left=NULL;else T-p-right=NULL;delete(T);return;/Only LeftSon;if(T-left&!T-right)if(T-p-left=T)T-p-left=T-left;else T-p-right=T-left;T-left-p=T-p;delete(T);return;/Only RightSon;if(!T-left&T-right)if(T-p-left=T)T-p-left=T-right;else T-p-right=T-right;T-right-p=T-p;delete(T)

17、;return;/Both LeftSon and RightSon;if(T-left&T-right)struct Tnode *M=Min(T-right);/Find M, TMright);if(M-p-left=M)M-p-left=NULL;/Remove Edge between M and M-p;else M-p-right=NULL;M-p=T-p;M-left=T-left;M-right=T-right;/Copy M to T;if(M-p-left=T)M-p-left=M;else M-p-right=M;M-left-p=M;M-right-p=M;void

18、Walk(struct Tnode *T)if(!T)return;Walk(T-left);coutkeyright);2. Interval Tree(線段樹 or 區間樹)struct Tnodeint l,r,m,sum;struct Tnode *left,*right,*p;Tnode()l=r=m=sum=0;left=right=p=NULL;struct IntervalTreeTnode *Root;/初始化void Init(int n)Root=new(Tnode);Root-l=1;Root-r=n;Root-m=(n1);Root-left=Root-right=Root-p=NULL;Build(Root);/從根開始，建立鏈接結構/建立鏈接結構的過程void Build(Tnode *T)if(T-l)=(T-r) T-sum=AT-l; return;Tnode *L=new(Tn