16个ACM经典算法介绍

目录目录 (1)Graph 图论 (3)|DAG的深度优先搜索标记 (3)|无向图找桥 (3)|无向图连通度(割) (3)|最大团问题DP+DFS (3)|欧拉路径O(E) (3)|D IJKSTRA数组实现O（N^2） (3)|D IJKSTRA O(E* LOG E) (4)|B ELLMAN F ORD单源最短路O(VE) (4)|SPFA(S HORTEST P ATH F ASTER A LGORITHM) (4)|第K短路（D IJKSTRA） (5)|第K短路（A*） (5)|P RIM求MST (6)|次小生成树O(V^2) (6)|最小生成森林问题(K颗树)O(MLOGM) (6)|有向图最小树形图 (6)|M INIMAL S TEINER T REE (6)|T ARJAN强连通分量 (7)|弦图判断 (7)|弦图的PERFECT ELIMINATION点排列 (7)|稳定婚姻问题O(N^2) (7)|拓扑排序 (8)|无向图连通分支(DFS/BFS邻接阵) (8)|有向图强连通分支(DFS/BFS邻接阵)O(N^2) (8)|有向图最小点基(邻接阵)O(N^2) (9)|F LOYD求最小环 (9)|2-SAT问题 (9)Network 网络流 (11)|二分图匹配（匈牙利算法DFS实现） (11)|二分图匹配（匈牙利算法BFS实现） (11)|二分图匹配（H OPCROFT－C ARP的算法） (11)|二分图最佳匹配（KUHN MUNKRAS算法O(M*M*N)）..11 |无向图最小割O(N^3) (12)|有上下界的最小(最大)流 (12)|D INIC最大流O(V^2*E) (12)|HLPP最大流O(V^3) (13)|最小费用流O(V*E* F).......................................13|最小费用流O(V^2* F). (14)|最佳边割集 (15)|最佳点割集 (15)|最小边割集 (15)|最小点割集（点连通度） (16)|最小路径覆盖O(N^3) (16)|最小点集覆盖 (16)Structure 数据结构 (17)|求某天是星期几 (17)|左偏树合并复杂度O(LOG N) (17)|树状数组 (17)|二维树状数组 (17)|T RIE树(K叉) (17)|T RIE树(左儿子又兄弟) (18)|后缀数组O(N* LOG N) (18)|后缀数组O(N) (18)|RMQ离线算法O(N*LOG N)+O(1) (19)|RMQ(R ANGE M INIMUM/M AXIMUM Q UERY)-ST算法(O(NLOGN +Q)) (19)|RMQ离线算法O(N*LOG N)+O(1)求解LCA (19)|LCA离线算法O(E)+O(1) (20)|带权值的并查集 (20)|快速排序 (20)|2台机器工作调度 (20)|比较高效的大数 (20)|普通的大数运算 (21)|最长公共递增子序列O(N^2) (22)|0-1分数规划 (22)|最长有序子序列（递增/递减/非递增/非递减） (22)|最长公共子序列 (23)|最少找硬币问题（贪心策略-深搜实现） (23)|棋盘分割 (23)|汉诺塔 (23)|STL中的PRIORITY_QUEUE (24)|堆栈 (24)|区间最大频率 (24)|取第K个元素 (25)|归并排序求逆序数 (25)|逆序数推排列数 (25)|二分查找 (25)|二分查找（大于等于V的第一个值） (25)|所有数位相加 (25)Number 数论 (26)|递推求欧拉函数PHI(I) (26)|单独求欧拉函数PHI(X) (26)|GCD最大公约数 (26)|快速GCD (26)|扩展GCD (26)|模线性方程 A * X = B (% N) (26)|模线性方程组 (26)|筛素数[1..N] (26)|高效求小范围素数[1..N] (26)|随机素数测试(伪素数原理) (26)|组合数学相关 (26)|P OLYA计数 (27)|组合数C(N, R) (27)|最大1矩阵 (27)|约瑟夫环问题（数学方法） (27)|约瑟夫环问题（数组模拟） (27)|取石子游戏1 (27)|集合划分问题 (27)|大数平方根（字符串数组表示） (28)|大数取模的二进制方法 (28)|线性方程组A[][]X[]=B[] (28)|追赶法解周期性方程 (28)|阶乘最后非零位,复杂度O(NLOGN) (29)递归方法求解排列组合问题 (30)|类循环排列 (30)|全排列 (30)|不重复排列 (30)|全组合 (31)|不重复组合 (31)|应用 (31)模式串匹配问题总结 (32)|字符串H ASH (32)|KMP匹配算法O(M+N) (32)|K ARP-R ABIN字符串匹配 (32)|基于K ARP-R ABIN的字符块匹配 (32)|函数名: STRSTR (32)|BM算法的改进的算法S UNDAY A LGORITHM (32)|最短公共祖先（两个长字符串） (33)|最短公共祖先（多个短字符串）...............................33Geometry 计算几何.. (34)|G RAHAM求凸包O(N* LOG N) (34)|判断线段相交 (34)|求多边形重心 (34)|三角形几个重要的点 (34)|平面最近点对O(N* LOG N) (34)|L IUCTIC的计算几何库 (35)|求平面上两点之间的距离 (35)|(P1-P0)*(P2-P0)的叉积 (35)|确定两条线段是否相交 (35)|判断点P是否在线段L上 (35)|判断两个点是否相等 (35)|线段相交判断函数 (35)|判断点Q是否在多边形内 (35)|计算多边形的面积 (35)|解二次方程A X^2+B X+C=0 (36)|计算直线的一般式A X+B Y+C=0 (36)|点到直线距离 (36)|直线与圆的交点，已知直线与圆相交 (36)|点是否在射线的正向 (36)|射线与圆的第一个交点 (36)|求点P1关于直线LN的对称点P2 (36)|两直线夹角（弧度） (36)ACM/ICPC竞赛之STL (37)ACM/ICPC竞赛之STL简介 (37)ACM/ICPC竞赛之STL--PAIR (37)ACM/ICPC竞赛之STL--VECTOR (37)ACM/ICPC竞赛之STL--ITERATOR简介 (38)ACM/ICPC竞赛之STL--STRING (38)ACM/ICPC竞赛之STL--STACK/QUEUE (38)ACM/ICPC竞赛之STL--MAP (40)ACM/ICPC竞赛之STL--ALGORITHM (40)STL IN ACM (41)头文件 (42)线段树 (43)求矩形并的面积（线段树+离散化+扫描线） (43)求矩形并的周长（线段树+离散化+扫描线） (44)Graph 图论/*==================================================*\| DAG的深度优先搜索标记| INIT: edge[][]邻接矩阵; pre[], post[], tag全置0;| CALL: dfstag(i, n); pre/post:开始/结束时间\*==================================================*/int edge[V][V], pre[V], post[V], tag;void dfstag(int cur, int n){ // vertex: 0 ~ n-1pre[cur] = ++tag;for (int i=0; i<n; ++i) if (edge[cur][i]) {if (0 == pre[i]) {printf("Tree Edge!\n");dfstag(i,n);} else {if (0 == post[i]) printf("Back Edge!\n");else if (pre[i] > pre[cur])printf("Down Edge!\n");else printf("Cross Edge!\n");}}post[cur] = ++tag;}/*==================================================*\| 无向图找桥| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],bridge 置0;| CALL: dfs(0, -1, 1, n);\*==================================================*/int bridge, edge[V][V], anc[V], pre[V], vis[V];void dfs(int cur, int father, int dep, int n){ // vertex: 0 ~ n-1if (bridge) return;vis[cur] = 1; pre[cur] = anc[cur] = dep;for (int i=0; i<n; ++i) if (edge[cur][i]) {if (i != father && 1 == vis[i]) {if (pre[i] < anc[cur])anc[cur] = pre[i];//back edge}if (0 == vis[i]) { //tree edgedfs(i,cur,dep+1,n);if (bridge) return;if (anc[i] < anc[cur]) anc[cur] = anc[i];if (anc[i] > pre[cur]) { bridge = 1; return; } }}vis[cur] = 2;}/*==================================================*\| 无向图连通度(割)| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],deg[]置为0;| CALL: dfs(0, -1, 1, n);| k=deg[0], deg[i]+1(i=1…n-1)为删除该节点后得到的连通图个数| 注意:0作为根比较特殊!\*==================================================*/int edge[V][V], anc[V], pre[V], vis[V], deg[V];void dfs(int cur, int father, int dep, int n){// vertex: 0 ~ n-1int cnt = 0;vis[cur] = 1; pre[cur] = anc[cur] = dep;for (int i=0; i<n; ++i) if (edge[cur][i]) {if (i != father && 1 == vis[i]) {if (pre[i] < anc[cur])anc[cur] = pre[i];//back edge}if (0 == vis[i]) { //tree edgedfs(i,cur,dep+1,n);++cnt; // 分支个数if (anc[i] < anc[cur]) anc[cur] = anc[i];if ((cur==0 && cnt>1) ||(cnt!=0 && anc[i]>=pre[cur]))++deg[cur];// link degree of a vertex }}vis[cur] = 2;} /*==================================================*\| 最大团问题 DP + DFS| INIT: g[][]邻接矩阵;| CALL: res = clique(n);\*==================================================*/int g[V][V], dp[V], stk[V][V], mx;int dfs(int n, int ns, int dep){if (0 == ns) {if (dep > mx) mx = dep;return 1;}int i, j, k, p, cnt;for (i = 0; i < ns; i++) {k = stk[dep][i]; cnt = 0;if (dep + n - k <= mx) return 0;if (dep + dp[k] <= mx) return 0;for (j = i + 1; j < ns; j++) {p=stk[dep][j];if (g[k][p]) stk[dep + 1][cnt++] = p;}dfs(n, cnt, dep + 1);}return 1;}int clique(int n){int i, j, ns;for (mx = 0, i = n - 1; i >= 0; i--) {// vertex: 0 ~ n-1for (ns = 0, j = i + 1; j < n; j++)if (g[i][j]) stk[1][ ns++ ] = j;dfs(n, ns, 1); dp[i] = mx;}return mx;}/*==================================================*\| 欧拉路径O(E)| INIT: adj[][]置为图的邻接表; cnt[a]为a点的邻接点个数;| CALL: elpath(0); 注意:不要有自向边\*==================================================*/int adj[V][V], idx[V][V], cnt[V], stk[V], top;int path(int v){for (int w ; cnt[v] > 0; v = w) {stk[ top++ ] = v;w = adj[v][ --cnt[v] ];adj[w][ idx[w][v] ] = adj[w][ --cnt[w] ];// 处理的是无向图—-边是双向的，删除v->w后，还要处理删除w->v}return v;}void elpath (int b, int n){ // begin from b int i, j;for (i = 0; i < n; ++i) // vertex: 0 ~ n-1 for (j = 0; j < cnt[i]; ++j)idx[i][ adj[i][j] ] = j;printf("%d", b);for (top = 0; path(b) == b && top != 0; ) {b = stk[ --top ];printf("-%d", b);}printf("\n");}/*==================================================*\| Dijkstra数组实现O（N^2）| Dijkstra --- 数组实现(在此基础上可直接改为STL的Queue实现)| lowcost[] --- beg到其他点的最近距离| path[] -- beg为根展开的树，记录父亲结点\*==================================================*/#define INF 0x03F3F3F3Fconst int N;int path[N], vis[N];void Dijkstra(int cost[][N], int lowcost[N], int n, int beg){ int i, j, min;memset(vis, 0, sizeof(vis));vis[beg] = 1;for (i=0; i<n; i++){lowcost[i] = cost[beg][i]; path[i] = beg;}lowcost[beg] = 0;path[beg] = -1; // 树根的标记int pre = beg;for (i=1; i<n; i++){min = INF;dist[v] = dist[u] + c;for (j=0; j<n; j++)// 下面的加法可能导致溢出,INF 不能取太大if (vis[j]==0 &&lowcost[pre]+cost[pre][j]<lowcost[j]){lowcost[j] =lowcost[pre] + cost[pre][j]; path[j] = pre; } for (j=0; j<n; j++) if (vis[j] == 0 && lowcost[j] < min){ min = lowcost[j]; pre = j; } vis[pre] = 1; } } /*==================================================*\ | Dijkstra O(E * log E) | INIT: 调用init(nv, ne)读入边并初始化; | CALL: dijkstra(n, src); dist[i]为src 到i 的最短距离 \*==================================================*/ #define typec int // type of cost const typec inf = 0x3f3f3f3f; // max of cost typec cost[E], dist[V]; int e, pnt[E], nxt[E], head[V], prev[V], vis[V]; struct qnode { int v; typec c; qnode (int vv = 0, typec cc = 0) : v(vv), c(cc) {} bool operator < (const qnode& r) const { return c>r.c; } }; void dijkstra(int n, const int src){ qnode mv; int i, j, k, pre; priority_queue<qnode> que; vis[src] = 1; dist[src] = 0; que.push(qnode(src, 0)); for (pre = src, i=1; i<n; i++) { for (j = head[pre]; j != -1; j = nxt[j]) { k = pnt[j]; if (vis[k] == 0 && dist[pre] + cost[j] < dist[k]){ dist[k] =dist[pre] + cost[j]; que.push(qnode(pnt[j], dist[k])); prev[k] = pre; } } while (!que.empty() && vis[que.top().v] == 1) que.pop(); if (que.empty()) break ; mv = que.top(); que.pop(); vis[pre = mv.v] = 1; } } inline void addedge(int u, int v, typec c){ pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++; } void init(int nv, int ne){ int i, u, v; typec c; e = 0;memset(head, -1, sizeof (head));memset(vis, 0, sizeof (vis));memset(prev, -1, sizeof (prev));for (i = 0; i < nv; i++) dist[i] = inf;for (i = 0; i < ne; ++i) {scanf("%d%d%d", &u, &v, &c);// %d: type of cost addedge(u, v, c); // vertex: 0 ~ n-1, 单向边 }}/*==================================================*\| BellmanFord 单源最短路O(VE)| 能在一般情况下，包括存在负权边的情况下，解决单源最短路径问题| INIT: edge[E][3]为边表| CALL: bellman(src);有负环返回0;dist[i]为src 到i 的最短距| 可以解决差分约束系统: 需要首先构造约束图，构造不等式时>=表示求最小值, 作为最长路，<=表示求最大值, 作为最短路 （v-u <= c:a[u][v] = c ）\*==================================================*/#define typec int // type of costconst typec inf=0x3f3f3f3f; // max of costint n, m, pre[V], edge[E][3];typec dist[V];int relax (int u, int v, typec c){if (dist[v] > dist[u] + c) {pre[v] = u; return 1; } return 0; } int bellman (int src){ int i, j;for (i=0; i<n; ++i) { dist[i] = inf; pre[i] = -1; } dist[src] = 0; bool flag; for (i=1; i<n; ++i){ flag = false; // 优化 for (j=0; j<m; ++j) { if( 1 == relax(edge[j][0], edge[j][1], edge[j][2]) ) flag = true; } if( !flag ) break; } for (j=0; j<m; ++j) { if (1 == relax(edge[j][0], edge[j][1], edge[j][2])) return 0; // 有负圈 } return 1; } /*==================================================*\ | SPFA(Shortest Path Faster Algorithm) Bellman-Ford 算法的一种队列实现，减少了不必要的冗余计算。

学习编程的十大经典算法学习编程是现代社会中一个非常重要的技能，而掌握经典算法是成为一个优秀的程序员的必备条件之一。

下面将介绍十大经典算法，详细解释它们的原理和应用。

1. 二分查找算法（Binary Search）二分查找算法是一种在有序数组中快速查找特定元素的算法。

它将查找范围不断缩小一半，直到找到目标元素或确定目标元素不存在。

二分查找算法的时间复杂度为O(log n)。

2. 冒泡排序算法（Bubble Sort）冒泡排序算法是一种简单但效率较低的排序算法。

它通过多次遍历数组，将相邻的元素进行比较并交换位置，使得较大（或较小）的元素逐渐移动到数组的末尾。

冒泡排序的时间复杂度为O(n^2)。

3. 快速排序算法（Quick Sort）快速排序算法是一种高效的排序算法。

它通过选择一个基准元素，将数组分为左右两个子数组，并对子数组进行递归排序。

快速排序算法的时间复杂度为O(n log n)，在大多数情况下具有较好的性能。

4. 归并排序算法（Merge Sort）归并排序算法是一种分治思想的排序算法。

它将数组一分为二，递归地对子数组进行排序，然后将排好序的子数组合并成一个有序的数组。

归并排序算法的时间复杂度为O(n log n)，稳定且适用于大规模数据的排序。

5. 插入排序算法（Insertion Sort）插入排序算法是一种简单且稳定的排序算法。

它通过将未排序的元素逐个插入已排序的序列中，以达到整体有序的目的。

插入排序的时间复杂度为O(n^2)，但对于小规模数据或基本有序的数组，插入排序具有较好的性能。

6. 选择排序算法（Selection Sort）选择排序算法是一种简单但效率较低的排序算法。

它通过多次遍历数组，选择出最小（或最大）的元素，并放置到已排序的序列中。

选择排序的时间复杂度为O(n^2)，但它适用于小规模数据或交换成本较高的情况。

7. 堆排序算法（Heap Sort）堆排序算法是一种高效的排序算法。

专用模板目录：一、图论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,giant-step n是素数.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.超级素数筛选三、数据结构1．树状数组2.线段树求区间的最大、小值3.线段树求区间和4.单调队列5.KMP模板6. 划分树，求区间第k小数7.最大堆，最小堆模板8. RMQ模板求区间最大、最小值9.快速排序，归并排序求逆序数.10.拓展KMP四、计算几何1.凸包面积2.Pick公式求三角形内部有多少点3.多边形边上内部各多少点以及面积pick4.平面最远点对5.判断矩形是否在矩形内6.判断点是否在多边形内7.判断4个点(三维)是否共面8.凸包周长9.等周定理变形一直两端点和周长求最大面积10.平面最近点对11.单位圆最多覆盖多少点(包括边上)12.多边形费马点求点到多边形各个点的最短距离13.矩形并周长14.zoj 2500 求两球体积并一、图论1.最大团#include<iostream>#include<algorithm>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){for(int j=1;j<=n;j++) bestn[j]=vis[j];best=cn;return ;}int ok=1;for(int j=1;j<i;j++){if(vis[j]==1&&map[i][j]==0){ok=0;break;}}if(ok){//进入左子树vis[i]=1;cn++;dfs(i+1);cn--;}if(cn+n-i>best){//进入右子树vis[i]=0;dfs(i+1);}}int main(){while(scanf("%d%d",&n,&m)==2){memset(vis,0,sizeof(vis));memset(map,0,sizeof(map));while(m--){int p,q;scanf("%d%d",&p,&q);map[p][q]=map[q][p]=1;//无向图}cn=0;best=0;dfs(1);printf("%d\n",best);}return 0;}2.拓扑排序#include<iostream>#include<cstring>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) {flag=1; printf("%d",ans[1]);for(int i=2;i<=n;i++) printf(" %d",ans[i]);printf("\n");return ;}for(int i=1;i<=n;i++){if(vis[i]==0&&in[i]==0){vis[i]=1;for(int j=1;j<=n;j++){if(map[i][j]>0){map[i][j]=-map[i][j];in[j]--;}}ans[step]=i;dfs(step+1);vis[i]=0;for(int j=1;j<=n;j++){if(map[i][j]<0){map[i][j]=-map[i][j];in[j]++;}}}}}int main(){while(scanf("%d",&n)==1){flag=0;memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));for(int i=1;i<=n;i++){int t;while(scanf("%d",&t),t){map[i][t]=1;in[t]++;}}dfs(1);}return 0;}3．最短路和次短路#include<iostream>#include<cstdio>#include<vector>#include<cstring>using namespace std;class Node{public:int e,w;//表示终点和边权};const int inf=(1<<25);int main(){int ci;cin>>ci;while(ci--){vector<Node> G[1005];//用邻接表存边int n,m;cin>>n>>m;for(int i=1;i<=m;i++){Node q;int u;cin>>u>>q.e>>q.w;G[u].push_back(q);}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<G[u].size();l++){int d=dis[u][k]+G[u][l].w,j=G[u][l].e;//important//4种情况if(d<dis[j][0]){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]){dis[j][1]=d;cnt[j][1]=cnt[u][k];}else if(d==dis[j][1]){cnt[j][1]+=cnt[u][k];}}}int num=cnt[f][0];//最短路int cc=cnt[f][1];//次短路}return 0;}4．SAP模板#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int inf=(1<<31)-1;const int point_num=300;int cap[point_num][point_num],dist[point_num],gap[point_num];//初始化见main里面int s0,t0,n;//源,汇和点数int find_path(int p,int limit=0x3f3f3f3f){if(p==t0) return limit;for(int i=0;i<n;i++)if(dist[p]==dist[i]+1 && cap[p][i]>0){int t=find_path(i,min(cap[p][i],limit));if(t<0) return t;if(t>0){cap[p][i]-=t;cap[i][p]+=t;return t;}}int label=n;for(int i=0;i<n;i++) if(cap[p][i]>0) label=min(label,dist[i]+1);if(--gap[dist[p]]==0 || dist[s0]>=n ) return -1;++gap[dist[p]=label];return 0;}int sap(){//初始化s,ts0=0,t0=n-1;int t=0,maxflow=0;gap[0]=n;while((t=find_path(s0))>=0) maxflow+=t;return maxflow;}int main(){int ci;while(cin>>ci>>n){//初始化memset(cap,0,sizeof(cap));memset(dist,0,sizeof(dist));memset(gap,0,sizeof(gap));//初始化capwhile(ci--){int x,y,c;cin>>x>>y>>c;x--;y--;cap[x][y]+=c;//因题而异}int ans=sap();cout<<ans<<endl;}return 0;}5．已知各点度，问能否组成一个简单图#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int inf=(1<<30);int d[1100];bool cmp(int x,int y){return x>y;}int main(){int ci;scanf("%d",&ci);while(ci--){int n,flag=1,cnt=0;scanf("%d",&n); for(int i=0;i<n;i++){scanf("%d",&d[i]);if(d[i]>n-1||d[i]<=0) flag=0; cnt+=d[i];}if(flag==0||cnt%2){printf("no\n");continue;}sort(d,d+n,cmp);for(int l=n;l>0;l--){for(int i=1;i<l&&d[0];i++){d[0]--,d[i]--;if(d[i]<0){flag=0;break;}}if(d[0]) flag=0;if(flag==0) break;d[0]=-inf;sort(d,d+l,cmp);}if(flag) printf("yes\n");else printf("no\n");}return 0;}6.KRUSKAL#include<iostream>#include<algorithm>using namespace std;int u[15005],v[15005],w[15005],fath[15005],r[15005];int ans1[15005],ans2[15005];bool cmp(int i,int j){return w[i]<w[j];}int find(int x){return fath[x]==x?x:fath[x]=find(fath[x]);}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) fath[i]=i;for(int i=1;i<=m;i++) r[i]=i;for(int i=1;i<=m;i++){cin>>u[i]>>v[i]>>w[i];}sort(r+1,r+m+1,cmp);int maxn=0,ans=0,k=0;for(int i=1;i<=m;i++){int e=r[i];int x=find(u[e]),y=find(v[e]);if(x!=y){ans+=w[e];fath[x]=y;if(w[e]>maxn) maxn=w[e];ans1[k]=u[e];ans2[k++]=v[e];}}return 0;}7.prime求最小生成树语法：prim(Graph G,int vcount,int father[]);参数：G：图，用邻接矩阵表示vcount：表示图的顶点个数father[]：用来记录每个节点的父节点返回值：null注意：常数max_vertexes 为图最大节点数常数infinity为无穷大源程序：#define infinity 1000000#define max_vertexes 5typedef int Graph[max_vertexes][max_vertexes];void prim(Graph G,int vcount,int father[]){int i,j,k;intlowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes]; for (i=0;i<vcount;i++){lowcost[i]=G[0][i];closeset[i]=0;used[i]=0;father[i]=-1;}used[0]=1;for (i=1;i<vcount;i++){j=0;while (used[j]) j++;for (k=0;k<vcount;k++)if ((!used[k])&&(lowcost[k]<lowcost[j])) j=k;father[j]=closeset[j];used[j]=1;for (k=0;k<vcount;k++)if (!used[k]&&(G[j][k]<lowcost[k])){ lowcost[k]=G[j][k];closeset[k]=j; }}}8.Dijkstra语法：result=Dijkstra(Graph G,int n,int s,int t, int path[]); 参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径返回值：最短路径长度注意：输入的图的权必须非负顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Dijkstra(Graph G,int n,int s,int t, int path[]){int i,j,w,minc,d[max_vertexes],mark[max_vertexes];for (i=0;i<n;i++) mark[i]=0;for (i=0;i<n;i++){ d[i]=G[s][i];path[i]=s; }mark[s]=1;path[s]=0;d[s]=0;for (i=1;i<n;i++){minc=infinity;w=0;for (j=0;j<n;j++)if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}mark[w]=1;for (j=0;j<n;j++)if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j])){ d[j]=d[w]+G[w][j];path[j]=w; }}return d[t];}9.Bellman-ford语法：result=Bellman_ford(Graph G,int n,int s,int t,int path[],int success);参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径success：函数是否执行成功返回值：最短路径长度注意：输入的图的权可以为负，如果存在一个从源点可达的权为负的回路则success=0顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Bellman_ford(Graph G,int n,int s,int t,int path[],int success){int i,j,k,d[max_vertexes];for (i=0;i<n;i++) {d[i]=infinity;path[i]=0;}d[s]=0;for (k=1;k<n;k++)for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]){d[j]=d[i]+G[i][j];path[j]=i;}success=0;for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]) return 0;success=1;return d[t];}10. SPFA#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;const __int64 maxn=1001000;const __int64 inf=1000100000;struct edge//邻接表{__int64 t,w;//s->t=w;__int64 next;//数组模拟指针};__int64 p[maxn],pf[maxn];//邻接表头节点edge G[maxn],Gf[maxn];//邻接表__int64 V,E;//点数[1-n] 边数__int64 dis[maxn];__int64 que[maxn],fro,rear;//模拟队列__int64 vis[maxn];__int64 inque[maxn];//入队次数bool spfa(__int64 s0){fro=rear=0;for(__int64 i=1;i<=V;i++) dis[i]=inf;dis[s0]=0;memset(vis,0,sizeof(vis));memset(inque,0,sizeof(inque));que[rear++]=s0;vis[s0]=1;inque[s0]++;while(fro!=rear){__int64 u=que[fro];fro++;if(fro==maxn) fro=0;vis[u]=0;for(__int64 i=p[u];i!=-1;i=G[i].next){__int64 s=u,t=G[i].t,w=G[i].w;if(dis[t]>dis[s]+w){dis[t]=dis[s]+w;if(vis[t]==0){que[rear++]=t,vis[t]=1;inque[t]++;if(inque[t]>V) return false;if(rear==maxn) rear=0;}}}}return true;}int main(){__int64 ci;scanf("%I64d",&ci);while(ci--){scanf("%I64d%I64d",&V,&E);memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf)); for(__int64 i=0;i<E;i++){__int64 u,v,w;scanf("%I64d%I64d%I64d",&u,&v,&w);G[i].t=v;G[i].w=w;G[i].next=p[u];p[u]=i;Gf[i].t=u;Gf[i].w=w;Gf[i].next=pf[v];pf[v]=i;}__int64 ans=0;spfa(1);//求第一个点到其他点的最短距离和for(__int64 i=1;i<=V;i++) ans+=dis[i];//反方向再来一次spfa 求其他点到第一个点的最短距离和 for(__int64 i=1;i<=V;i++) p[i]=pf[i];for(__int64 i=0;i<E;i++) G[i]=Gf[i];spfa(1);for(__int64 i=1;i<=V;i++) ans+=dis[i];printf("%I64d\n",ans);}return 0;}11.Kosaraju模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;struct edge{int t,w;//u->t=w;int next;};int V,E;//点数(从1开始)，边数int p[maxn],pf[maxn];//邻接表原图,逆图edge G[maxn],Gf[maxn];//邻接表原图,逆图int l,lf;void init(){memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf));l=lf=0;}void addedge(int u,int t,int w,int l){G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}void addedgef(int u,int t,int w,int lf){Gf[l].w=w;Gf[l].t=t;Gf[l].next=pf[u];pf[u]=l;}///Kosaraju算法,返回为强连通分量个数bool flag[maxn]; //访问标志数组int belg[maxn]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量int numb[maxn]; //结束时间(出栈顺序)标记,其中numb[i]表示离开时间为i的顶点//用于第一次深搜,求得numb[1..n]的值void VisitOne(int cur, int &sig){flag[cur] = true;for (int i=p[cur];i!=-1;i=G[i].next){if (!flag[G[i].t]){VisitOne(G[i].t,sig);}}numb[++sig] = cur;}//用于第二次深搜,求得belg[1..n]的值void VisitTwo(int cur, int sig){flag[cur] = true;belg[cur] = sig;for (int i=pf[cur];i!=-1;i=Gf[i].next){if (!flag[Gf[i].t]){VisitTwo(Gf[i].t,sig);}}//Kosaraju算法,返回为强连通分量个数int Kosaraju_StronglyConnectedComponent(){int i, sig;//第一次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=1; i<=V; ++i ){if ( false==flag[i] ){VisitOne(i,sig);}}//第二次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=V; i>0; --i ){if ( false==flag[numb[i]] ){VisitTwo(numb[i],++sig);}}return sig;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int u=i,t,w=1;while(scanf("%d",&t)==1&&t){E++;addedge(u,t,w,l++);addedgef(t,u,w,lf++);}}int ans=Kosaraju_StronglyConnectedComponent(); printf("%d\n",ans);}return 0;12.tarjan模板//自己模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int belg[maxn];//第i个节点属于belg[i]个强连通分量int stck[maxn],stop;//stck栈int instck[maxn];//第i个节点是否在栈中int scnt;//强联通分量int index;void dfs(int i){dfn[i]=lowc[i]=++index;instck[i]=1;//节点i入栈stck[++stop]=i;for(int j=p[i];j!=-1;j=G[j].next){int t=G[j].t;//更新lowc数组if(!dfn[t])//t没有遍历过{dfs(t);if(lowc[i]>lowc[t]) lowc[i]=lowc[t];}//t是i的祖先节点else if(instck[t]&&lowc[i]>dfn[t]) lowc[i]=dfn[t];}//是强连通分量的根节点if(dfn[i]==lowc[i]){scnt++;int t;do{t=stck[stop--];instck[t]=0;belg[t]=scnt;}while(t!=i);}}int tarjan(){stop=scnt=index=0;memset(dfn,0,sizeof(dfn));memset(instck,0,sizeof(instck));for(int i=1;i<=V;i++){if(!dfn[i]) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}//吉大模板邻接表版#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int stck[maxn],stop;//stck栈int pre[maxn];//int scnt;//强联通分量int cnt;//void dfs(int v)//1-V{int t,minc=lowc[v]=pre[v]=cnt++;stck[stop++]=v;for(int i=p[v];i!=-1;i=G[i].next){int pv=G[i].t;if(pre[pv]==-1) dfs(pv);if(lowc[pv]<minc) minc=lowc[pv]; }if(minc<lowc[v]){lowc[v]=minc;return ;}do{dfn[t=stck[--stop]]=scnt;lowc[t]=V;}while(t!=v);++scnt;}int tarjan(){stop=cnt=scnt=0;memset(pre,-1,sizeof(pre));for(int i=1;i<=V;i++){if(pre[i]==-1) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}二、数学1．剩余定理int mod(int c[],int b[],int n){int all_multy=1,sum=0;int i,j,x[5];for(i=0;i<n;i++)all_multy*=c[i];for(i=0;i<n;i++)x[i]=all_multy/c[i];for(i=0;i<n;i++){j=1;while((x[i]*j)%c[i]!=1)j++;x[i]*=j;}for(i=0;i<n;i++)sum+=(b[i]*x[i]);return sum%all_multy;}2．N!中质因子P的个数//对于任意质数p，n！中有（n/p+n/p^2+n/p^3+...)个质因子p。

常用算法设计方法要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。

计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。

算法数据结构是程序的两个重要方面。

算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。

指令正确地描述了要完成的任务和它们被执行的顺序。

计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。

通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。

其次是算法所需要的存储空间少和执行更快等。

算法设计是一件非常困难的工作，常用的算法设计方法主要有迭代法、穷举搜索法、递推法、递归法、贪婪法、回溯法、分治法、动态规划法等。

一、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。

设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：（1）选一个方程的近似根，赋给变量x0；（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；（3）当x0与x1的差的绝对值还大于指定的精度要求时，重复步骤（2）的计算。

若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。

上述算法用C程序的形式表示为：【算法】迭代法求方程的根{ x0=初始近似根；do {x1=x0；x0=g(x1)； /*按特定的方程计算新的近似根*/} while ( fabs(x0-x1)>Epsilon)；prin tf(“方程的近似根是%f\n”，x0)；}具体使用迭代法求根时应注意以下两种可能发生的情况：（1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；（2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。

ACM大数分解质因数1. 引言在算法竞赛中，ACM（ACM ICPC）是一项广受欢迎的比赛形式。

其中，大数分解质因数是一个常见的题目类型。

本文将介绍大数分解质因数的基本概念、常见解法以及一些优化技巧，帮助读者更好地理解和解决相关问题。

2. 基本概念2.1 质数质数（prime number）指的是只能被1和自身整除的正整数。

例如，2、3、5、7等都是质数，而4、6、8等都不是质数。

2.2 质因数质因数（prime factor）指的是一个数的所有质数因子。

例如，24的质因数为2、2、2、3，可以记作2^3 * 3。

2.3 大数在ACM竞赛中，我们常常需要处理超出普通整数范围的大数。

大数通常用字符串或数组来表示，可以进行各种数值运算。

3. 常见解法3.1 枚举法枚举法是最简单直接的解法，其基本思想是从2开始逐个判断是否为质因数。

具体步骤如下：1.将待分解的大数存储为num。

2.从2开始，依次判断每个数i是否为num的质因数。

3.若i是num的质因数，则将i存储为结果，并将num除以i，继续判断num是否还有其他质因数。

4.若num无法再被除尽，说明已经找到了所有质因数，结束循环。

枚举法的时间复杂度较高，但对于小规模的输入仍然是可行的。

3.2 分解法分解法是一种改进的解法，其基本思想是先找到一个质因数，然后将该质因数除尽后，再继续寻找下一个质因数。

具体步骤如下：1.将待分解的大数存储为num。

2.从2开始，依次判断每个数i是否为num的质因数。

3.若i是num的质因数，则将i存储为结果，并将num除以i，继续判断num是否还有其他质因数。

4.若num无法再被除尽，说明已经找到了所有质因数，结束循环。

分解法相较于枚举法，减少了不必要的判断，能够更快地找到质因数。

3.3 分解法优化分解法在寻找质因数时，可以优化判断的上界。

具体优化如下：1.将待分解的大数存储为num。

2.从2开始，依次判断每个数i是否为num的质因数。

ACM常见算法ACM算法⼀、数论算法 1．求两数的最⼤公约数 2．求两数的最⼩公倍数 3．素数的求法 A.⼩范围内判断⼀个数是否为质数： B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：⼆、图论算法1．最⼩⽣成树A.Prim算法：B.Kruskal算法：(贪⼼) 按权值递增顺序删去图中的边，若不形成回路则将此边加⼊最⼩⽣成树。

2.最短路径 A.标号法求解单源点最短路径： B.Floyed算法求解所有顶点对之间的最短路径： C. Dijkstra 算法：3.计算图的传递闭包4．⽆向图的连通分量 A.深度优先 B 宽度优先（种⼦染⾊法）5．关键路径⼏个定义：顶点1为源点，n为汇点。

a. 顶点事件最早发⽣时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0; b. 顶点事件最晚发⽣时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n); c. 边活动最早开始时间 Ee[I], 若边I由<j,k>表⽰，则Ee[I] = Ve[j]; d. 边活动最晚开始时间 El[I], 若边I由<j,k>表⽰，则El[I] = Vl[k] – w[j,k]; 若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。

求解⽅法： a. 从源点起topsort,判断是否有回路并计算Ve; b. 从汇点起topsort,求Vl; c. 算Ee 和 El;6．拓扑排序找⼊度为0的点，删去与其相连的所有边，不断重复这⼀过程。

例寻找⼀数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO.7.回路问题 Euler回路(DFS) 定义：经过图的每条边仅⼀次的回路。

（充要条件：图连同且⽆奇点） Hamilton回路定义：经过图的每个顶点仅⼀次的回路。

acm数论知识点总结1. 整除与余数整除是数论中最基本的概念之一。

如果一个整数a可以被另一个整数b整除，那么我们说b是a的一个因子，记作b|a。

如果a不能被b整除，记作b∣a。

另外，如果a除以b得到的商为q，余数为r，那么我们有a=bq+r，并且0≤r<|b|。

这里的余数r可以用来求解问题，比如判断一个数是奇数还是偶数；或者用来求解同余方程。

2. 最大公约数和最小公倍数两个整数a和b的最大公约数（Greatest Common Divisor，GCD）是能够整除a和b的最大的整数。

通常记作gcd(a, b)。

最小公倍数（Least Common Multiple，LCM）是能够被a和b整除的最小的整数。

通常记作lcm(a, b)。

最大公约数和最小公倍数可以用辗转相除法快速求解，而且它们有一些常见的性质，比如gcd(a, b)⋅lcm(a, b)=a⋅b。

3. 素数素数是指只能被1和自身整除的正整数。

素数在数论中是非常重要的，它们有许多特殊的性质。

比如任意一个整数都可以分解成若干个素数的乘积。

素数在ACM竞赛中常用于判断数字的性质，或者用于设计算法。

4. 同余同余是数论中一个重要的概念，如果两个整数a和b除以一个正整数m得到的余数相同，那么我们就说a同余b模m，记作a≡b(mod m)。

同余关系具有传递性和对称性，满足一些特殊的性质。

同余关系可以用来求解很多问题，比如求解同余方程、构造递归关系等。

5. 奇数和偶数奇数是最基本的整数，它们可以被2整除；偶数是能够被2整除的整数。

奇数和偶数在一些问题中有特殊的性质，比如奇数乘以奇数得到的是奇数，奇数加偶数得到的是奇数等。

6. 欧拉定理欧拉定理是数论中一个著名的定理，它为解决同余方程提供了一个重要的工具。

欧拉定理表明，如果正整数a和m互质（即gcd(a, m)=1），那么a的欧拉函数值为φ(m)，则a^φ(m)≡1(mod m)。

欧拉定理在RSA密码算法中有重要应用。

数学 (4)最大公约数、最小公倍数 (4)最大公约数——欧几里得算法O(n) (4)Stein算法O( log(max(a,b)) ) (4)最小公倍数： (4)素数相关 (5)普通素数判断 (5)筛法求素数[1，N] (5)二次筛法求素数[L，R] (6)Miller-Rabbin素数测试方法 (7)算术基本定理的定义和性质： (8)同余方程[组] 乘法模逆元中国剩余定理 (9)扩展欧几里得，求一组解x，y，使得gcd(a,b) = d = a * x + b * y (9)扩展欧几里得，求所有解x，y，使得c = a * x + b * y (10)扩展欧几里得，求a关于n的逆元a^-1，使得a * a^-1 ≡ 1(mod n) (10)扩展欧几里得，求解x，满足同余方程组x ≡ Ri(mod Ai) (10)扩展欧几里得，求解x，满足高次同余方程A^x ≡ B(mod C) (11)中国剩余定理： (13)中国剩余定理最小非负数解的算法： (14)求解a*x + b*y = c的其中一组解，使得|x| + |y|尽可能小，若相等，则a|x| + b|y|尽可能小。

(15)整数快速幂 (16)矩阵快速幂 (16)整数分解 (18)试除法整数分解 (18)筛法整数分解 (18)PollardRho大整数分解 (19)欧拉函数 (22)直接欧拉函数 (22)递推快速求欧拉函数 (23)容斥原理 (23)母函数 (24)普通母函数 (24)指数型母函数 (25)其他相关 (27)九余数定理：一个数N各位数字的和，对9取余等于这个数对9取余 (27)给你一个奇数N，求1~N的奇数平方和： S = N*(N+1)*(N+2)/6 (27)约瑟夫问题：有N个人，编号为1~N，按顺时针围成一个圈，每数k个人，就将这个人从圈中消除，问：最终只留下一个人的编号。

(27)给你整数x和y的和以及x和y的积，是否能找到满足这两个式子的整数x和整数y。

ACM信息汇总⼀、ACM算法总结及刷题参考（摘⾃：）初期:⼀.基本算法:(1)枚举. (poj1753,poj2965)(2)贪⼼(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)⼆.图算法:(1)图的深度优先遍历和⼴度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最⼩⽣成树算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4)拓扑排序 (poj1094)(5)⼆分图的最⼤匹配 (匈⽛利算法) (poj3041,poj3020)(6)最⼤流的增⼴路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串 (poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应⽤.(4)哈希表和⼆分查找等⾼效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)(2)⼴度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书 page149):1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共⼦序列)(poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优⼆分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算⽅法.1.⼆分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算⼏何学.(1)⼏何公式.(2)叉积和点积的运⽤(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求⾯积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包. (poj2187,poj1113)中级:⼀.基本算法:(1)C++的标准模版库的应⽤. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)⼆.图算法:(1)差分约束系统的建⽴和求解. (poj1201,poj2983)(2)最⼩费⽤最⼤流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分⽀及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最⼩割模型、⽹络流规约(poj3308, )三.数据结构:(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态⼆叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的⾼级应⽤. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可⾏性剪枝(2)搜索的技巧和优化 (poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施⾏商问题等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.⾼斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧⼏⾥德(中国剩余定理) (poj3101)(3)计算⽅法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单⾕)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题.(poj1870,poj3296,poj3286,poj1095)七.计算⼏何学:(1)坐标离散化.(2)扫描线算法(例如求矩形的⾯积和周长并,常和线段树或堆⼀起使⽤).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平⾯交)(poj3130,poj3335)(4)⼏何⼯具的综合应⽤.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)⾼级:⼀.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和⾼效性. poj3434⼆.图算法:(1)度限制最⼩⽣成树和第K最短路. (poj1639)(2)最短路,最⼩⽣成树,⼆分图,最⼤流问题的相关理论(主要是模型建⽴和求解)(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446(3)最优⽐率⽣成树. (poj2728)(4)最⼩树形图(poj3164)(5)次⼩⽣成树.(6)⽆向图、有向图的最⼩环三.数据结构.(1)trie图的建⽴和应⽤. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应⽤(维护⼀个单调的队列,常常在动态规划中起到优化状态转移的⽬的). (poj2823)(4)左偏树(可合并堆).(5)后缀树(⾮常有⽤的数据结构,也是赛区考题的热点).(poj3415,poj3294)四.搜索(1)较⿇烦的搜索题⽬训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)⼴搜的状态优化:利⽤M进制数存储状态、转化为串⽤hash表判重、按位压缩存储状态、双向⼴搜、A*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量⽤位运算、⼀定要加剪枝、函数参数尽可能少、层数不易过⼤、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)五.动态规划(1)需要⽤数据结构优化的动态规划.(poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极⼤极⼩过程(poj3317,poj1085)2.Nim问题.七.计算⼏何学.(1)半平⾯求交(poj3384,poj2540)(2)可视图的建⽴(poj2966)(3)点集最⼩圆覆盖.(4)对踵点(poj2079)⼋.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)补充：Dp状态设计与⽅程总结1.不完全状态记录<1>青蛙过河问题<2>利⽤区间dp2.背包类问题<1> 0-1背包，经典问题<2>⽆限背包，经典问题<3>判定性背包问题<4>带附属关系的背包问题<5> + -1背包问题<6>双背包求最优值<7>构造三⾓形问题<8>带上下界限制的背包问题(012背包)3.线性的动态规划问题<1>积⽊游戏问题<2>决⽃（判定性问题）<3>圆的最⼤多边形问题<4>统计单词个数问题<5>棋盘分割<6>⽇程安排问题<7>最⼩逼近问题(求出两数之⽐最接近某数/两数之和等于某数等等)<8>⽅块消除游戏(某区间可以连续消去求最⼤效益)<9>资源分配问题<10>数字三⾓形问题<11>漂亮的打印<12>邮局问题与构造答案<13>最⾼积⽊问题<14>两段连续和最⼤<15>2次幂和问题<16>N个数的最⼤M段⼦段和<17>交叉最⼤数问题4.判定性问题的dp(如判定整除、判定可达性等)<1>模K问题的dp<2>特殊的模K问题，求最⼤(最⼩)模K的数<3>变换数问题5.单调性优化的动态规划<1>1-SUM问题<2>2-SUM问题<3>序列划分问题(单调队列优化)6.剖分问题(多边形剖分/⽯⼦合并/圆的剖分/乘积最⼤)<1>凸多边形的三⾓剖分问题<2>乘积最⼤问题<3>多边形游戏(多边形边上是操作符,顶点有权值)<4>⽯⼦合并(N^3/N^2/NLogN各种优化)7.贪⼼的动态规划<1>最优装载问题<2>部分背包问题<3>乘船问题<4>贪⼼策略<5>双机调度问题Johnson算法8.状态dp<1>⽜仔射击问题(博弈类)<2>哈密顿路径的状态dp<3>两⽀点天平平衡问题<4>⼀个有向图的最接近⼆部图9.树型dp<1>完美服务器问题(每个节点有3种状态)<2>⼩胖守皇宫问题<3>⽹络收费问题<4>树中漫游问题<5>树上的博弈<6>树的最⼤独⽴集问题<7>树的最⼤平衡值问题<8>构造树的最⼩环⼆、ACM⼤赛准备（经验1）（摘⾃：）ACM常⽤算法及练习第⼀阶段：练经典常⽤算法，下⾯的每个算法给我打上⼗到⼆⼗遍，同时⾃⼰精简代码，因为太常⽤，所以要练到写时不⽤想，10-15分钟内打完，甚⾄关掉显⽰器都可以把程序打出来.1.最短路(Floyd、Dijstra,BellmanFord)2.(先写个prim,kruscal要⽤并查集，不好写)3.⼤数（⾼精度）加减乘除4.⼆分查找. (代码可在五⾏以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练(要熟，要灵活,代码要简)7.数学上的有：辗转相除（两⾏内），线段交点、多⾓形⾯积公式.8. 调⽤系统的qsort, 技巧很多，慢慢掌握.9. 任意进制间的转换第⼆阶段：练习复杂⼀点，但也较常⽤的算法。

ACM典型试题--简单的加密算法（⼀）1. 题⽬描述简单的加密算法：把字符串中的字符替换成另外的字符，只有对⽅知道如何替换就可以解密。

要求根据给定的加密⽅法和密⽂，得到原始消息。

输⼊格式第⼀⾏输⼊密钥，第⼆⾏输⼊密⽂。

输出格式对输⼊的数据输出解密后的原始信息。

输⼊样例eydbkmiqugjxlvtzpnwohracsfKifq oua zarxa suar bti yaagrj fa xtfgrj输出样例Jump the fence when you seeing me coming2. 题⽬分析和算法实现第⼀⾏的“eydbkmiqugjxlvtzpnwohracsf”相当于密钥，含义是a 对应e、b 对应y、c 对应d…。

因此，只要把密⽂序列中的相应字符替换为对应后⾯的字符即可。

即对于“Kifq oua zarxa suar bti yaagrj fa xtfgrj”，把K 替换成J，把i 替换成u，把f 替换成m，…。

但要注意⼤⼩写。

编程的时候，可以定义数组表⽰密钥。

然后对密⽂进⾏遍历得到原始信息。

3. 问题实现及代码分析#include <stdio.h>int main( void ){char codeKey[128],codeWord[100],Decode[100];printf("\n输⼊密钥26个字母:");for (int i='a';i<='z';i++){scanf("%c",&codeKey[i]);codeKey[i-32]=codeKey[i]-32;}codeKey[127]='\0';printf("\n输⼊密钥为：");for (int i='a';i<='z';i++){printf("%c",codeKey[i]);}printf("\n输⼊密⽂:");getchar();gets(codeWord);int j=0;while(codeWord[j]!='\0'){if (codeWord[j]==' '){Decode[j]=codeWord[j];}else{Decode[j]=codeKey[codeWord[j]];}++j;}Decode[j]='\0';printf("\n解密为：");puts(Decode);}4.结果。

16个ACM经典算法介绍一、排序算法：1.冒泡排序：基于比较的排序算法，通过不断交换相邻元素将最大元素逐渐向后移动。

2.插入排序：基于比较的排序算法，通过将元素逐个插入到已排好序的部分中，最终得到完全有序的序列。

3.归并排序：基于分治的排序算法，将待排序序列划分为一系列子序列，然后将子序列进行合并，最终得到完全有序的序列。

4.快速排序：基于分治的排序算法，通过选择一个基准元素将序列划分为两部分，然后递归地对两部分进行排序。

5.堆排序：基于堆的排序算法，通过构建最大堆或最小堆来实现排序。

二、查找算法：6.二分查找：基于有序序列的查找算法，通过将待查找值与序列中间元素进行比较，逐渐缩小查找范围。

7.哈希表：基于哈希函数的查找算法，通过将键值对存储在哈希表中，实现高效的查找。

三、图算法：8.深度优先（DFS）：基于栈的算法，通过递归地访问顶点的邻接顶点，实现图的遍历。

9.广度优先（BFS）：基于队列的算法，通过访问顶点的邻接顶点，实现图的遍历。

10. 最小生成树算法：用来求解无向图的最小生成树，常用的有Prim算法和Kruskal算法。

11. 最短路径算法：用来求解有向图或带权重的无向图的最短路径，常用的有Dijkstra算法和Floyd-Warshall算法。

四、动态规划算法：12.最长上升子序列（LIS）：用来求解一个序列中最长严格递增子序列的长度。

13.背包问题：用来求解在给定容量下，能够装入尽量多的物品的问题。

五、字符串算法：14.KMP算法：用来在一个文本串S中查找一个模式串P的出现位置的算法，通过预处理模式串，利用已经匹配过的子串，跳过一定长度进行下一轮匹配。

15. Boyer-Moore算法：用来在一个文本串S中查找一个模式串P的出现位置的算法，通过从模式串末尾开始匹配，利用好后缀和坏字符规则，跳过一定长度进行下一轮匹配。

16.字符串匹配算法：用来在一个文本串S中查找多个模式串的出现位置的算法，常用的有AC自动机和后缀树。

ACM 题型算法分类题目均来自主流算法搜索//回溯DP（动态规划）贪心图论//Dijkstra、最小生成树、网络流数论//解模线性方程计算几何//凸壳、同等安置矩形的并的面积与周长组合数学//Polya定理模拟数据结构//并查集、堆10.博弈论1、排序1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379,1002（需要字符处理，排序用快排即可）1007（稳定的排序）2159（题意较难懂）2231 2371（简单排序）2388（顺序统计算法）2418（二叉排序树）2、搜索、回溯、遍历1022 1111d 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078,2083,2303,2310,2329简单1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742,1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426,不易1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197,2349,推荐1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709,1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170,2288, 2331, 2339, 2340,1979（和迷宫类似）1980（对剪枝要求较高）3、历法1008 2080 （这种题要小心）4、枚举1012，1046，1387，1411，2245，2326，2363，2381，1054（剪枝要求较高），1650 （小数的精度问题）5、数据结构的典型算法容易1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395,不易1145, 1177, 1195, 1227, 1661, 1834,推荐1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010,2119, 2274, 1125(弗洛伊德算法) ，2421（图的最小生成树）6、动态规划1037 A decorative fence、1050 To the Max、1088 滑雪、1125 Stockpoker Grapevine、1141 Brackets Sequence、1159 Palindrome、1160 Post Office、1163 The Triangle、1458 Common Subsequence、1579 Function Run Fun、1887 Testing the CATCHER、1953 World Cup Noise、2386 Lake Counting7、贪心1042, 1065, 1230, 1323, 1477, 1716, 1784,1328 1755（或用单纯形方法），2054，1017，1328，1862，1922 ，2054，2209，2313，2325，2370。

不同因子个数 acm
ACM（美国计算机协会）在不同因子个数方面可能涉及到数论和
算法方面的知识。

首先，我们来讨论一下因子的概念。

在数论中，
一个数的因子是能够整除该数的整数。

比如，数 6 的因子包括 1、2、3 和 6。

不同因子个数指的是一个数有多少个不同的因子。

首先，我们可以讨论如何计算一个数的因子个数。

一个简单的
方法是通过数的质因数分解来确定因子的个数。

如果一个数可以表
示为质数的乘积，那么它的因子个数可以通过指数加 1 的乘积来计算。

举个例子，假设一个数的质因数分解为 p1^a1 p2^a2 p3^a3，那么它的因子个数就是 (a1+1) (a2+1) (a3+1)。

这个方法可以用
来高效地计算因子个数。

另外，我们还可以讨论如何在算法竞赛中解决与因子个数相关
的问题。

有一类经典的问题叫做“高度合数数”问题，要求找出第
n 个因子个数大于某个阈值的数。

解决这类问题通常需要使用一些
数论知识，比如筛法求质数、因子个数函数等。

算法竞赛中对于因
子个数的计算也有一些经典的优化技巧，比如欧拉筛、莫比乌斯反
演等。

此外，还有一些与因子个数相关的数论定理，比如莫比乌斯反演、约数和公约数的关系等。

这些定理可以帮助我们更深入地理解
因子个数的性质和计算方法。

总的来说，不同因子个数涉及到数论和算法方面的知识，涵盖
了因子个数的计算方法、与算法竞赛相关的问题以及一些数论定理。

希望这些信息能够帮助你更全面地理解这个问题。