noip算法分类总结（c语言）

《noip算法分类总结（c语言）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Part1.数学有关1.最大公约数Longgcd(longx,longy){returnx%y==0?y:gcd(y,x%y);}2.最小公倍数Longlcm(longx,longy){returnx*y/gcd(x,y);}3.判断素数Boolprime(longp){longx=sqrt(p)+1;If(p==1

2、

3、p==2

4、

5、p==3)returntrue;If(p%2==0

6、

7、p%3==0)returnfalse;For(inti=5;i<=x;i+=2)If(p%i==0)returnfalse;Returntrue;}4.暴力分解质因数Int

8、record[10000];VoidBaoli(longp){Longx=sqrt(p)+1,i,lc=0,ok=true;If(prime(p)==1){Lc=1;record[lc]=p;Return;}for(i=2;(i<=x)&&ok;i++){While(p%i==0){lc++;Record[lc]=i;P/=i;If(p==1){ok=false;Break;}}}}5.卡特兰数longf[1001]={0};longCountCatalan(longn){f[0]=f[1]=1;for(longi=1;i<=n;i++){f[i]=0;

9、for(longj=1;j<=i;j++)f[i]+=f[i-j]*f[j-1];}returnf[n];}Part2.排序相关1.快排VoidQuickSort(int*A,intp1,intp2){If(p1>=p2)return;Intx=A[(p1+p2)>>1],i=p1,j=p2;While(ix)j--;If(i<=j){IntTemp=A[i];A[i]=A[j];A[j]=Temp;i++;j--;}}QuickSort(A,p1,j);QuickSort(A,i,p2);

10、}2.冒泡排序VoidBubbleSort(int*A,intn){Inttemp;For(inti=1;ia[j])temp=a[j-1],a[j-1]=a[j],a[j]=temp;}3.堆排序VoidMinHeapify(intp,constintHeapSize){IntSmall=p;If(p*2<=HeapSize&&a[p*2]

11、f(Small!=p){Inttemp=a[p];a[p]=a[small];a[small]=temp;MinHeapify(small,HeapSize);}}voidExtraMin(int&HeapSize){Intans=a[1];a[1]=a[HeapSize];A[HeapSize--]=ans;MinHeapify(1);}VoidHeapsort(intn){HeapSize=n;For(inti=n/2;i>=1;i--)MinHeapify(i,HeapSize);For(inti=1;i<=n;i++)ExtraMin(HeapS

12、ize);}Part3.图论相关1.最小生成树prim算法Constintmaxint=(1<<16)-1;Intg[][],dis[],n,visit[];intPrim(){intmst=0;Intdex=1,temp=-1;For(inti=1;i<=n;i++)dis[i]=maxint;Dis[dex]=0;For(inti=1;i<=n-1;i++){Visit[dex]=1;For(intj=1;j<=n;j++){If(visit[j]==0){If(g[dex][j]!=0&&g[dex][j]

13、[j];If(temp==-1

14、

15、dis[j]

16、,vis[2001]={0};longx,y,z;classHeapClass{