下载文档原格式
ACM/ICPC竞赛中用到的大量算法，包括：组合数学、数论、图论、计算几何、高级数据结构等。
北京大学
课程内容共八个专题，除理论知识外还包括精选例题讲解：
7.14 数据结构（一）: 线段树，树状数组，二维线段树
7.15 数学题：组合数学，数论等
7.16 数据结构（二）: 并查集, DFA, Trie图等
7.17 若干图论问题：最小生成树最短路强连通分量、桥和割点等
7.21 计算几何：线与线求交，线与面求交，求凸包，半平面求交等
7.22 搜索：深搜，广搜，剪枝，A*算法
7.24 动态规划
7.24 网络流算法：基本的网络流算法，Dinic算法，带上下界的网络流，最小费用
流。
acm-icpc暑期课_最短路北京⼤学暑期课《ACM/ICPC 竞赛训练》最短路算法本讲义为四处抄袭后改编⽽成，来源已不可考。
仅⽤于内部授课北京⼤学信息学院郭炜 guo_wei@/doc/d83c4f84bb68a98270fefa4a.html/doc/d83c4f84bb68a98270fefa4a.html /guoweiofpkuDijkstra 算法●解决⽆负权边的带权有向图或⽆向图的单源最短路问题●贪⼼思想，若离源点s 前k-1近的点已经被确定，构成点集P ，那么从s 到离s 第k 近的点t 的最短路径，{s,p 1,p 2…p i ,t}满⾜s,p 1,p 2…p i ∈P 。
●否则假设pi ?P ，则因为边权⾮负，pi 到t 的路径≥0，则d[pi]≤d[t],pi 才是第k 近。
将pi 看作t ，重复上⾯过程，最终⼀定会有找不到pi 的情况●d[i]=min(d[p i ]+cost(p i ,i)),i ?P,p i ∈P d[t]=min(d[i]) ,i ?P基本思想●初始令d[s]=0，d[i]=+∞，P=?●找到点i?P，且d[i]最⼩●把i添⼊P，对于任意j?P，若d[i]+cost(i,j)d[j]=d[i]+cost(i,j)。
●⽤邻接表，不优化，时间复杂度O(V2+E)●Dijkstra+堆的时间复杂度 o(ElgV)●⽤斐波那契堆可以做到O(VlogV+E)●若要输出路径，则设置prev数组记录每个节点的前趋点，在d[i]更新时更新prev[i]4 23 150200200 100080005000v Dist[v]0 01234 50100001000300025025082505250源点0加⼊P后：Dijkstra's AlgorithmDijkstra 算法也适⽤于⽆向图。
但不适⽤于有负权边的图。
231-234d[1,2] = 2但⽤Dijkstra 算法求得 d[1,2] = 3有N个孩⼦（N<=3000)分糖果。
北京大学暑期课《ACM/ICPC竞赛训练》北京大学信息学院郭炜guo_wei@/guoweiofpku课程网页：/summerschool/pku_acm_train.htm信息科学技术学院《程序设计与算法》ACM/ICPC中的数学郭炜/林舒( a + b ) mod c =((a mod c) + (b mod c)) mod c( a * b ) mod c =((a mod c) * (b mod c)) mod c消去律：若 gcd(c,p) = 1,则ac ≡ bc mod p => a ≡ b mod p消去律证明：ac ≡ bc mod p => ac = bc + kp => c(a-b) = kpc和p没有除1以外的公因子 =>1) c能整除k 或 2) a = b如果2不成立，则c|kpc和p没有公因子 => c|k，所以k = ck'=> c(a-b)=kp可以表示为c(a-b) =ck'p因此a-b = k'p，得出a ≡ b mod pint Pow(int a,int b){ //快速求a^b ，复杂度 log(b)if(b == 0)return 1;if(b & 1) { //b是奇数return a * Pow(a,b-1);}else {int t = Pow(a,b/2);return t * t;}}int Pow(int a,int b){ //快速求a^b ，复杂度 log(b) int result = 1;int base = a;while(b) {if( b & 1)result *= base;base *= base;b >>= 1;}return result;}快速幂取模int PowMod(int a,int b,int c){//快速求 a^b % c ，要避免计算中间结果溢出int result = 1;int base = a%c;while(b) {if( b & 1)result = (result * base)%c;base = (base * base) % c;b >>= 1;}return result;}Sn= a+a2+...+a n要求 Snmod p如果用公式算，可能溢出，因此用二分法求1) 若 n是偶数Sn= a+...+a n/2 + a n/2+1 + a n/2+2 +...+ a n/2+n/2 =(a+...+a n/2) + a n/2(a+...+a n/2)=Sn/2+ a n/2Sn/2=(1+a n/2)Sn/22) 若n是奇数= a+...+a(n-1)/2 + a(n-1)/2+1 +...Sn+ a(n-1)/2+(n-1)/2 + a(n-1)/2+(n-1)/2 + 1 =S+ a(n-1)/2(a+...+a(n-1)/2)+a n (n-1)/2+a n=(1+a(n-1)/2)S(n-1)/2等比数列二分求和取模int PowSumMod(int a,int n,int p){// return (a+ a^2 + ... + a^n) Mod p;if( n == 1)return a%p;if( n %2 == 0)return (1+PowMod(a,n/2,p))*PowSumMod(a,n/2,p) % p;elsereturn ((1+PowMod(a,(n-1)/2,p)) * PowSumMod(a,(n-1)/2,p) + PowMod(a,n,p)) % p;}POJ3233 Matrix Power Series矩阵快速幂+等比数列二分求和取模给一个n×n的整数矩阵A和正整数k,m, 令S = A + A2 + A3+ … +A k求 S mod m (S的每个都 mod m)n (n≤ 30),k (k≤ 109) and m (m < 104).struct Matrix{T a[32][32];int r; //行列数Mat(int rr):r(rr) { }void MakeI() { //变为单位矩阵memset(a,0,sizeof(a));for(int i = 0;i < r; ++i)a[i][i] = 1;}};Matrix Pow(const Matrix & m,int k,int p){ //求m k mod pint r = m.r;Matrix result(r);result.MakeI(); //MakeI是将result变为单位矩阵Matrix base = m;while(k) {if( k & 1)result = Product(result,base,p); //result*base mod pk >>= 1;base = Product(base,base,p);}return result;} 14欧几里得算法求最大公约数int Gcd(int a,int b){if( b == 0)return a;return Gcd(b,a%b);}最小公倍数：lcm(a,b) = a*b/gcd(a,b)ax+by=gcd(a,b) 有整数解(x,y)<=>bx+(a%b)y = gcd(a,b) 有整数解(x1,y1)，且x = y1, y = x1-[a/b]*y1因此，可以在求gcd(a,b)的同时，对 ax+by=gcd(a,b)求解int GcdEx(int a,int b,int &x ,int & y) //求 ax+by=gcd(a,b)的整数解,返回gcd(a,b) {if( b == 0) {x = 1;y = 0;return a;}int x1,y1;int gcd = GcdEx(b,a%b,x1,y1);x = y1;y = x1 - a/b * y1;return gcd;}• ax+by=c 有解的充要条件是 gcd(a,b)|c•设 d = gcd(a,b), k = c/d，ax+by = d的解是 (x1,y1) 则ax+by = c的解集是：x = k*x1 + t*(b/d)y = k*y1 – t*(a/d) t为任意整数18•求ax≡c(mod b)等价于求 ax+by = c •设 d = gcd(a,b), k = c/d，ax+by = d的解是 (x1,y1) 则•ax≡c(mod b) 的解集是：x = k*x1 + t*(b/d) t为任意整数其中模b不同的解共有 d 个，为：x = k*x1 + t*(b/d) t=0,1,..d-1•求ax≡c(mod b) 的最小非负整数解：令 ans = k * x1;s = b/d;则 x = ans + t*s t为任意整数则最小非负整数解是：(ans%s + s)%s•对下面的循环：for (variable = A; variable != B; variable += C)statement;A,B,C和variable都是K(K<=32)比特的无符号数,+=运算的结果也是K比特的无符号数，给定 A,B,C和K，问循环执行多少次。
国际大学生程序设计竞赛辅导教程郭嵩山崔昊吴汉荣陈明睿著北京大学出版社前言ACM 国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，简称ACM/ICPC）是由国际计算机界历史最悠久、颇具权威性的组织ACM 学会（Association for Computer Machinery）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。
该项竞赛从 1970 年举办至今已历 25 届，因历届竞赛都荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，而受到国际各知名大学的重视，并受到全世界各著名计算机公司的高度关注，成为世界各国大学生最具影响力的国际级计算机类的赛事，ACM 所颁发的获奖证书也为世界各著名计算机公司、各知名大学所认可。
该项竞赛分区域预赛和世界决赛两个阶段进行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的 3~4 月举行，而区域预赛安排在上一年的 9 月~12 月在各大洲举行。
ACM/ICPC 的区域预赛是规模很大，范围很广的赛事，近几年，全世界有 1000 多所大学，近 2000 支参赛队在六大洲的 28~30 个赛站中争夺世界决赛的 60 个名额，其激烈程度可想而知。
与其他编程竞赛相比，ACM/ICPC 题目难度更大，更强调算法的高效性，不仅要解决一个指定的命题，而且必需要以最佳的方式解决指定的命题；它涉及知识面广，与大学计算机系本科以及研究生如程序设计、离散数学、数据结构、人工智能、算法分析与设计等相关课程直接关联，对数学要求更高，由于采用英文命题，对英语要求较高，ACM/ICPC 采用3 人合作、共用一台电脑，所以它更强调团队协作精神；由于许多题目并无现成的算法，需要具备创新的精神，ACM/ICPC 不仅强调学科的基础，更强调全面素质和能力的培养；由于ACM/ICPC 是采用5 小时全封闭式竞赛，参赛队员与外界完全隔离，完全独立完成，没有任何水份，是其实际能力的真实表露，其成绩可信度甚高；但ACM/ICPC 又是一种“开卷考试”，可以带任何书籍、资料甚至源程序代码清单（但不能带软盘），不需要去死背算法，而强调的是算法的灵活运用；与其它计算机竞赛（如软件设计，网站设计等）相比，ACM/ICPC 有严谨而客观的评判规则（严格的数据测试），排除了因评委的主观因素而造成评审不公平的现象，所以，ACM/ICPC 对成绩的争议较少，大家比较心服口服。
