acm试题集(免下载卷)

《acm试题集(免下载卷)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM经典试题ACM经典试题ACM经典试题ACM经典试题ACM经典试题ACM经典试题124目录一．数论41.阶乘最后非零位42.模线性方程(组)43.素数表64.素数随机判定(miller_rabin)65.质因数分解76.最大公约数欧拉函数8二．图论_匹配91.二分图最大匹配(hungary邻接表形式)92.二分图最大匹配(hungary邻接表形式,邻接阵接口)103.二分图最大匹配(hungary邻接阵形式)104.二分图最大匹配(hungary正向表形式)115.二分图最佳匹配(kuhn_munkras邻接阵形式

2、)116.一般图匹配(邻接表形式)127.一般图匹配(邻接表形式,邻接阵接口)138.一般图匹配(邻接阵形式)149.一般图匹配(正向表形式)15三．图论_生成树161.最小生成树(kruskal邻接表形式)162.最小生成树(kruskal正向表形式)173.最小生成树(prim+binary_heap邻接表形式)194.最小生成树(prim+binary_heap正向表形式)205.最小生成树(prim+mapped_heap邻接表形式)216.最小生成树(prim+mapped_heap正向表形式)227.最小生

3、成树(prim邻接阵形式)238.最小树形图(邻接阵形式)24四．图论_网络流251.上下界最大流(邻接表形式)252.上下界最大流(邻接阵形式)263.上下界最小流(邻接表形式)274.上下界最小流(邻接阵形式)295.最大流(邻接表形式)306.最大流(邻接表形式,邻接阵接口)317.最大流(邻接阵形式)328.最大流无流量(邻接阵形式)329.最小费用最大流(邻接阵形式)33五.图论_最短路径341.最短路径(单源bellman_ford邻接阵形式)342.最短路径(单源dijkstra_bfs邻接表形式)353

4、.最短路径(单源dijkstra_bfs正向表形式)354.最短路径(单源dijkstra+binary_heap邻接表形式)365.最短路径(单源dijkstra+binary_heap正向表形式)371246.最短路径(单源dijkstra+mapped_heap邻接表形式)387.最短路径(单源dijkstra+mapped_heap正向表形式)398.最短路径(单源dijkstra邻接阵形式)409.最短路径(多源floyd_warshall邻接阵形式)40六.图论_连通性411.无向图关键边(dfs邻接阵形式

5、)412.无向图关键点(dfs邻接阵形式)423.无向图块(bfs邻接阵形式)434.无向图连通分支(bfs邻接阵形式)435.无向图连通分支(dfs邻接阵形式)446.有向图强连通分支(bfs邻接阵形式)447.有向图强连通分支(dfs邻接阵形式)458.有向图最小点基(邻接阵形式)46七.图论_应用461.欧拉回路(邻接阵形式)462.前序表转化473.树的优化算法484.拓扑排序(邻接阵形式).495.最佳边割集506.最佳顶点割集517.最小边割集528.最小顶点割集539.最小路径覆盖55八.图论_NP搜索5

6、51.最大团(n小于64)(faster)552.最大团58九.组合591.排列组合生成592.生成gray码603.置换(polya)614.字典序全排列615.字典序组合626.组合公式62十.数值计算631.定积分计算(Romberg)632.多项式求根(牛顿法)643.周期性方程(追赶法)66十一.几何671.多边形672.多边形切割703.浮点函数714.几何公式765.面积786.球面791247.三角形798.三维几何819.凸包(graham)8910.网格(pick)9111.圆9212.整数函数94

7、13.注意96十二.结构971.并查集972.并查集扩展(friend_enemy)983.堆(binary)984.堆(mapped)995.矩形切割996.线段树1007.线段树扩展1028.线段树应用1059.子段和10510.子阵和105十三.其他1061.分数1062.矩阵1083.日期1104.线性方程组(gauss)1115.线性相关113十四.应用1141.joseph1142.N皇后构造解1153.布尔母函数1154.第k元素1165.幻方构造1166.模式匹配(kmp)1187.逆序对数1188.字

8、符串最小表示1199.最长公共单调子序列11910.最长子序列12011.最大子串匹配12112.最大子段和12213.最大子阵和123一．数论1.阶乘最后非零位124//求阶乘最后非零位,复杂度O(nlogn)//返回该位,n以字符串方式传入#include#defineMAXN10000intlastdig