2023年8月1日发(作者：)
acm经历和经验我看的⼀篇⾮常好的经验之谈，于是转载了过来，关于时间安排等。我看到的⼀篇⾮常好的⽂章，于是转了过来，标明出处：内容开始：⾸先，我想说的就是，我是⼀个很普通的ACMer，⾼中没有参加过任何计算机和数学竞赛的经历，也没有ben那样过⼈的天资，努⼒⾄今也未能取得什么成绩，我之所以写下这篇⽂章，只是希望给刚进⼤学或者刚进ACM队的同学⼀点⼩⼩的帮助，希望你们可以少⾛⼀些弯路，更希望你们可以帮助华理取得我没能取得的辉煌。(1).起步阶段
我是从⼤⼆开始接触ACM的，要说基础的话就是⼤⼀的C语⾔课程了，语⾔⽅⾯的基础也弱，不过ACM起步阶段对于语⾔的要求并不是太⾼，只要掌握了学校C语⾔的课程，基本就可以开始你ACM的历程了，不过这也仅限于开始的时候，当你的ACM学到⼀定程度的时候，每道题的代码长度也会越来越长，你会发现⼀些C+ +的语⾔特性可以极⼤得简化你的代码长度及思路，⽽且C+ +本⾝就是⼀门⾮常重要的语⾔，啃下C+ +⽆论是对于ACM⽔平的提⾼，还是为后继Windows编程打下基础，都是有极⼤的帮助的。⾄于很多⼈所遇到的所谓“不知如何开头”的问题，我也想谈谈我的看法，⾸先你需要做的就是把PKU上⼀些最基础的模拟题敲⼀下，为什么呢？对于⼀个过去没有接触过编程的⼈来说，模拟题可以在相当程度上帮助你提⾼的编码能⼒，这⾥的编码能⼒，即将你的想法或者说是思路，在尽可能短的时间内，⽤尽可能优美的代码去完全正确地实现它，⾄于何为优美，我想在你学习的过程中你会慢慢体会到的。这⾥你可能要问了，去哪⾥找那么多模拟题呢？我想你只要在Google上搜索下“PKU ⽔题”之类的关键字，或者直接看下我们学校的题⽬分类(想要的同学可以发邮件给我问我要)就可以找到了。那么这样的题要做多少道呢？我想，对于⼀个初学者来说，做上⼤约30道～50道的简单模拟题就⾜够了。
我从⼤⼆的暑假开始在PKU上做题，由于那个时候主要抱着⼀个“玩玩”的⼼态，根本就没有任何⽐赛的打算，整个暑假边玩边学，基本上没怎么接触过算法题，也就切了⼏⼗道最简单的⽔题，直到暑假集训结束了也没什么长进，由于暑假最后⼤⼆的学长(那个时候我是⼤⼀)还有军训，所以我们这些⼤⼀的就全部回家了，回家之后就完全把ACM放到⼀边了，基本就没有碰过，这种颓废的状态⼀直持续到了⼤⼆开始后相当长⼀段时间，不知什么原因我⼜开始切题了(我真的忘记当初是为什么⼜开始切题了)，并且开始接触各种基础算法了，刚开始的时候确实⽐较痛苦，但靠着天哥和ben⽜的帮助以及上⽹看别⼈的解题报告总算摸爬滚打做了200道题左右，这个时候⼤⼆上差不多已经要结束了，⽽我由于要出国的原因在寒假中参加了新东⽅TOEFL的培训班，ACM⼜被我“正当理由”放到了⼀边，⽽且整个寒假⼏乎都没有碰过。⽽⼤⼆下学期开学后我⼜复习了⼀段时间TOEFL，直到考试结束我才⼜开始了切题的⽣涯，其实从严格意义上来说，知道这个时候我才开始了真正意义上有计划的且⽐较刻苦的ACM训练，⼀直训练到了上海邀请赛的时候。这是我参加ACM以来参加的第⼀次⽐赛，也是我第⼀次⽤⾃⼰的眼睛确认了⾃⼰和别⼈之间的差距，这场⽐赛给我的震撼很⼤，⼀样是⼤学⽣，⼀样的年龄，但是差距却如此之⼤，确实令⼈深思。知道这个时候我才真正意识到了⾃⼰曾经浪费了多少的时间，意识到了⾃⼰的⽔平竟然和别⼈有那么⼤的差距。这之后不久，⼤⼆的暑假集训就开始了，这两个⽉是我搞ACM以来进步最快的⼀段时间。下⾯，我就想把⾃⼰的⼀些做题的经验和感受告诉⼤家，希望能对⼤家有帮助。
(2).做题要点
⾸先，我认为最重要的是独⽴思考和敢于尝试，所谓的独⽴思考，就是不要养成做不来就上⽹搜别⼈代码的习惯，如果实在做不出来，可以尝试问⼀下别⼈思路，然后再尝试⾃⼰去实现，等做出来之后再看别⼈的代码，学习⼀些好的地⽅。⽽所谓的敢于尝试，就是不要怕错，编程是⼀件很特别的事情，他可以在当场验证你的理论的正确性，所以，不要把错藏在⼼⾥，打开电脑⾃⼰试下，⾃然就明了了，也只有这样，你才能从⾃⼰完成的每⼀道题中获得快乐。其次，就是要写解题报告，把⾃⼰在这道题中学到的知识和碰到的问题记下来，并经常梳理总结⾃⼰学过的知识，把他们联系在⼀起。当你坚持到这⾥的时候，我想和你说，你是好样的，但是，还请你继续坚持下去，因为ACM中真正的乐趣才刚刚开始，也就是算法。我想，包括我在内的⼤部分初识算法的同学都会感到⾮常的迷茫，因为就我的经历来说，我是⼏乎每拿到⼀道题，⼤部分情况下都是⼀点没有思路，难得有点思，写了⽼半天还可能是错的，我想，碰到这种情况的你完全不必担⼼，因为有相当⼀批⼈都是和你⼀样的，同时，在他们当中也有很多的⼈成为了相当出⾊的ACMer，当然了，这也是在他们付出了相当的努⼒之后才取得的结果。所以，我相信，只要你坚持下去，终会有收获的⼀天的。那么在下⾯⼀⼤点中，我想说下你们要攻克的⼏个最主要的⽅⾯。
(3).动态规划(Dynamic Programming,以下简称DP)
俗话说，要看⼀个⼈的算法⽔平，只要看⼀下他做DP题的⽔平就OK了，⽽在ACM这个多变的赛场上，⼏多算法沉浮，唯有DP⼏乎从未消失过，如果你问我什么类型的题在赛场上出现的概率最⾼，我可以毫不犹豫地告诉你，是DP。由此也可以看出，DP的地位有多么重要，那么这样⼀个⼏乎每场⽐赛都会出现的题型，应该很难啊，为什么要让我们从DP⼊⼿呢？确实，DP是很难，其变型之多，覆盖知识⾯之⼴，确实让⼈望⽽⽣却，但是，我想说下如何⼊门DP题。⾸先是DP⼏个最为基本的模型，LCS(最长公共⼦序列)，LIS(最长上升⼦序列)，最⼤公共⼦段和，数塔问题，矩阵连乘等⼏个最为经典的问题，⼤家⼀开始的时候可能难以理解DP中⾃底向上，重叠⼦结构等基本思想，对于这⼏道问题可以先看⼀下别⼈的代码和书上的讲解，然后再⾃⼰反复地理解，理解了之后再⾃⼰敲⼀下代码，如果有地⽅实在不理解，可以先放⼀下，去看看其他题，回过头来再想⼀下以前的题，也许会有豁然开朗的效果。吃透了DP的⼏个经典问题之后，就可以做⼀下这些经典问题的变型了，⽐如最⼤公共⼦段和的变型——最⼤⼦矩阵和最⼤m⼦段和，最长公共⼦序列和最长上升⼦序列的变型——最长公共上升⼦序列等等。并且可以尝试接触DP的⼀些重要的应⽤，最重要的要数背包问题，背包问题是DP⼀个很⼤的分⽀(算是分⽀吧，我找不到其他更好的词来形容他了)，同样也有⾮常多的变型，如最为基础的01背包，以及扩充出去的多重背包，完全背包，分组背包，树型DP(这个知识点我待会会介绍)中应⽤⾮常多的泛化背包等等，下⾯我把最为基本01背包，多重背包和完全背包讲⼀下，⾸先是最简单的01背包，伪代码如下：
for i=1..N
for v=V..0
f[v]=max{ f[v], f[ v-c[i] ] + w[i] }
这⾥为什么要倒推呢？其实道理很简单，因为这⾥其实是利⽤类似滚动数组的概念，只不过他连2个数组都不⽤开了，只需要开⼀个数组就可以了，这是为什么呢？因为传统的⼆维数组中f[i][v]的值是由max( f[i-1][v], f[i-1][ v-c[i] ] + w[i] )得来的，所以每次f[v]的值是由上层循环中f得来的，所以改成了⼀维数组后，如果从⼩到⼤循环的话，在计算完成f[v] 之后，就会在计算f[v’](v’ >=v)时发⽣错误，因为原本计算f[v’]所需的上层循环中的f[v]的值已经被新的值覆盖掉了，故必须从⼤到⼩循环。其次是多重背包，完全可以化为01背包问题，不过是把相同价值的同种类物品看成多个价值相同的不同种类物品，即⽐01背包多了⼀重循环，要注意的是这两层循环都要从⼤到⼩，原理和01背包类似。最后是完全背包问题，伪代码如下：
for i=1..N
for v=0..V
f[v]=max{ f[v], f[ v-c[i] ] + w[i] }
这个伪代码与01背包的伪代码只有v的循环次序不同⽽已。为什么这样⼀改就可⾏呢？⾸先想想为什么01背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推⽽来。换句话说，这正是为了保证每件物品只选⼀次，保证在考虑“选⼊第i件物品”这件策略时，依据的是⼀个绝⽆已经选⼊第i件物品的⼦结果f[i-1][v-c[i]]。⽽现在完全背包的特点恰是每种物品可选⽆限件，所以在考虑 “加选⼀件第i种物品”这种策略时，却正需要⼀个可能已选⼊第i种物品的⼦结果f[i][v-c[i]]，所以就可以并且必须采⽤v= 0..V的顺序循环。这就是这个简单的程序为何成⽴的道理。这⾥我向⼤家推荐⼀下浙江⼤学的DD⽜所写的《背包九讲》，是背包⼊门及提⾼的最为经典的资料。现在就要讲⼀下树型DP了，树型DP其实就是DP，只不过是建⽴在树模型之上的DP罢了，不过树型DP说起来虽然简单，确是DP中相当困难的⼀个知识点，要好好理解，多做些题才⾏。最后是状态压缩DP，这也是⼀个DP的⼀个难点，所谓的状态是指利⽤⼆进制或者其他进制的数来表⽰状态从⽽达到空间上压缩的⽬的，这⼀类的状态设计⼀般都很巧妙，⽽且涉及的众多位运算对于编码能⼒也是⼀个相当⼤的挑战，介于状态压缩DP是⽤记忆化搜索(所谓记忆化搜索，是DP的另外⼀种递归的实现形式，即所谓的⾃顶向下)来实现的，⼜要牵涉到搜索的知识点，建议等学习了相关的内容之后再回过来头来学习这个知识点。状态压缩的经典题有棋盘覆盖问题，炮兵阵地等。
(4).搜索(包括DFS, BFS, A*)
搜索也是ACM中相当重要的⼀个组成部分，涉及范围也是相当之⼴，⾸先是最为基础的深度优先搜索DFS，所谓的DFS，其实就是通过递归的⽅式枚举所有的可能从⽽得到我们想要的结果，⽽搜索中相当重要的⼀个技巧就是剪枝，即⼈为地删去⼀些没有必要搜索的可能，从⽽提⾼我们程序的效率，DFS的经典题有最为著名的⼋皇后为题，Sticks等等。其实DFS的题实在是太多了，PKU上有很多的题可以供我们练⼿。另外⼀个就是⼴度优先搜索(BFS)了，⼴度优先搜索是基本思想就是建⽴⼀个队列(队列是⼀种基本的数据结构，我会在下⼀部分中说明)，然后每⼀次都拿出队列出的⼀个点扩展出所有的可能，再把我们需要的解放⼊队列等着下次再扩展，⼀直扩展到找到答案或者不能扩展为⽌，BFS的经典题有跳马问题，⼋数码等。BFS有⼀个⾮常常⽤的技巧或者说是优化，就是双向BFS，思想是⼀样的，就是同时从起点和终点开始扩展，等到出现交点的时候就意味着找到了答案，这样⽐起普通的BFS可以节省⼤量的空间和时间。BFS还有另外⼀个常见的扩展，就是优先队列BFS，所谓的优先队列(优先队列是队列的⼀种实现，我同样会在下⼀部分中给出解释)，就是始终都保持队列的队⾸元素是最⼩的，这样每次扩展的就是当前最⼩的元素了，这⾥所谓的最⼩，其实指的是当前看来最优的解，利⽤这么⼀种贪⼼的⽅法，来加快我们搜到答案的速度，当然了，具体的效率还要看题⽬的数据。说了这么多的优先队BFS，其实就是A*的⼀种特殊情况，A*的中⽂名是启发式搜索，是⼈⼯智能中常⽤的⼀种搜索技术，A*最基础的应⽤就是求最短路，通过某个估价函数对当前的点做出⼀个价值评估，然后将这些扩展出来的点按照其价值放⼊⼀个优先队列中，那么我们每次拿出的队⾸元素不就是我们当前最优希望的⼀个点吗？如果⽤STL(C++的标准模板库，同样会在下⼀部分中给出解释)来实现优先队列的话，A*⽐起BFS的代码量⼏乎没增加，⽆⾮多了⼀个估价函数，但是问题就在于如何更好地设计出⼀个估价函数，A*的经典题有贪吃蛇，⼋数码。
(5).C++应⽤之STL
STL是C++的标准模板库，为我们提供了相当多的现成的库函数和数据结构，STL即可以极⼤地缩短我们的代码长度，有可以极⼤地降低我们出错的概率。那么你可能就奇怪了，为什么我还会恨STL呢？理由很简单，我们必须要付出相当⼤代价，那就是效率。下⾯我简要地介绍⼀下STL在ACM中的简单应⽤。⾸先就是STL中的库函数了，其中我们有我们最为常⽤的sort排序函数，有find，lower_bound和upper_bound等⼀些查找函数⽤来简化我们的代码，另外最常⽤的就是顺序容器和关联容器了，其实顺序容器可以相当相当程度上代替⼀些常⽤的基础数据结构如vector可以代替长度可变的数组(可以简单地实现邻接表)，list可以代替链表，stack可以代替栈，deque可以代替双端队列，priority_queue可以代替我们前⾯提到的优先队列，⽽关联容器中的map可以实现任意两种类型的数据之间的索引，⽽set可以查找某个集合中是否存在某个元素。
(6).数据结构之基础篇
数据结构在ACM中应⽤⾮常⼴泛，但单独考查某个数据结构基础的题⽬较少，⼀般都是起⼀些辅助的作⽤，⽐如我们前⾯提到的优先队列，还有⼀个⾮常常⽤的就是哈希，前⾯我们提到过，在BFS的过程中，我们需要从每次扩展出来的点中筛选出来我们需要的点放⼊队列中，哪些是不需要的点，⼀般来说，指的是和以前某个搜索过的点具有相同的状态的点，⽽判别状态是否相同的⽅法经常是利⽤哈希来保存以前搜索过的状态，并且判断每次扩展出来的点的状态是否已经存在，如果不存在，我们再把它放⼊队列中。
(7).数据结构之提⾼篇(包括并查集,树状数组,线段树)
数据结构还有⼀些相对来说⽐较⾼级的应⽤，这些知识点可能会作为⼀个知识点单独考查，⾸先是并查集，并查集的基本思想是在⼀个集合中选出⼀个元素作为⼀个集合代表元素，通过对这些代表元素的操作来实现集合之间的合并操作，在求最⼩⽣成树的经典算法Kruscal中也会⽤到并查集来判断两个元素是否属于同⼀条边，这在下⼀部分图论的总结中会提到。并查集也有很多的题⽬可以做，经典题有⾷物链，搞会⽤到并查集来判断两个元素是否属于同⼀条边，这在下⼀部分图论的总结中会提到。并查集也有很多的题⽬可以做，经典题有⾷物链，搞同性恋的⾍⼦，帮派结伙等，并查集还有⼀个变型就是从⼀个集合中删除某⼀个元素，我们知道，普通的并查集是不包括删除元素的功能的，⽽删除元素的实现其实也很简单，就是对每个点都建⽴⼀个索引，⼀开始每个点的索引都指向⾃⼰，当⼀个元素被删除掉的时候，先建⽴⼀个新的不属于任何集合的新点，在把被删除掉的点索引到那个新点之上即可。第⼆部分是树状数组，他⽀持在O(nlogn)的复杂度内算出区间内的元素之和，他的思想很是巧妙，就是树状数组总结：假设c[]为树状数组，a[]为原数组，则两者之间存在这么⼀个关系，c[i]代表的意义是从a[i]开始往前2^k个元素的和(k为i化成⼆进制后尾部包含的0的个数)。由位运算的性质可以得到：对于i来说，i&(-i) = 2^k，那么树状数组的基本功能就能明⽩了。树状数组也有⽐较多的题，PKU_1990，PKU_2828，PKU_2155等等。最后我想说⼀下线段树，线段树是⼀个⾮常强⼤的数据结构，他⽀持在O(nlogn)的复杂度内对区间范围内的元素进⾏修改，删除等操作，和并查集，树状数组不同的是，线段树的实现⾮常灵活，⼀道题⼀个样，⼏乎没有什么定式，当然了，最为基本的思想就是每个节点代表⼀个区间，他的左右⼦树分别为左半区间和右半区间，如此这般地递归定义，直到为⼀个点或者包含⼀个单位为⽌。线段树也有⼏个基本模型和经典例题，⾸先我想讲的是线段树的⼀种相对⽽⾔⽐较简单但是⾮常经典的应⽤来引⼊线段树的概念等⼀系列问题，即染⾊问题。以PKU_2777为例，题⽬⼤意是有⼀块长度为L厘⽶的板，每厘⽶可以看成⼀个单位区间，颜⾊的种类由数字表⽰，⼀开始每个区间的颜⾊都是1，⽽现在要对这种树进⾏O次操作，操作有两种，第⼀种是将区间A到B的颜⾊都染成C颜⾊，第⼆种是询问区间A到B之间⼀共有⼏种颜⾊。最简单的想法可能是开个长度为L的数组a[]，⽽a[i]存的就是第i格的颜⾊，但是可⾏吗？我们来看下数据范围，L的范围是⼗万，O的范围也是⼗万，那么算法复杂度就是O(LO)，明显会超时，所以我们选择⽤线段树来帮助我们解决这个问题，其实线段树这个名词并不能很好地阐述它强⼤的功能，我更喜欢他的学术名词——区间树，同其他的树⼀样，他可以在O(logL)的时间内对树进⾏维护操作，这也就意味着他可以在O(logL)的时间内对⼀段区间进⾏⼀系列的操作。正是线段树这种⾼效，让他在RMQ问题，以及求矩形合并⾯积，周长等⼀系列问题中得到了充分的应⽤。这⾥我想讲⼀下RMQ问题(即求区间内最⼤or最下值的问题)，众所周知，RMQ问题有⼀种O(NlogN)的预处理以及O(1)时间求出任意区间内最⼤or最⼩值的离线算法（所谓离线，即不能在求的过程中动态地改变或者插⼊区间的值），即ST(Sparse Table)算法，相⽐之下，线段树并没有效率上的优势，但ST算法有个局限性，就是不⽀持在线操作，⽽线段树则没有这种限制，由此可知，线段树的强⼤。线段树还有⼀个⾼级的应⽤就是对于区间最值信息的维护，相应的经典题有很多，也有⼀定的难度，PKU_2482，PKU_1151(求n个矩形合并后的⾯积)，PKU_1177(求n个矩形合并后的边界周长)等等。最值的维护要抓住的基本思想就是递归地维护每⼀颗⼦树，利⽤⼦树的信息去维护⽗亲。
( 8 ).字符串(包括KMP算法,Trie树,后缀数组)
字符串处理也是ACM中相当⼤的⼀块知识⾯，⽽且也具有相当的实际应⽤⾯，其实对于字符串的知识我⾃⼰接触的也⽐较少，所以只能简单地谈⼀下⼏个最为基础的算法，KMP算法是两串匹配最为基础的线性算法，该算法的核⼼是对于next数组的理解，该数组是对于⼀个串进⾏了预处理得到的，从⽽成功将两串匹配的复杂度降到了线性。但KMP算法只能是两串之间的匹配，如果我们要多串匹配的话该怎么办呢？Trie帮助我们解决了这个难题，Trie其实是⼀颗字母树，树的每个节点都有26个英⽂字母，通过对这些节点的进⾏标记来插⼊⼀个字符串，在插⼊了n个字符串之后，我们就可以同时对这n个字符串之后我们就可以同时对这n个字符串进⾏匹配了，Trie树有⼀个很⼤的缺点，就是他所需要的空间是指数级别的，所有⼀般来说字符串的长度超过15的话我们就应该考虑别的⽅法了。最后是后缀数组，算法的主要精髓在于对于height数组的理解和应⽤，在国家队论⽂中有两篇⽂章是专门介绍后缀数组的，我这⾥就不赘述了。
(9).图论(包括最短路,最⼩⽣成树,强连通分量等知识点)
之所以把图论的内容放在最后讲完全是因为图论的知识点实在是太多了，涉及的⽅⾯也实在是太⼴了，我这⾥挑⼏个我题⽬做得⽐较多的⽅⾯来简单总结⼀下。⾸先就是最短路了，主要分为多源最短路，⽤的算法是⾮常经典的Floyd算法，复杂度为O(n^3)，实现起来相当简单，主要就是DP的思想。还有单源最短路，最原始的⽅法是Bellman-Ford，但该算法使⽤的概率不⾼，因为他有⼀个⾮常好的替代品，就是SPFA，SPFA的实现有点类似⼴搜，代码也⾮常短，对于Bellman-Ford求⼀个图中是否存在负环的问题可以以完全地替代，另外在稀疏图中求最短路的效率甚⾄要⾼于⽤了优先队列优化过的Dijkstra，确实是⼀个实⽤的好东西。当然了，最为著名的Dijkstra算法是绝对不能不提的，该算法是我们求最短路时最常⽤的算法，但是由于他利⽤了贪⼼准则，所以⼀定要注意Dijkstra不能处理有负权边的图，⽽Dijkstra也有⼏个⾮常经典的变型，⼀个是将Dijkstra扩展到⼆维来求次短路，另⼀个是利⽤A*来求次短路，⼤家是否注意到，学到后⾯的时候，不同知识块之间的分界已经越来越不清晰了，因为我们的脑中正在逐步形成⼀张知识⽹，将每⼀个知识点都有机地串联到了⼀起。第⼆个⼤点是最⼩⽣成树，该类问题也有两个⼴为⼈知的算法，适⽤于稠密图的Prim算法和适⽤于稀疏图的Kruscal算法(该算法中要⽤到并查集的算法)，最⼩⽣成树同样有⼀些经典的变型，如次⼩⽣成树，最⼩限制度⽣成树等。再有⼀类⾮常重要的问题就是⼆分匹配问题，该问题涉及的知识点也是相当的多，求⽆权⼆分图的最⼤匹配有最为经典的匈⽛利算法以及求带权的⼆分图的最⼩/⼤匹配的KM算法，⽽由不带权的⼆分图的最⼤匹配数衍⽣出去的知识点有最⼩覆盖问题，最⼩路径覆盖问题等等，这块内容概念性⽐较强，其实说起来，图论最⼤的特点就是概念性强，变型极多，如果不深⼊地理解每⼀次问题及其经典算法，着实⽆法应变。最来就是欧拉回路问题，该类问题⽐较简单，⽆⾮就是两种，⼀个是判断图中是否存在欧拉回路，再⼀个就是求出该欧拉回路中的⼀条，实现起来也很简单，⼀个DFS就可以完成了。还有就是强连通分量，该算法的核⼼就是对⼀个图求强连通分量后缩点，从⽽将⼀个图转化成⼀个有向⽆环图，从⽽⽅便我们进⾏接下去的操作。最后⼀个⼤块就是⽹络流了，该内容我涉及也⽐较少，主要就是⼏个求⽹络流的经典算法，如HLPP，ISAP，EK等等，⽹络流的变型也⾮常地多，需强加练习。
(10).ACM最终回之⽐赛篇
我参加过的正式⽐赛有两场，⼀场是⼤⼆下的上海邀请赛，另⼀场是⼤三上的合肥区域赛，由于⽔平有限，终究还是只拿了两块铜牌，下⾯我想谈⼀下组队的个⼈感受，⾸先是队员的构成，⾄少要有⼀个编码能⼒较强的⼈主要负责敲代码以增加出简单题的速度，另外就是数学基础较强的⼈，由于ACM现在越来越喜欢出数学题，⽽且数学好的往往思路会⽐较开阔，可以为整个团队提供想法，再有⼀个就是算法接触⽐较⼴的⼈，这⼀类的⼈接触的算法⽐较多，切题数也⽐较多，虽然可能没有哪个⽅⾯特别强，但其丰富的做题经验保证了他对于⼀道题的算法嗅觉，可以为整个团队指明⽅向。说到这⾥，我的总结也要结束了，希望⼤家可以从中可以获得帮助。
2023年8月1日发(作者：)
acm经历和经验我看的⼀篇⾮常好的经验之谈，于是转载了过来，关于时间安排等。我看到的⼀篇⾮常好的⽂章，于是转了过来，标明出处：内容开始：⾸先，我想说的就是，我是⼀个很普通的ACMer，⾼中没有参加过任何计算机和数学竞赛的经历，也没有ben那样过⼈的天资，努⼒⾄今也未能取得什么成绩，我之所以写下这篇⽂章，只是希望给刚进⼤学或者刚进ACM队的同学⼀点⼩⼩的帮助，希望你们可以少⾛⼀些弯路，更希望你们可以帮助华理取得我没能取得的辉煌。(1).起步阶段
我是从⼤⼆开始接触ACM的，要说基础的话就是⼤⼀的C语⾔课程了，语⾔⽅⾯的基础也弱，不过ACM起步阶段对于语⾔的要求并不是太⾼，只要掌握了学校C语⾔的课程，基本就可以开始你ACM的历程了，不过这也仅限于开始的时候，当你的ACM学到⼀定程度的时候，每道题的代码长度也会越来越长，你会发现⼀些C+ +的语⾔特性可以极⼤得简化你的代码长度及思路，⽽且C+ +本⾝就是⼀门⾮常重要的语⾔，啃下C+ +⽆论是对于ACM⽔平的提⾼，还是为后继Windows编程打下基础，都是有极⼤的帮助的。⾄于很多⼈所遇到的所谓“不知如何开头”的问题，我也想谈谈我的看法，⾸先你需要做的就是把PKU上⼀些最基础的模拟题敲⼀下，为什么呢？对于⼀个过去没有接触过编程的⼈来说，模拟题可以在相当程度上帮助你提⾼的编码能⼒，这⾥的编码能⼒，即将你的想法或者说是思路，在尽可能短的时间内，⽤尽可能优美的代码去完全正确地实现它，⾄于何为优美，我想在你学习的过程中你会慢慢体会到的。这⾥你可能要问了，去哪⾥找那么多模拟题呢？我想你只要在Google上搜索下“PKU ⽔题”之类的关键字，或者直接看下我们学校的题⽬分类(想要的同学可以发邮件给我问我要)就可以找到了。那么这样的题要做多少道呢？我想，对于⼀个初学者来说，做上⼤约30道～50道的简单模拟题就⾜够了。
我从⼤⼆的暑假开始在PKU上做题，由于那个时候主要抱着⼀个“玩玩”的⼼态，根本就没有任何⽐赛的打算，整个暑假边玩边学，基本上没怎么接触过算法题，也就切了⼏⼗道最简单的⽔题，直到暑假集训结束了也没什么长进，由于暑假最后⼤⼆的学长(那个时候我是⼤⼀)还有军训，所以我们这些⼤⼀的就全部回家了，回家之后就完全把ACM放到⼀边了，基本就没有碰过，这种颓废的状态⼀直持续到了⼤⼆开始后相当长⼀段时间，不知什么原因我⼜开始切题了(我真的忘记当初是为什么⼜开始切题了)，并且开始接触各种基础算法了，刚开始的时候确实⽐较痛苦，但靠着天哥和ben⽜的帮助以及上⽹看别⼈的解题报告总算摸爬滚打做了200道题左右，这个时候⼤⼆上差不多已经要结束了，⽽我由于要出国的原因在寒假中参加了新东⽅TOEFL的培训班，ACM⼜被我“正当理由”放到了⼀边，⽽且整个寒假⼏乎都没有碰过。⽽⼤⼆下学期开学后我⼜复习了⼀段时间TOEFL，直到考试结束我才⼜开始了切题的⽣涯，其实从严格意义上来说，知道这个时候我才开始了真正意义上有计划的且⽐较刻苦的ACM训练，⼀直训练到了上海邀请赛的时候。这是我参加ACM以来参加的第⼀次⽐赛，也是我第⼀次⽤⾃⼰的眼睛确认了⾃⼰和别⼈之间的差距，这场⽐赛给我的震撼很⼤，⼀样是⼤学⽣，⼀样的年龄，但是差距却如此之⼤，确实令⼈深思。知道这个时候我才真正意识到了⾃⼰曾经浪费了多少的时间，意识到了⾃⼰的⽔平竟然和别⼈有那么⼤的差距。这之后不久，⼤⼆的暑假集训就开始了，这两个⽉是我搞ACM以来进步最快的⼀段时间。下⾯，我就想把⾃⼰的⼀些做题的经验和感受告诉⼤家，希望能对⼤家有帮助。
(2).做题要点
⾸先，我认为最重要的是独⽴思考和敢于尝试，所谓的独⽴思考，就是不要养成做不来就上⽹搜别⼈代码的习惯，如果实在做不出来，可以尝试问⼀下别⼈思路，然后再尝试⾃⼰去实现，等做出来之后再看别⼈的代码，学习⼀些好的地⽅。⽽所谓的敢于尝试，就是不要怕错，编程是⼀件很特别的事情，他可以在当场验证你的理论的正确性，所以，不要把错藏在⼼⾥，打开电脑⾃⼰试下，⾃然就明了了，也只有这样，你才能从⾃⼰完成的每⼀道题中获得快乐。其次，就是要写解题报告，把⾃⼰在这道题中学到的知识和碰到的问题记下来，并经常梳理总结⾃⼰学过的知识，把他们联系在⼀起。当你坚持到这⾥的时候，我想和你说，你是好样的，但是，还请你继续坚持下去，因为ACM中真正的乐趣才刚刚开始，也就是算法。我想，包括我在内的⼤部分初识算法的同学都会感到⾮常的迷茫，因为就我的经历来说，我是⼏乎每拿到⼀道题，⼤部分情况下都是⼀点没有思路，难得有点思，写了⽼半天还可能是错的，我想，碰到这种情况的你完全不必担⼼，因为有相当⼀批⼈都是和你⼀样的，同时，在他们当中也有很多的⼈成为了相当出⾊的ACMer，当然了，这也是在他们付出了相当的努⼒之后才取得的结果。所以，我相信，只要你坚持下去，终会有收获的⼀天的。那么在下⾯⼀⼤点中，我想说下你们要攻克的⼏个最主要的⽅⾯。
(3).动态规划(Dynamic Programming,以下简称DP)
俗话说，要看⼀个⼈的算法⽔平，只要看⼀下他做DP题的⽔平就OK了，⽽在ACM这个多变的赛场上，⼏多算法沉浮，唯有DP⼏乎从未消失过，如果你问我什么类型的题在赛场上出现的概率最⾼，我可以毫不犹豫地告诉你，是DP。由此也可以看出，DP的地位有多么重要，那么这样⼀个⼏乎每场⽐赛都会出现的题型，应该很难啊，为什么要让我们从DP⼊⼿呢？确实，DP是很难，其变型之多，覆盖知识⾯之⼴，确实让⼈望⽽⽣却，但是，我想说下如何⼊门DP题。⾸先是DP⼏个最为基本的模型，LCS(最长公共⼦序列)，LIS(最长上升⼦序列)，最⼤公共⼦段和，数塔问题，矩阵连乘等⼏个最为经典的问题，⼤家⼀开始的时候可能难以理解DP中⾃底向上，重叠⼦结构等基本思想，对于这⼏道问题可以先看⼀下别⼈的代码和书上的讲解，然后再⾃⼰反复地理解，理解了之后再⾃⼰敲⼀下代码，如果有地⽅实在不理解，可以先放⼀下，去看看其他题，回过头来再想⼀下以前的题，也许会有豁然开朗的效果。吃透了DP的⼏个经典问题之后，就可以做⼀下这些经典问题的变型了，⽐如最⼤公共⼦段和的变型——最⼤⼦矩阵和最⼤m⼦段和，最长公共⼦序列和最长上升⼦序列的变型——最长公共上升⼦序列等等。并且可以尝试接触DP的⼀些重要的应⽤，最重要的要数背包问题，背包问题是DP⼀个很⼤的分⽀(算是分⽀吧，我找不到其他更好的词来形容他了)，同样也有⾮常多的变型，如最为基础的01背包，以及扩充出去的多重背包，完全背包，分组背包，树型DP(这个知识点我待会会介绍)中应⽤⾮常多的泛化背包等等，下⾯我把最为基本01背包，多重背包和完全背包讲⼀下，⾸先是最简单的01背包，伪代码如下：
for i=1..N
for v=V..0
f[v]=max{ f[v], f[ v-c[i] ] + w[i] }
这⾥为什么要倒推呢？其实道理很简单，因为这⾥其实是利⽤类似滚动数组的概念，只不过他连2个数组都不⽤开了，只需要开⼀个数组就可以了，这是为什么呢？因为传统的⼆维数组中f[i][v]的值是由max( f[i-1][v], f[i-1][ v-c[i] ] + w[i] )得来的，所以每次f[v]的值是由上层循环中f得来的，所以改成了⼀维数组后，如果从⼩到⼤循环的话，在计算完成f[v] 之后，就会在计算f[v’](v’ >=v)时发⽣错误，因为原本计算f[v’]所需的上层循环中的f[v]的值已经被新的值覆盖掉了，故必须从⼤到⼩循环。其次是多重背包，完全可以化为01背包问题，不过是把相同价值的同种类物品看成多个价值相同的不同种类物品，即⽐01背包多了⼀重循环，要注意的是这两层循环都要从⼤到⼩，原理和01背包类似。最后是完全背包问题，伪代码如下：
for i=1..N
for v=0..V
f[v]=max{ f[v], f[ v-c[i] ] + w[i] }
这个伪代码与01背包的伪代码只有v的循环次序不同⽽已。为什么这样⼀改就可⾏呢？⾸先想想为什么01背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推⽽来。换句话说，这正是为了保证每件物品只选⼀次，保证在考虑“选⼊第i件物品”这件策略时，依据的是⼀个绝⽆已经选⼊第i件物品的⼦结果f[i-1][v-c[i]]。⽽现在完全背包的特点恰是每种物品可选⽆限件，所以在考虑 “加选⼀件第i种物品”这种策略时，却正需要⼀个可能已选⼊第i种物品的⼦结果f[i][v-c[i]]，所以就可以并且必须采⽤v= 0..V的顺序循环。这就是这个简单的程序为何成⽴的道理。这⾥我向⼤家推荐⼀下浙江⼤学的DD⽜所写的《背包九讲》，是背包⼊门及提⾼的最为经典的资料。现在就要讲⼀下树型DP了，树型DP其实就是DP，只不过是建⽴在树模型之上的DP罢了，不过树型DP说起来虽然简单，确是DP中相当困难的⼀个知识点，要好好理解，多做些题才⾏。最后是状态压缩DP，这也是⼀个DP的⼀个难点，所谓的状态是指利⽤⼆进制或者其他进制的数来表⽰状态从⽽达到空间上压缩的⽬的，这⼀类的状态设计⼀般都很巧妙，⽽且涉及的众多位运算对于编码能⼒也是⼀个相当⼤的挑战，介于状态压缩DP是⽤记忆化搜索(所谓记忆化搜索，是DP的另外⼀种递归的实现形式，即所谓的⾃顶向下)来实现的，⼜要牵涉到搜索的知识点，建议等学习了相关的内容之后再回过来头来学习这个知识点。状态压缩的经典题有棋盘覆盖问题，炮兵阵地等。
(4).搜索(包括DFS, BFS, A*)
搜索也是ACM中相当重要的⼀个组成部分，涉及范围也是相当之⼴，⾸先是最为基础的深度优先搜索DFS，所谓的DFS，其实就是通过递归的⽅式枚举所有的可能从⽽得到我们想要的结果，⽽搜索中相当重要的⼀个技巧就是剪枝，即⼈为地删去⼀些没有必要搜索的可能，从⽽提⾼我们程序的效率，DFS的经典题有最为著名的⼋皇后为题，Sticks等等。其实DFS的题实在是太多了，PKU上有很多的题可以供我们练⼿。另外⼀个就是⼴度优先搜索(BFS)了，⼴度优先搜索是基本思想就是建⽴⼀个队列(队列是⼀种基本的数据结构，我会在下⼀部分中说明)，然后每⼀次都拿出队列出的⼀个点扩展出所有的可能，再把我们需要的解放⼊队列等着下次再扩展，⼀直扩展到找到答案或者不能扩展为⽌，BFS的经典题有跳马问题，⼋数码等。BFS有⼀个⾮常常⽤的技巧或者说是优化，就是双向BFS，思想是⼀样的，就是同时从起点和终点开始扩展，等到出现交点的时候就意味着找到了答案，这样⽐起普通的BFS可以节省⼤量的空间和时间。BFS还有另外⼀个常见的扩展，就是优先队列BFS，所谓的优先队列(优先队列是队列的⼀种实现，我同样会在下⼀部分中给出解释)，就是始终都保持队列的队⾸元素是最⼩的，这样每次扩展的就是当前最⼩的元素了，这⾥所谓的最⼩，其实指的是当前看来最优的解，利⽤这么⼀种贪⼼的⽅法，来加快我们搜到答案的速度，当然了，具体的效率还要看题⽬的数据。说了这么多的优先队BFS，其实就是A*的⼀种特殊情况，A*的中⽂名是启发式搜索，是⼈⼯智能中常⽤的⼀种搜索技术，A*最基础的应⽤就是求最短路，通过某个估价函数对当前的点做出⼀个价值评估，然后将这些扩展出来的点按照其价值放⼊⼀个优先队列中，那么我们每次拿出的队⾸元素不就是我们当前最优希望的⼀个点吗？如果⽤STL(C++的标准模板库，同样会在下⼀部分中给出解释)来实现优先队列的话，A*⽐起BFS的代码量⼏乎没增加，⽆⾮多了⼀个估价函数，但是问题就在于如何更好地设计出⼀个估价函数，A*的经典题有贪吃蛇，⼋数码。
(5).C++应⽤之STL
STL是C++的标准模板库，为我们提供了相当多的现成的库函数和数据结构，STL即可以极⼤地缩短我们的代码长度，有可以极⼤地降低我们出错的概率。那么你可能就奇怪了，为什么我还会恨STL呢？理由很简单，我们必须要付出相当⼤代价，那就是效率。下⾯我简要地介绍⼀下STL在ACM中的简单应⽤。⾸先就是STL中的库函数了，其中我们有我们最为常⽤的sort排序函数，有find，lower_bound和upper_bound等⼀些查找函数⽤来简化我们的代码，另外最常⽤的就是顺序容器和关联容器了，其实顺序容器可以相当相当程度上代替⼀些常⽤的基础数据结构如vector可以代替长度可变的数组(可以简单地实现邻接表)，list可以代替链表，stack可以代替栈，deque可以代替双端队列，priority_queue可以代替我们前⾯提到的优先队列，⽽关联容器中的map可以实现任意两种类型的数据之间的索引，⽽set可以查找某个集合中是否存在某个元素。
(6).数据结构之基础篇
数据结构在ACM中应⽤⾮常⼴泛，但单独考查某个数据结构基础的题⽬较少，⼀般都是起⼀些辅助的作⽤，⽐如我们前⾯提到的优先队列，还有⼀个⾮常常⽤的就是哈希，前⾯我们提到过，在BFS的过程中，我们需要从每次扩展出来的点中筛选出来我们需要的点放⼊队列中，哪些是不需要的点，⼀般来说，指的是和以前某个搜索过的点具有相同的状态的点，⽽判别状态是否相同的⽅法经常是利⽤哈希来保存以前搜索过的状态，并且判断每次扩展出来的点的状态是否已经存在，如果不存在，我们再把它放⼊队列中。
(7).数据结构之提⾼篇(包括并查集,树状数组,线段树)
数据结构还有⼀些相对来说⽐较⾼级的应⽤，这些知识点可能会作为⼀个知识点单独考查，⾸先是并查集，并查集的基本思想是在⼀个集合中选出⼀个元素作为⼀个集合代表元素，通过对这些代表元素的操作来实现集合之间的合并操作，在求最⼩⽣成树的经典算法Kruscal中也会⽤到并查集来判断两个元素是否属于同⼀条边，这在下⼀部分图论的总结中会提到。并查集也有很多的题⽬可以做，经典题有⾷物链，搞会⽤到并查集来判断两个元素是否属于同⼀条边，这在下⼀部分图论的总结中会提到。并查集也有很多的题⽬可以做，经典题有⾷物链，搞同性恋的⾍⼦，帮派结伙等，并查集还有⼀个变型就是从⼀个集合中删除某⼀个元素，我们知道，普通的并查集是不包括删除元素的功能的，⽽删除元素的实现其实也很简单，就是对每个点都建⽴⼀个索引，⼀开始每个点的索引都指向⾃⼰，当⼀个元素被删除掉的时候，先建⽴⼀个新的不属于任何集合的新点，在把被删除掉的点索引到那个新点之上即可。第⼆部分是树状数组，他⽀持在O(nlogn)的复杂度内算出区间内的元素之和，他的思想很是巧妙，就是树状数组总结：假设c[]为树状数组，a[]为原数组，则两者之间存在这么⼀个关系，c[i]代表的意义是从a[i]开始往前2^k个元素的和(k为i化成⼆进制后尾部包含的0的个数)。由位运算的性质可以得到：对于i来说，i&(-i) = 2^k，那么树状数组的基本功能就能明⽩了。树状数组也有⽐较多的题，PKU_1990，PKU_2828，PKU_2155等等。最后我想说⼀下线段树，线段树是⼀个⾮常强⼤的数据结构，他⽀持在O(nlogn)的复杂度内对区间范围内的元素进⾏修改，删除等操作，和并查集，树状数组不同的是，线段树的实现⾮常灵活，⼀道题⼀个样，⼏乎没有什么定式，当然了，最为基本的思想就是每个节点代表⼀个区间，他的左右⼦树分别为左半区间和右半区间，如此这般地递归定义，直到为⼀个点或者包含⼀个单位为⽌。线段树也有⼏个基本模型和经典例题，⾸先我想讲的是线段树的⼀种相对⽽⾔⽐较简单但是⾮常经典的应⽤来引⼊线段树的概念等⼀系列问题，即染⾊问题。以PKU_2777为例，题⽬⼤意是有⼀块长度为L厘⽶的板，每厘⽶可以看成⼀个单位区间，颜⾊的种类由数字表⽰，⼀开始每个区间的颜⾊都是1，⽽现在要对这种树进⾏O次操作，操作有两种，第⼀种是将区间A到B的颜⾊都染成C颜⾊，第⼆种是询问区间A到B之间⼀共有⼏种颜⾊。最简单的想法可能是开个长度为L的数组a[]，⽽a[i]存的就是第i格的颜⾊，但是可⾏吗？我们来看下数据范围，L的范围是⼗万，O的范围也是⼗万，那么算法复杂度就是O(LO)，明显会超时，所以我们选择⽤线段树来帮助我们解决这个问题，其实线段树这个名词并不能很好地阐述它强⼤的功能，我更喜欢他的学术名词——区间树，同其他的树⼀样，他可以在O(logL)的时间内对树进⾏维护操作，这也就意味着他可以在O(logL)的时间内对⼀段区间进⾏⼀系列的操作。正是线段树这种⾼效，让他在RMQ问题，以及求矩形合并⾯积，周长等⼀系列问题中得到了充分的应⽤。这⾥我想讲⼀下RMQ问题(即求区间内最⼤or最下值的问题)，众所周知，RMQ问题有⼀种O(NlogN)的预处理以及O(1)时间求出任意区间内最⼤or最⼩值的离线算法（所谓离线，即不能在求的过程中动态地改变或者插⼊区间的值），即ST(Sparse Table)算法，相⽐之下，线段树并没有效率上的优势，但ST算法有个局限性，就是不⽀持在线操作，⽽线段树则没有这种限制，由此可知，线段树的强⼤。线段树还有⼀个⾼级的应⽤就是对于区间最值信息的维护，相应的经典题有很多，也有⼀定的难度，PKU_2482，PKU_1151(求n个矩形合并后的⾯积)，PKU_1177(求n个矩形合并后的边界周长)等等。最值的维护要抓住的基本思想就是递归地维护每⼀颗⼦树，利⽤⼦树的信息去维护⽗亲。
( 8 ).字符串(包括KMP算法,Trie树,后缀数组)
字符串处理也是ACM中相当⼤的⼀块知识⾯，⽽且也具有相当的实际应⽤⾯，其实对于字符串的知识我⾃⼰接触的也⽐较少，所以只能简单地谈⼀下⼏个最为基础的算法，KMP算法是两串匹配最为基础的线性算法，该算法的核⼼是对于next数组的理解，该数组是对于⼀个串进⾏了预处理得到的，从⽽成功将两串匹配的复杂度降到了线性。但KMP算法只能是两串之间的匹配，如果我们要多串匹配的话该怎么办呢？Trie帮助我们解决了这个难题，Trie其实是⼀颗字母树，树的每个节点都有26个英⽂字母，通过对这些节点的进⾏标记来插⼊⼀个字符串，在插⼊了n个字符串之后，我们就可以同时对这n个字符串之后我们就可以同时对这n个字符串进⾏匹配了，Trie树有⼀个很⼤的缺点，就是他所需要的空间是指数级别的，所有⼀般来说字符串的长度超过15的话我们就应该考虑别的⽅法了。最后是后缀数组，算法的主要精髓在于对于height数组的理解和应⽤，在国家队论⽂中有两篇⽂章是专门介绍后缀数组的，我这⾥就不赘述了。
(9).图论(包括最短路,最⼩⽣成树,强连通分量等知识点)
之所以把图论的内容放在最后讲完全是因为图论的知识点实在是太多了，涉及的⽅⾯也实在是太⼴了，我这⾥挑⼏个我题⽬做得⽐较多的⽅⾯来简单总结⼀下。⾸先就是最短路了，主要分为多源最短路，⽤的算法是⾮常经典的Floyd算法，复杂度为O(n^3)，实现起来相当简单，主要就是DP的思想。还有单源最短路，最原始的⽅法是Bellman-Ford，但该算法使⽤的概率不⾼，因为他有⼀个⾮常好的替代品，就是SPFA，SPFA的实现有点类似⼴搜，代码也⾮常短，对于Bellman-Ford求⼀个图中是否存在负环的问题可以以完全地替代，另外在稀疏图中求最短路的效率甚⾄要⾼于⽤了优先队列优化过的Dijkstra，确实是⼀个实⽤的好东西。当然了，最为著名的Dijkstra算法是绝对不能不提的，该算法是我们求最短路时最常⽤的算法，但是由于他利⽤了贪⼼准则，所以⼀定要注意Dijkstra不能处理有负权边的图，⽽Dijkstra也有⼏个⾮常经典的变型，⼀个是将Dijkstra扩展到⼆维来求次短路，另⼀个是利⽤A*来求次短路，⼤家是否注意到，学到后⾯的时候，不同知识块之间的分界已经越来越不清晰了，因为我们的脑中正在逐步形成⼀张知识⽹，将每⼀个知识点都有机地串联到了⼀起。第⼆个⼤点是最⼩⽣成树，该类问题也有两个⼴为⼈知的算法，适⽤于稠密图的Prim算法和适⽤于稀疏图的Kruscal算法(该算法中要⽤到并查集的算法)，最⼩⽣成树同样有⼀些经典的变型，如次⼩⽣成树，最⼩限制度⽣成树等。再有⼀类⾮常重要的问题就是⼆分匹配问题，该问题涉及的知识点也是相当的多，求⽆权⼆分图的最⼤匹配有最为经典的匈⽛利算法以及求带权的⼆分图的最⼩/⼤匹配的KM算法，⽽由不带权的⼆分图的最⼤匹配数衍⽣出去的知识点有最⼩覆盖问题，最⼩路径覆盖问题等等，这块内容概念性⽐较强，其实说起来，图论最⼤的特点就是概念性强，变型极多，如果不深⼊地理解每⼀次问题及其经典算法，着实⽆法应变。最来就是欧拉回路问题，该类问题⽐较简单，⽆⾮就是两种，⼀个是判断图中是否存在欧拉回路，再⼀个就是求出该欧拉回路中的⼀条，实现起来也很简单，⼀个DFS就可以完成了。还有就是强连通分量，该算法的核⼼就是对⼀个图求强连通分量后缩点，从⽽将⼀个图转化成⼀个有向⽆环图，从⽽⽅便我们进⾏接下去的操作。最后⼀个⼤块就是⽹络流了，该内容我涉及也⽐较少，主要就是⼏个求⽹络流的经典算法，如HLPP，ISAP，EK等等，⽹络流的变型也⾮常地多，需强加练习。
(10).ACM最终回之⽐赛篇
我参加过的正式⽐赛有两场，⼀场是⼤⼆下的上海邀请赛，另⼀场是⼤三上的合肥区域赛，由于⽔平有限，终究还是只拿了两块铜牌，下⾯我想谈⼀下组队的个⼈感受，⾸先是队员的构成，⾄少要有⼀个编码能⼒较强的⼈主要负责敲代码以增加出简单题的速度，另外就是数学基础较强的⼈，由于ACM现在越来越喜欢出数学题，⽽且数学好的往往思路会⽐较开阔，可以为整个团队提供想法，再有⼀个就是算法接触⽐较⼴的⼈，这⼀类的⼈接触的算法⽐较多，切题数也⽐较多，虽然可能没有哪个⽅⾯特别强，但其丰富的做题经验保证了他对于⼀道题的算法嗅觉，可以为整个团队指明⽅向。说到这⾥，我的总结也要结束了，希望⼤家可以从中可以获得帮助。
![[01背包]遗传算法](/uploads/image/0462.jpg)
发布评论