ACM常用算法

发布 2021-05-28 13:09:28 阅读 7423

专用模板。

目录:1. 最大团。

2. 拓扑排序。

3. 最短路和次短路。

4. sap模板。

5. 已知各点度,问能否组成一个简单图。

6. kruskal

7. prim算法求最小生成树。

8. dijkstra

9 . bellman-ford

10. spfa

11. kosaraju 模板。

12. tarjan 模板。

1. 剩余定理。

2. n!中质因子p的个数。

3.拓展欧几里得。

4.三角形的各中心到顶点的距离和。

5.三角形外接圆半径周长。

6.归并排序求逆序数。

7. 求n!的位数。

8.欧拉函数。

9. miller-rabin,大整数分解,求欧拉函数。

10. 第一类斯特林数。

11.计算表达式。

12.约瑟夫问题。

13.高斯消元法。

14. baby-step,giant-step n是素数。n任意。

15. a^b%c=a ^(b%eular(c)+eular(c)) c

16.判断第二类斯特林数的奇偶性。

17.求组合数c(n,r)

18.进制转换。

算法计算积分。

20. 行列式计算。

21. 返回x 的二进制表示中从低到高的第i位。

22.高精度运算 +-

23.超级素数筛选。

1.树状数组。

2.线段树求区间的最大、小值。

3.线段树求区间和。

4.单调队列。

模板。6. 划分树,求区间第k小数。

7.最大堆,最小堆模板。

8. rmq模板求区间最大、最小值。

9.快速排序,归并排序求逆序数。

10.拓展kmp

1. 凸包面积。

2. pick公式求三角形内部有多少点

3. 多边形边上内部各多少点以及面积 pick

4. 平面最远点对。

5. 判断矩形是否在矩形内。

6. 判断点是否在多边形内。

7. 判断4个点(三维)是否共面。

8. 凸包周长。

9. 等周定理变形一直两端点和周长求最大面积。

10. 平面最近点对。

11. 单位圆最多覆盖多少点(包括边上)

12. 多边形费马点求点到多边形各个点的最短距离。

13. 矩形并周长。

14. zoj 2500 求两球体积并。

一、图论。1.最大团。

#include

#include

using namespace std;

int n,m;

int cn;//当前顶点数。

int best;//当前最大顶点数。

int vis[50];/当前解。

int bestn[50];/最优解。

int map[50][50];/临界表。

void dfs(int i)

if(i>n)

int ok=1;

for(int j=1;j

if(ok)

if(cn+n-i>best)

int main()

while(scanf("%d%d",&n,&m)==2)

cn=0;best=0;

dfs(1);

printf("%d",best);

return 0;

2.拓扑排序。

#include

#include

using namespace std;

int map[105][105],in[105],vis[105],ans[105],n;

int flag;

void dfs(int step)

if(flag) return ;

if(step==n+1)

for(int i=1;i<=n;i++)

ans[step]=i;

dfs(step+1);

vis[i]=0;

for(int j=1;j<=n;j++)

int main()

while(scanf("%d",&n)==1)

dfs(1);

return 0;

3.最短路和次短路。

#include

#include

#include

#include

using namespace std;

class node

public:

int e,w;//表示终点和边权。

const int inf=(1<<25);

int main()

int ci;

cin>>ci;

while(ci--)

int s,f;//起点和终点。

cin>>s>>f;

dijkstra 求最短路和次短路。

int flag[1005][2];

int dis[1005][2],cnt[1005][2];/0表示最短路,1表示次短路。

memset(flag,0,sizeof(flag));

for(int i=1;i<=n;i++)dis[i][0]=dis[i][1]=inf;

dis[s][0]=0;cnt[s][0]=1;//初始化。

for(int c=0;c<2*n;c++)找最短路和次短路,故要进行2*n次循环也可以改成while(1)

int temp=inf,u=-1,k;//找s-s'集合中的最短路径,u记录点的序号,k记录是最短路或者是次短路。

for(int j=1;j<=n;j++)

if(flag[j][0]==0&&temp>dis[j][0]) temp=dis[j][0],u=j,k=0;

else if(flag[j][1]==0&&temp>dis[j][1]) temp=dis[j][1],u=j,k=1;

if(temp==inf) break;//s'集合为空或者不联通,算法结束。

更新路径。flag[u][k]=1;

for(int l=0;l

int d=dis[u][k]+g[u][l].w,j=g[u][l].e;//important

4种情况。if(d

dis[j][1]=dis[j][0];cnt[j][1]=cnt[j][0];

dis[j][0]=d;cnt[j][0]=cnt[u][k];

else if(d==dis[j][0])

cnt[j][0]+=cnt[u][k];

else if(d

dis[j][1]=d;cnt[j][1]=cnt[u][k];

acm常用

acm fighting 2 1.计算几何 5 1.1 注意 5 1.2几何公式 6 1.3 多边形 8 1.4多边形切割 11 1.5 浮点函数 12 1.6 面积 18 1.7球面 18 1.8三角形 19 1.9三维几何 22 1.10 凸包 30 1.11 网格 32 1.12 圆 33 1...

工程常用算法作业五

工程常用算法 综合实践作业五。作业名称 数值求积 45组完成日期 2014 年4月4 日。数值求积 20分 采用复化simpson 复化cotes和复化romberg公式计算,精确到小数点后12位,比较不同方法的计算结果。要求 任选一种方法,但希望得到 优秀 成绩的小组必须选择复化romberg算法...

数据结构常用算法数据结构算法

void union list la,list lb union void mergelist list la,list lb,list lc else while i la len while j lb len mergelist status initlist sq sqlist l elemt...