模块目录
一、 排序
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.数学有关
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 record[10000];
Void Baoli(long p){
Long x=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.卡特兰数
long f[1001]={0};
long CountCatalan(long n){
f[0]=f[1]=1;
for(long i=1;i<=n;i++){
f[i]=0;
for(long j=1;j<=i;j++)
f[i]+=f[i-j]*f[j-1];
}
return f[n];
}
Part2.排序相关
1.快排
Void QuickSort(int *A,int p1,int p2){
If(p1>=p2)return;
Int x=A[(p1+p2)>>1],i=p1,j=p2;
While(i<j){
while(A[i]<x)i++;
While(A[j]>x)j--;
If(i<=j){
Int Temp=A[i];
A[i]=A[j];
A[j]=Temp;
i++; j--;
}
}
QuickSort(A,p1,j);
QuickSort(A,i,p2);
}
2.冒泡排序
Void BubbleSort(int *A,int n){
Int temp;
For(int i=1;i<n;i++)
For(int j=i;j<=n;j++)
If(a[j-1]>a[j])
temp=a[j-1],a[j-1]=a[j],a[j]=temp;
}
3.堆排序
Void MinHeapify(int p,const int HeapSize){
Int Small=p;
If(p*2<=HeapSize&&a[p*2]<a[Small])
Small=p*2;
If(p*2+1<=Heapsize&&a[p*2+1]<a[Small])
Small=p*2+1;
If(Small!=p){
Int temp=a[p];
a[p]=a[small];
a[small]=temp;
MinHeapify(small,HeapSize);
}
}
void ExtraMin(int &HeapSize){
Int ans=a[1];
a[1]=a[HeapSize];
A[HeapSize--]=ans;
MinHeapify(1);
}
Void Heapsort(int n){
HeapSize=n;
For(int i=n/2;i>=1;i--)
MinHeapify(i,HeapSize);
For(int i=1;i<=n;i++)
ExtraMin(HeapSize);
}
Part3.图论相关
1.最小生成树prim算法
Const int maxint=(1<<16)-1;
Int g[][],dis[],n,visit[];
int Prim(){
int mst=0;
Int dex=1,temp=-1;
For(int i=1;i<=n;i++)dis[i]=maxint;
Dis[dex]=0;
For(int i=1;i<=n-1;i++){
Visit[dex]=1;
For(int j=1;j<=n;j++){
If(visit[j]==0){
If(g[dex][j]!=0&&g[dex][j]<dis[j])dis[j]=g[dex][j];
If(temp==-1||dis[j]<dis[temp])temp=j;
}
}
dex=temp;
mst+=dis[dex];
}
Return mst;
}//O(n^2)
2.最小生成树prim算法利用最小堆优化且图用邻接表存储
const long maxint=(1<<30-1);
struct Hnode{
long dis,v;
Hnode(){
v=0;
dis=maxint;
}
};
struct Gnode{
long v,w,pos,In;
struct Gnode *next;
Gnode(){
next=NULL;
v=w=In=pos=0;
}
}G[2001];
long n,m,vis[2001]={0};
long x,y,z;
class HeapClass{
public:
Hnode A[2001];
long Size;
void MinHeapify(long dep){
long Small=dep;
struct Hnode Temp;
if(2*dep<=Size&&A[Small].dis>A[2*dep].dis)
Small=2*dep;
if(2*dep+1<=Size&&A[Small].dis>A[2*dep+1].dis)
Small=2*dep+1;
if(Small!=dep){
Temp=A[Small];A[Small]=A[dep];A[dep]=Temp;
G[A[dep].v].pos=dep;
G[A[Small].v].pos=Small;
MinHeapify(Small);
}
}
struct Hnode ExtraMin(){
struct Hnode Ans=A[1];
A[1]=A[Size--];
G[A[Size+1].v].pos=Size+1;
G[A[1].v].pos=1;
MinHeapify(1);
return Ans;
}
void Decrease(long dep){
Hnode x=A[dep];
long i;
while(dep>1){
i=dep/2;
if(A[i].dis<=x.dis)break;
A[dep]=A[i],G[A[dep].v].pos=dep;
dep=i;
}
A[dep]=x;
G[A[dep].v].pos=dep;
}
}Heap;
long Prim(){
long MST=0;
Heap.A[1].v=1;
Heap.A[1].dis=0;
G[1].pos=1;
for(int i=2;i<=n;i++){
Heap.A[i].v=i;
G[i].pos=i;
}
for(i=n/2;i>=1;i--)
Heap.MinHeapify(i);
for(int k=1;k<=n;k++){
Hnode Now=Heap.ExtraMin();
MST+=Now.dis;
G[Now.v].pos=-1;
Gnode *T=G[Now.v].next;
while(T){
if((G[T->v].pos!=-1)&&((T->w)<(Heap.A[G[T->v].pos].dis))){
Heap.A[G[T->v].pos].dis=T->w;
Heap.Decrease(G[T->v].pos);
}
T=T->next;
}
}
Retrun MST;
}//O(nlogn)
3.最小生成树kruskal算法利用并查集(的路径压缩)优化
int f[],m,n; //m表示边数,n表示节点数
Struct Edge{
Int x,y,w;
}E[100000],Temp,P;
Int find(int x){
If(f[x]!=x)
f[x]=find(f[x]);
Return f[x];
}//并查集的性价比多高啊。就几行代码。。
Void Qsort(int p1,int p2){
If(p1>=p2)return;
P=E[rand()%(p2-p1)+p1];
Int i=p1,j=p2;
While(i<j){
while(E[i].w<P.w)i++;
While(E[j].w>P.w)j--;
If(i<=j){
Temp=E[i],E[i]=E[j],E[j]=Temp;
i++,j--;
}
}
Qsort(p1,j),Qsort(i,p2);
}
Int Kruskal(){
Int mst=0,cnt=0; //cnt用于记录已经加入了多少条边
For(int i=1;i<=n;i++)
f[i]=i;
Qsort(1,m);
For(int i=1;i<=m;i++){
Int fx=find(E[i].x),fy=find(E[i].y);
If(fx!=fy){
f[fx]=fy; //并查集的合并操作。。
mst+=E[i].w;
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;j<=n;j++)
If(g[i][k]>0&&g[k][j]>0&&g[i][k]+g[k][j]<g[i][j])
g[i][j]=g[i][k]+g[k][j];
}
5.单源最短路的dijstra算法(写出来跟prim的样子差不多)
Const int maxint=（1<<16)-1;
Int visit[]={0},dis[],g[][]
Void Dijstra(){
For(int i=1;i<=n;i++)dis[i]=maxint;
Int dex=1,temp=-1;
dis[dex]=0;
for(int i=1;i<=n;i++){
Visit[dex]=1;
For(int j=1;j<=n;j++){
if(visit[j]==0){
If(dis[dex]+g[dex][j]<dis[j])dis[j]=dis[dex]+g[dex][j];
If(temp==-1||dis[j]<dis[temp])temp=j;
}
}
dex=temp;
}
}//O(n^2)..跟prim差不多一模一样。。
//加个堆呢？。。也是跟prim差不多。。自己写吧。。
6.单源最短路的SPFA算法（用队列优化的bellman-ford算法）
Const int maxint=(1<<16)-1;
Int Inqueue[]={0},Queue[],head=0,tail=1;
Int dis[],g[][],dex;
Void SPFA(){
For(int i=1;i<=n;i++)dis[i]=maxint;
Inqueue[1]=1,Queue[1]=1;
Do{
head++;
Inqueue[Queue[head]]=0;
dex=Queue[head];
For(int i=1;i<=n;i++){
If(g[dex][i]>0&&g[dex][i]+dis[dex]<dis[i]){
dis[i]=g[dex][i]+dis[dex];
If(Inqueue[i]==0){
Inqueue[i]=1;
Queue[++tail]=i;
}
}
}
}while(head<tail);
}//理想状态下是O(E);
7.BFS框架
int g[][],Q[],visit[];
int begin=0,end=0;
void BFS(){
Q[end++]=1;
visit[1]=true;
while(begin<end){
int x=Q[begin++];
for(int i=1;i<=n;i++)
if(g[x][i]&&!visited[i]){
Q[end++]=i;
visit[i]=true;
}
}
}
8.DFS框架
Int g[][],visit[];
Void dfs(int dep){
if(visit[dep]==1)return;
Visit[dep]=1;
For(int i=1;i<=n;i++)
If(g[dep][i])
dfs(i);
}
Part4.数据结构
1.Binary Search Tree（二叉搜索树) = BST
struct Tnode{
int key;
struct Tnode *left,*right,*p;
};
struct BST{
struct Tnode *Root;
BST(){
Root=new(Tnode);
Root=NULL;
}
void Insert(int key){
struct Tnode *New=new(Tnode);
New->key=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)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&&!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);
return;
}
//Both LeftSon and RightSon;
if(T->left&&T->right){
struct Tnode *M=Min(T->right); //Find M, T<M<(T->right);
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 Walk(struct Tnode *T){
if(!T)return;
Walk(T->left);
cout<<T->key<<" ";
Walk(T->right);
}
};
2.Interval Tree(线段树 or 区间树)
struct Tnode{
int l,r,m,sum;
struct Tnode *left,*right,*p;
Tnode(){
l=r=m=sum=0;
left=right=p=NULL;
}
};
struct IntervalTree{
Tnode *Root;
//初始化
void Init(int n){
Root=new(Tnode);
Root->l=1;Root->r=n;Root->m=(n>>1);
Root->left=Root->right=Root->p=NULL;
Build(Root); //从根开始，建立链接结构
}
//建立链接结构的过程
void Build(Tnode *T){
if((T->l)==(T->r)){
T->sum=A[T->l];
return;
}
Tnode *L=new(Tnode),*R=new(Tnode);
T->left=L;T->right=R;
L->p=R->p=T;
L->l=T->l;L->r=T->m;L->m=(L->l+L->r)>>1;
R->l=T->m+1;R->r=T->r;R->m=(R->l+R->r)>>1;
Build(L);Build(R);
T->sum=L->sum+R->sum;
}
//后序遍历
void Walk(Tnode *T){
if(!T)return;
Walk(T->left);
Walk(T->right);
cout<<(T->l)<<" "<<(T->r)<<" "<<(T->sum)<<endl;
}
//更新在p上的节点的值；
void Update(int p,int x){
Tnode *T=Root;
while(T){
if((T->l)==(T->r)&&(T->l)==p)break;
if((T->m)<p)T=T->right;
else T=T->left;
}
T->sum=x;
//更新该节点上面所有节点sum值；
T=T->p;
while(T){
T->sum=(T->left->sum+T->right->sum);
T=T->p;
}
}
//查询某区间关键字之和；
int Ask(Tnode *T,int l,int r){
if((T->l)==l&&(T->r)==r)return T->sum;
if((T->l)==(T->r))return T->sum;
if(r<=(T->m))
return Ask(T->left,l,r);
else if(l>(T->m))
return Ask(T->right,l,r);
else return Ask(T->left,l,T->m)+Ask(T->right,T->m+1,r);
}
};
3.Treap = BSTree + Heap