USACO总结

我的 USACO 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf Congratulations! You have finished all available material. Chapter 1 DONE 2008.12.16 Getting started Chapter 2 DONE 2008.12.24 Bigger Challenges Chapter 3 DONE 2009.01.15 Techniques more subtle Chapter 4 DONE 2009.02.03Advanced algorithms and difficult drills Chapter 5 DONE 2009.02.17 Serious challenges Chapter 6 DONE 2009.02.20 Contest Practice 花了差不多四个月把 USACO做完了，感觉收获很大，它就像一个私人教练能督促你学习一 样，对于一个 oier来说，USACO绝对是一个不可不做的经典 OJ，为了整理一下知识点也 当是一次巩固，便写下了这篇总结，以总结一下自己的疏漏，也希望能帮助到别人。 --湖南南县一中 czz 一、枚举 枚举是我们用的比较多的一种算法，编程简单是它的优点，而时间效率低则是它的致命 缺点，不过很多 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目通过合理的优化比如减小枚举量等来优化算法。 The Clocks是第一道需要优化的枚举题，首先由于这题有 9个时钟，而且每个的移动次 数也不清楚，似乎无从开始，不过经过研究发现对于一个时钟如果移动四次就会便相当于没 有移动，因此我们只需要枚举每个钟的四种状态共 9^4共 6561种状态，这样就不会超时了， 不过如果进一步研究这个题目发现移动 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 之间是有约束的，打个比方，A时钟由三种移动 方案确定，如果其中的两种方案的次数已经知道，那么第三种方案也就会确定，因此我们只 要枚举前三个方案的次数其他的便可以递推出来，状态只有 4^3个，效率无疑大大提高。 Arithmetic Progressions这题由于题目要求按 b升序排列，所以我们习惯性得 把 b放在外循环而 a放在内循环，这样做加上剪枝后也会超时，由于剪枝时按 a 剪枝时力度无疑会更大，因此我们可以把 a提到外循环，相应的加一个快排，因 此我们得出一个结论：把剪枝有利的尽量放在外循环。 素数的题目也有几个，枚举就行了，不过注意要先生成一定范围内的素数， 然后再枚举判断，不过有一种随机化的素数判断可以在 klogn内判断，可以参考 周咏基的论文《论随机化原理与设计》。 Party Lamp与 The Clocks有异曲同工之妙，同样我们可以判断出一个按钮如 果按了两次就没有意义了，n值是有小于 4时才会限制按键次数否则不予考虑。 不过这样枚举还是会超时，如果再次分析可以发现每六个灯一个循环即灯的最后 状态是循环的，因此只要枚举 6个灯的状态即可，算法十分优秀了。 Controling Company当时看到这道题时，看到题解是才发现N的范围并不大 ， 完全可以用迭代枚举来求解，即不断枚举更新公司之间的关系，直到无法更新。 可以看出枚举对付一些看起来很复杂的题目很有一套。 Contact也是一道难题，为了判重，我们不得不借助于 Hash表，把一个字符 串看出一个二进制数，不过为了区分 11和 0011这样的相同大小的字符串，我们 可以先处理长度为 1的，再处理长度为 2的……知道处理完全。 Camelot应该是 USACO里最难的一道枚举题目，首先我们可以用广搜得到 棋盘之间的最短路径，然后先枚举汇合点，再枚举汇聚点，最后枚举接国王的骑 士，不过这样超时十分严重，继续分析，由于国王走路很慢，因此肯定要让他尽 量少走路，我们可以进一步缩小汇聚点的范围，即在国王两部以内，这样就 AC 了 由此可以看出枚举的一般思路： 1、估计枚举量，看是否可行。 2、确定枚举对象，注意把容易剪枝的放在外面。 3、进一步分析看可否减小枚举量(注意挖掘枚举对象之间的约束关系)。 二、动态规划 USACO离的动态规划题是比较多的，主要分为几类： 1、背包问题 Subset sums是一道典型的 01背包问题模型，由于它要求求出均等划分 的个数，对于奇数的总和特判无解，因此先用动态规划求出装出总重量 的一半，由于集合的对称性，即 N=3时，{1,2}和{3}是同一中方案，因 此将结果除以 2即是答案。 Money System，Score Inflation则是完全背包模型，由于物体个数无限， 所以我们在实现时只要将一维数组的实现循环倒过来即可。 Stamps是背包问题的变种，不过颇为简单，设 can[i]表示 i容量能否装出 ， 则 can[i]=can[i] or can[i-w[k]]。 Shopping Offers也是 dp，不过从一维到了五维，而且实现时要把物体的 编号映射为 1..5，方便处理。不过这题有个相当有趣的图论算法：构图， 每种购买商品的组合是一个顶点，每种打折方式是一条边，然后 SPFA求解。 Beef Mcnuggets是一道有难度的 dp，由于题目的范围巨大，直接 dp是肯 定MLE+TLE，不过我们进行一下数学分析就会发现，题目中的数据是 吓人的，如果数据中任意两个数不互质，那么无法装出来的数一定小于 最大的两个数的最小公倍数。此时便可以进行 dp了，此题体现了数学分 析在信息学奥赛中的作用。 Milk Measureing 开始做的时候用的 ID迭代加宽搜索+DP,结果由于数据 暴弱，竟然过了，但是我在网上找了很久也没有找到纯 DP的题解，不 知那位大牛可以指教一下。 Raucous Rocker也是一个类背包问题，我们设 f[i,j]表示前 i张光盘放前 j 首歌时最多放的个数，那么决策就是第 i张光碟放多少，得出方程： F[i,j]=Max(f[i-1,k]+g[k+1,j]); 其中 g[i,k]表示将第 i到第 k首歌放在一个 光盘中最多放的个数，对于 g数组我们可以将数组排序后从左到右扫描 即可（可以增设 Order[i]表示现在第 i 个数原来的位置）。复杂度为 O(n^2*m)，完美解决了这个问题。 2、与矩形边长有关问题 主要有三个问题：Home on the rage Big barn A rectangular Barn 其中前两个问题较为简单，用 f[i,j]表示以第 i行第 j列为右下角时最大正 方形的边长，则 f[i,j]=min(f[i-1,j-1],f[i-1,j],f[I,j-1])+1; 即往上面，左边，左上三个方向扩展的最大长度最小值为现在的最大扩 展边长。第三个题目由于是求矩形面积，所以不能简单的套用以前的方 程，这里我们设三个数组，L,R,H分别表示向左，向右，向上扩展的最 大长度，则： H[i,j]=H[i-1,j]+1; L[i,j]=Min(L[i-1,j],J-最靠近的坏格子（左边的）)； R[i,j]=Min(R[i-1,j],最靠近的坏格子（右边的）)； 由于会超空间，所以我们可以用数组迭代计算即可。 具体这个方程是怎么来的可以参考王之坤的论文。 3、求解第 N个状态问题 这种类型以 Two Five和 Stringsobits为代表，这类题目共同的特点是给定 一系列 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf 构造出一系列对象，要你求第 N个状态，而共同的求法就是 利用动态规划求出每一位的总数，然后一位一位求解。 Stringsobits由于题目范围巨大，所以模拟是肯定 TLE，考虑动态规划： 设 F[N,L]表示 N个 0和 1组成的 1个数小于等于 L的数的个数，则 F[N,L]=F[N-1,L-1]+F[N-1,L] //分别在前面加一个 0和 1 {上面的方程和组合数的方程及其相似，可以结合理解} 边界条件 F[I,0]=1; F[0,I]=1;（0<=I<=N）;（注意利用小数据推边界条件 ） 求出来以后我们一位一位处理，假设 A[I]表示序列的第 I位， 对于每 I为，如果 F[I-1,L] 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 两次 2,3这个序列， 为了解决这个问题，我们可以限定方程中 K的范围，将方程改为： Sum[I]= ∑Sum[K]（I前面那个与A[I]相同的数J-I则将 F[I,J]赋为 J-I，因为这是最大长度。 其实如果我们将相邻的两个数做差，那么问题就转化为寻找最大重复序 列，此时我们可以用扩展 KMP做到 O(nlogn)或后缀树做到 O(N); Postal Vans一题个人感觉不太像动态规划反而像递推，即把路径分为 8 种，根据路径之间的连接关系来一步一步叠加，具体可以看 ruiqi的题解 ， 很好理解。 建立动态规划模型一般步骤： 1、确定其可行性。包括空间问题，无后效性等。 2、划分状态。 3、确定方程，可以套用经典的方程，注意要让方程包含的决策数少。 4、动态规划还有一个难点就是推边界条件，这一步可以利用既要直接利 用边界条件算的，有可以自己手算出来的小范围数据进行推导。 三、搜索 搜索的实质是枚举，不过搜索可以用来解决枚举对象不确定即随输入数据变 化而变化的一类问题，一般来说，编出搜索程序都不是问题，真正的挑战是 剪枝与优化，这里主要总结一下我的优化方法。 Checker Challenger是第一道不优化无法过的搜索题，朴素的搜索最后一个 点 1.6秒，所以一定要优化，有两种方法：一是用位运算加速，当时我选了 这种方法（m67牛的教程不错）。另外便是利用对称性：考虑对称如果 n是 偶数，第一行枚举前一半的数，这样每搜索出一种方案后，沿中线对称过来 又是一种方案，并且因为第一行的数小于一半，对称过来的方案总大于原方 案（即在搜索树中后被搜索到），不会出现重复的情况。如果 n是奇数，先 在中间行和中间列放子，并且位置都不超过半数(<=n div 2)，且中间行>中 间列，这样每搜索出一种方案，把它对称旋转后一共有 8种方案，因为中间 行和中间列的的不出现重复，所以 8种方案不重复。这样只需枚举原来的 1/8 就可以了。这样就完全可以过了。{注意放在正中间位置的时候} Overfencing一题可以用广搜解决，对两个出口为源点分别进行一次广搜， 就可以得到最短路径中的最长路径了。 Magic Squares也是一道广搜，不过过程中必须要用 hash表判重，8维数组 肯定会超空间，首先，如果前 7个数已经确定，那么第 8个数随之确定，因 此将 8为数组改为 7维，不过这样还是不行，想一下，前 7个数实际上就是 8的全排列的前 7位而已，所以我们可以定义一个七维的动态数组，然后生 成 8的全排列进行开域即可，空间需求只有 8!*7了，完全满足要求。 Riding The Fences实际上是求一条欧拉路，其方法是从有解的点出发，每次 找出一个标号最小的点，然后以这个点递归，直到递归完成，那么这个点放 入答案中。 Fence Rails一道较难的搜索题，由于题目深度不知道，用深度搜索很容易超 时，广搜空间又不够，折中后就是一中新的搜索方法：DFS-ID。思想就是 先搜索 1块木料是否可以割出来，然后搜索 2块木料是否可以割出来…… 每次不断加大搜索深度，直到无法搜索出方案来。由于前一次搜索量与下一 次相比量很小，所以重复搜索不会大量影响时间效率，不过还要优化： 将木料排序，每次验证 K块木料能否割出来时选择最短的 K块验证。然后 由于木料长度存在相同的，所以为了排除重复搜索，可以规定如果存在两块 木料 I,I+1,且Rail[I]=Rail[I+1],那么搜索时 I对应的木板<=I+1对应的木板（实 质就是优化搜索顺序，认真体会）。最后如果一块木板切了以后连最小的木 料都切不出来了，那么它就是浪费，如果 现在的浪费>木板总数-要割的木 料总数，那么一定无解。加了上述剪枝后就过了。 Cryptcowgraphy这题要加大量的优化，先确定搜索对象：搜索每一个C，O，W, 将他们去掉，直到得到解。剪枝：每个 C，O，W之间的字符必须存在于目 标中，不满足就剪枝。然后为了消除重复判断一个字符串，我们可以利用 Elfhash判重（在我看来，Elfhash实质就是对一个字符串乱搞）。 The Primes这题差点把我搞疯了，首先生成所有的素数，然后枚举将它们放 进去：结果连样例都超时。这题将搜索顺序的作用发挥到了极致，一个原则 ： 现在的选择对以后的选择造成的约束越大越好，网上的搜索顺序有很多，大 家可以参考，这里就不说了。不过这样以后还是超时，此时可以加优化，比 如放的过程中第一为与第二为分别为 X,Y的素数是否存在等等，当时我加 了以后还是超在了第 9个点，无赖之中寻寻找找，结果发现了原因：此题为 了减少枚举量，要用多个数据结构储存，比如放置一个素数，如果已知它第 一位为 2，第二位为 5，那么直接用储存了第一位为 2，第二位为 5的数据 结构来枚举，减小了枚举量。有了这个优化，即使不用上面那个存在性的优 化也可以 0.2秒过了。 Snail Trail不知怎么估计它的时间复杂度了，裸搜都可以 0.01秒过了。 All Latin Squares裸搜可以过 5个点，连 N=6都无法 TLE，优化： 由于第一行已经确定，如果我们强制第一列递增得出的解数为 Ans，那么最 后的答案就是Ans*(N-1)!，加了这个优化以后 6就可以瞬时出解了，不过N=7 还是超时，这时可以用Maigo的置换剪枝（我不太理解，就不分析了）。 Betsy's Tour又是一道难题，关于它的剪枝网上多的有卖的，主要是利用局 部判断的可行性剪枝，不过即使这样还是无法得出解，只好用 Hash： 在走的时候肯定会出现这种情况：走的两条不同的路，却走了完全相同的格 子，最后还聚在同一个点上，那么此时的解肯定和以前一样，为了避免重复 搜索，我们可以用 Hash[X,Y,M]表示在第 X行，Y列，走的格子集合为 M 时答案数，由于最多只有 49个格子，每个格子只有两种状态，所以可以用 Int64储存，同时为了避免超空间，可以用M对一个大素数取摸，相应的用 链表处理冲突，这样我就 0.6秒过了。 搜索优化的总结： 1、搜索无外乎两个主要的剪枝：可行性剪枝和最优化剪枝。 2、搜索顺序很重要，通常可以通过自己规定一系列规则避免重复搜索。 3、要配合好的数据结构，避免重复枚举。 4、Hash表的运用很重要，注意体会。 四、图论 图论是数学的一个分支，有很多有趣的算法值得研究，USACO里也有很多 经典的图论题，这太就一些典型的题目总结一下。 Cow Tours、Bessie Come Home和 Sweet Butter是三道很明显的最短路，对 于最短路我们一般有三种求法：Dijstra，Floyed和 SPFA，前两种流传得很 广，不过个人认为 SPFA才是最快的，SPFA要用队列实现，关于它的基本 实现就不说了，它的优化：首先用邻接表代替邻接矩阵，如果是个很稀疏的 图，可以使用前向星，然后再算法执行过程中，假设一个元素入队后发现它 比队首元素更优就可以将它与队首元素交换不会影响结果，这样程序只多了 一行，不过效率却大大改善了。Floyed程序很短，对于数据很小的题目可以 使用它，而 Dijstra+Heap优化以后也很快，不过实现复杂，一般不用。 Agri-Net求出最小生成树，有两种算法：Prim算法和 Kruskal算法，个人比 较喜欢用 Kruskal，特别用并查集优化后可以得到很好的时间效率，介绍一 下 Kruskal算法：把所有的边按从小到大排序，然后一条一条加入生成树， 如果待加入的边不会构成回路就加入（构成回路的条件就是边的两个点都在 同一个集合里），因此这里可以用并查集判断。 Fence Loops此题实际上是求最小环，有两种求法，一种是枚举删除每一条 边，然后对两个端点求最短路，复杂度约是 O(E*N^2),对于稀疏图很有效果 。 另一种是在 Floyed的过程中顺便求出来，这里给出代码，仔细体会： For K:=1 To N DO Begin For I:=1 To K-1 DO For J:=1 To I-1 DOAns:=Min(Ans,A[K,I]+A[K,J]+F[I,J]; For I:=1 To N DO For J:=1 To N DO F[I,J]:=Min(F[I,J],F[I,K]+F[K,J]); End. 为什么上述代码可以求出最小环？因为求Ans时 I和 J还没有以K为中介点 求最短路，所以可以求出最小环。 Drainage Ditches一道网络流题目，一般来说网络流我用的是标号加增广路 法（不过听说 Dinic既快有好写），这题没什么好说的，只要在出现同一条 路线时累加一下最大流量就可以了。 Pollutant Control和 Telecowmunication都是求最小割，Pollution那一题是求 最小边集割，由于要求去掉的边最少，而且编号要最小，所以我们可以将所 有边按最大流量从大到小排序，流量相同的则按编号从小到大排序，然后从 左到右枚举删除每一条边，如果删除后减少的流量刚好等于边的流量则表示 这条边是必须经过的边，删除它，然后重复上述过程直到最大流为 0 即可。 Telecowmunication一题有点不同，它是求最小节点割，不过我们可以使用化 归的思想，将一个点拆成两个点加一条边，然后每次枚举删除每个点所对应 的边套用上一题的解法即可。不过这一题还有一个诡异的解法（不知道正确 性如何，不过可以过 USACO的数据）：每次枚举删除一个点，在求最大流 的过程中将每个点的容量看成 1，每次用了以后就不用了，也就是求最大流 时记录增广路中的节点使得下一条增广路不重复走同一个节点不就可以了。 伪代码： var v:array[0..maxn] of boolean; function getmaxflow:longint; begin fillchar(v,sizeof(v),0); repeat SPFA; //用类 SPFA算法求出增广路，注意在求时不用 v值为 true 的节点； if dist[goal]=0 then break else inc(getmaxflow,dist[goal]); DEL; //递推求出增广路的节点，进行数组修改，同时将路径上的点 v值赋值为 true until false; end; {再次声明：上面的算法正确性还未得到证明} Street Race第一问好求，枚举删除每一个点，然后用 Floodfill算法看还能否 从 1到达 N，如果不能则它是不可避免的点集。第二问肯定是第一问的子集 ， 枚举第一问中的点，由于这个点是左边的终点，而题目已经说明终点不能到 达任何路口，因此我们可以对终点进行一次 Floodfill，如果它到达了左边的 点则它是不合法的一个点。 The Perfect Stall实际上是求最大匹配，可以用网络流求，即构造一个图：一 个源点，从源点到每个奶牛一条边，容量为 1，奶牛到对应的牛棚一条边， 容量为 1，然后设置一个汇点，从牛棚到汇点一条边，容量为 1，然后求最 大流即可，不过用专门的匈牙利算法可以得到更快的时间效率。 Network of Schools第一问就是先求出说有的联通分量，然后把每个联通分 量都收缩成一个点，其中入度为 0的点就是必须发放的点。第二问我们假设 增加一个点，所有出度为 0的点跟它连一条边，所有入读为 0的被它连一条 边，那么这个网络就联通了，撤掉这个点后情况也不会变，因此第二位 Ans=Max(入度为 0的点，出度为 0的点)。 五、几何 在计算机奥赛中，计算几何是个相对独立的分支，各种各样烦杂的情况是它 的最大的特点，这里选取几个典型讲解一下。 Packing Rectangles第一道几何体，不过这题题目已经把所有的情况都给你分 析清楚了，你所做的就是按要求模拟即可。 Closed Fences一道有难度的几何题，第一问就是判断是否有线段相交，写个 用叉积判断相交的函数即可解决，第二问就有难度了，用二分的思想判断一 条线段是否能看到： 取一条线段的端点 A,B,以及它的中电 C.人的位置是 O 不能看到的条件: 1.AO和 BO被同一条边遮挡 2.AO,BO,CO均被遮挡 3.AB的长度接近为 0(看成一个质点) 能被看到的条件: 4.除了端点能有一点未被遮挡 5.当上述两个条件未达到时用二分的方法,将此线段割为两块,重复上述过程. 因此这题可以分治解决。 Electric Fences很经典的一个随机算法，由于对解的精度要求不高，所以我 们先任取一个点，然后判断 100之内有没有比它优秀的点，如果有就把它变 成那个点，重复上述过程，如果没有就不断缩小精度，知道在 0.1的范围内 没有更优秀的点，此时的点就是答案。此题中求点与线的距离很麻烦 Fencing the Cows一个裸凸包算法，先取最左边（横坐标相同就取最下面）， 然后把其他的点按叉积排序，然后用扫描法求凸包即可。 六、其他 Milking Cows一题要用离散化，先把农民们的时间从小到大排序，然后在统 计即可，不过离散化的思想要掌握。 Mixing Milk和 Barn Repair都是贪心的经典题，贪心是一种重要的思维，想 出贪心策略一般都不难，不过证明它就是一个很大的挑战，一般要使用反证 法。前一题就是一个典型的部分背包问题，贪心策略为：每次选取最便宜的 拿，知道那够了，可以证明这就是最小费用。而第二题有点难度，假设我们 先用一块木板把所有的都拦住，那么长度就是牛棚的长度，如果我们可以该 两个木板呢，我们可以找出最长的一段空段，把它锯掉就可以了，因此这个 问题可以用贪心解决。 Job Processing是个很值得一题的贪心，第一问可以直接用贪心求解，问题 是第二位，为了平衡，我们把 A中最先加工的放在 B中最后加工的中，这 样就可以使得时间平衡了。 Ordered Fractions一题可以先生成所有的分数然后再排序，不过有一种很强 的方法：递归解决（不过我不清楚原因），代码： Procedure Print(x1,y1,x2,y2:Longint); Begin If (y1+y2<=N) Then Begin Print(x1,y1,x1+x2,y1+y2); Writeln(x1+x2,’/’,y1+y2); Print(x1+x2,y1+y2,x2,y2); End. 上述程序应用了不等式 a/b