NOIP算法分類總結(jié)(C語(yǔ)言

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

2、數(shù)學(xué)有關(guān)1.最大公約數(shù)Long gcd(long x,long y)return x%y=0?y:gcd(y,x%y);2.最小公倍數(shù)Long lcm(long x,long y) return x*y/gcd(x,y);3.判斷素?cái)?shù)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.暴力分解質(zhì)因數(shù)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.卡特蘭數(shù)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.圖論相關(guān)1.最小生成樹(shù)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.最小生成樹(shù)prim算法利用最小堆優(yōu)化且圖用鄰接表存儲(chǔ)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.最小生成樹(shù)kruskal算法利用并查集(的路徑壓縮)優(yōu)化int f,m,n;/m表示邊數(shù),n表示節(jié)點(diǎn)數(shù)Struct EdgeInt x,y,w;E,Temp,P;Int find(int x)If(fx!=x)fx=find(fx);Return fx;/并查集的性價(jià)比多高啊。就幾行代碼。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用于記錄已經(jīng)加入了多少條邊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.求各點(diǎn)間最短距離的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算法(寫(xiě)出來(lái)跟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差不多一模一樣。/加個(gè)堆呢？。也是跟prim差不多。自己寫(xiě)吧。6.單源最短路的SPFA算法（用隊(duì)列優(yōu)化的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);/理想狀態(tài)下是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(線段樹(shù) or 區(qū)間樹(shù))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);/從根開(kāi)始，建立鏈接結(jié)構(gòu)/建立鏈接結(jié)構(gòu)的過(guò)程void Build(Tnode *T)if(T-l)=(T-r) T-sum=AT-l; return;Tnode *L=new(Tn