ACM常用算法模板.docx

《ACM常用算法模板.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、专用模板目录：一、图论1．最大团2．拓扑排序3．最短路和次短路4．SAP模板5．已知各点度，问能否组成一个简单图6．KRUSKAL7.Prim算法求最小生成树8.Dijkstra9.Bellman-ford10.SPFA11.Kosaraju模板12.tarjan模板二、数学1.剩余定理2.N!中质因子P的个数3.拓展欧几里得4.三角形的各中心到顶点的距离和5.三角形外接圆半径周长6.归并排序求逆序数7.求N！的位数8.欧拉函数9.Miller-Rabin,大整数分解，求欧拉函数10.第一类斯特林数11.计算表达式12.约瑟夫问题13．高斯消元法14.Baby-step,

2、giant-stepn是素数.n任意15.a^b%c=a^(b%eular(c)+eular(c))%c16.判断第二类斯特林数的奇偶性17.求组合数C(n,r)18.进制转换19.Ronberg算法计算积分20.行列式计算21.返回x的二进制表示中从低到高的第i位22.高精度运算+-*/23.超级素数筛选96/96三、数据结构1．树状数组2.线段树求区间的最大、小值3.线段树求区间和4.单调队列5.KMP模板6.划分树，求区间第k小数7.最大堆，最小堆模板8.RMQ模板求区间最大、最小值9.快速排序，归并排序求逆序数.10.拓展KMP四、计算几何1.凸包面积2.Pick

3、公式求三角形内部有多少点3.多边形边上内部各多少点以及面积pick4.平面最远点对5.判断矩形是否在矩形内6.判断点是否在多边形内7.判断4个点(三维)是否共面8.凸包周长9.等周定理变形一直两端点和周长求最大面积10.平面最近点对11.单位圆最多覆盖多少点(包括边上)12.多边形费马点求点到多边形各个点的最短距离13.矩形并周长14.zoj2500求两球体积并96/96一、图论1.最大团#include#includeusingnamespacestd;intn,m;intcn;//当前顶点数intbest;//当前最大顶点数i

4、ntvis[50];//当前解intbestn[50];//最优解intmap[50][50];//临界表voiddfs(inti){if(i>n){for(intj=1;j<=n;j++)bestn[j]=vis[j];best=cn;return;}intok=1;for(intj=1;jbest){//进入右子树vis[i]=0;dfs(i+1);}}intmain

5、()96/96{while(scanf("%d%d",&n,&m)==2){memset(vis,0,sizeof(vis));memset(map,0,sizeof(map));while(m--){intp,q;scanf("%d%d",&p,&q);map[p][q]=map[q][p]=1;//无向图}cn=0;best=0;dfs(1);printf("%d",best);}return0;}2.拓扑排序#include#includeusingnamespacestd;intmap[105][105],in[105],

6、vis[105],ans[105],n;intflag;voiddfs(intstep){   if(flag)return;if(step==n+1){flag=1;printf("%d",ans[1]);for(inti=2;i<=n;i++)printf("%d",ans[i]);printf("");return;}   for(inti=1;i<=n;i++)   {       if(vis[i]==0&&in[i]==0)       {           vis[i]=1;           for(intj=1;j<=n;j++)        

7、   {               if(map[i][j]>0)               {                   map[i][j]=-map[i][j];                   in[j]--;               }           }           ans[step]=i;96/96           dfs(step+1);           vis[i]=0;           for(intj=1;j<=n;j++)           {