USACO Tips 分析
- 格式：doc
- 大小：73.50 KB
- 文档页数：13
USACO提示题号标题难度系数算法1.1.1-1 Your Ride Is Here 10% 考你会不会编程1.1.1-2 Greedy Gift Givers 30% 字符串处理+统计1.1.2-1 Broken Necklace 50% 比较经典的枚举题1.1.2-2 Prime Palindromes 40% 穷举1.1.3-1 Mixing Milk 30% 贪心1.1.3-2 Barn Repair 40% 动态规划1.1.3-3 What Time Is It 50% 英文表达1.1.4-1 Checker Challenge 60% 深搜1.1.4-2 Number Triangles 20% 简单的动态规划1.1.4-2 Superprime Rib 50% 穷举1.1.2-1: 这道题目需要考虑全面。
可以枚举断开点，然后分别向两边收集。
注意以下几点：1. 断开点两边可能是白珠;2. 注意不要收集重复了(从左边收集了一次，从右边又收集一次);3. 注意全都是白珠的数据。
1.1.2-2: 先列举回文数，再判断是不是素数。
1.1.4-2: 先列举1位的超级素数(2,3,5,7)，然后在此基础上再扩展出所有2位的超级素数，3位的超级素数···1.2.x题号标题难度系数算法1.2.1-1 Shaping Regions 60% 离散统计1.2.1-2 The Castle 55% 遍历1.2.1-3 Ordered Fractions 50% 穷举1.2.1-4 Contact 40% 简单的统计1.2.2-1 Preface Numbering 65% 数字统计1.2.2-2 Runaround Numbers 65% 枚举1.2.2-3 Money Systems 40% 递推1.2.2-4 The Tamworth Two 40% 模拟1.2.2-5 Milking Cows 50% 离散统计1.2.3-1 Overfencing 45% 最短路径1.2.3-2 Bessie Come Home 40% 最短路径1.2.3-3 The Clocks 35% 穷举1.2.3-4 Fractions to Decimals 40% 简单的数学题1.2.4-1 Score Inflation 50% 动态规划1.2.4-2 Mother's Milk 50% 广搜+Hash1.2.4-3 Name That Number 30% 字符串匹配1.2.4-4 Humble Numbers 65% 一类变相递推1.2.5-1 Palindromic Squares 30% 穷举1.2.5-2 Factorials 30% 数学题1.2.5-3 Stringsobits 50% 排列组合算法1.2.5-4 Prime Cryptarithm 50% 硬搜1.2.5-5 Sorting a Three-Valued Sequence 55% 排序题1.2.1-2：先遍历(深搜广搜都可以)把各个房间标号，然后墙都统计以下每一堵墙拆除后最大的房间面积即可。
1.2.2-2：这道题更有效的办法是做一次哈密顿遍历，然后再把答案倒推出来(注意，以样例为例，用这种方法推出的答案是31312，然后你可以把其中的一些数加上5(它的位数))。
1.2.2-4：总共也只有10*10*4*10*10*4=160000种状态(F, C处在不同位置、方向)。
有两种方法，一是用Hash表记录以走过的状态，二是干脆模拟160000步，如果还没有相遇，那就不会相遇了。
1.2.3-3：如果一个按钮使用了4次，那就相当于没用。
枚举量不大。
1.2.3-4：这道题判断循环节的方法是看被除后的余数，如果余数相同，那么就一定循环了。
1.2.5-2：用longint就够了，多记几位，乘一个数后，去掉末尾所有的0，再对10取模就可以了。
1.2.5-5：建立队列q[i, j](表示数字i出现在原本应该是数字j的地方的所有元素的队列)。
然后:1.while(存在q[i, j]与q[j, i]都不空)交换此两队的队首元素;2.while(存在q[i, j]与q[j, k]与q[k, i]都不空)交换此三队的队首元素。
1.题号标题难度系数算法2. 1.3.1-1 Riding the Fences 55% 欧拉路3. 1.3.1-2 Party Lamps 45% 枚举4. 1.3.1-3 Dual Palindromes 40% 穷举5. 1.3.2-1 Agri-Net 40% 最小生成树6. 1.3.2-2 Home on the Range 40% 简单的统计7. 1.3.2-3 Calf Flac 55% 统计8. 1.3.2-4 A Game 55% 博弈(DP)9. 1.3.3-1 Camelot 65% 最短路问题10.1.3.3-2 Friday the Thirteenth 55% 直接统计11.1.3.3-3 Packing Rectangles 65% 枚举+判断12.1.3.3-4 Zero Sum 40% 搜索13.1.3.3-5 Controlling Companies 60% 统计问题14.1.3.4-1 Closed Fences 70% 平面几何(恶心)15.1.3.4-2 Cow Tours 55% 最短路径+枚举16.1.3.4-3 American Heritage 55% 树的遍历17.1.3.4-4 Transformations 35% 穷举+判断18.19.20.21.1.3.1-1: 本题使用的算法正是Usaco网站上的那篇Eulerian Tour文章中的，即用深度遍历法寻找欧拉路:22. proc Circuit(u)23. while exist(u,v)24. Delete (u,v)25. Circuit(v)26. Add u to the queue.27.然后倒着把队列里的点输出即可。
至于题目要求的顺序，只要每次找v时都找号码最小的就可以了。
28.29.1.3.1-2: 实际上有效的的只有6个灯，即1~6号，以后7号=1号，8号=2号...30.31.1.3.2-2: 此题O(n^3)算法就能过。
但是存在一个O(n^2)算法，大家可以思考思考。
32.33.1.3.2-3: 选定一个位置(一个字符或是两个字符之间，依回文词长度的奇偶而定)然后向两边扩展，判断是不是回文词。
34.35.1.3.2-4: 设f[i, j]为还剩下i到j号石头时当前选手采取策略后所能与对方拉开的最大得分差距(可能<0)36. f[i, j] = max(w[i] - f[i + 1, j], w[j] - f[i, j - 1]); w[i]为第i堆的分值37.38.1.3.3-3: 枚举量很小，可以随便翻转矩形，因此此题只用考虑算法正确性(除非你故意找TLE)。
39.注意前5种basic layouts都是很简单的，但最后一种却比较复杂，要很小心得处理各长度关系。
40.41.1.3.3-5: 这道题最怕重复统计。
因此建议用一个数组mark[i, j]标号，mark[i, j]= true表示公司j的直接持有股已经并入公司i的所有持有股。
题号标题难度系数算法1.4.1-1 Beef McNuggets 55% 递推1.4.1-2 Fence Rails 75% 搜索1.4.1-3 Fence Loops 60% 找最小环1.4.1-4 Cryptcowgraphy 75% 搜索(推荐,练剪枝)1.4.1-5 Arithmetic Progressions 70% 枚举(强烈推荐) 1.4.2-1 Drainage Ditches 60% 网络流1.4.2-2 The Perfect Stall 60% 匹配1.4.2-3 Buy Low, Buy Lower 55% 递推1.4.2-4 Job Processing 60% 最优工序安排1.4.2-5 Frame Up 60% 图像处理1.4.3-1 The Primes 70% 搜索1.4.3-2 Longest Prefix 60% 动态规划1.4.3-3 Cowcycles 70% 搜索(恶心)1.4.3-4 Shopping Offers 60% 备忘录式动态规划1.4.3-5 Street Race 55% 图论1.4.4-1 Spinning Wheels 55% 穷举1.4.4-2 Feed Ratios 45% 解方程(搜索) 1.4.4-3 Shuttle Puzzle 60% 构造1.4.4-4 Magic Squares 60% 广搜+Hash1.4.4-5 Pollutant Control 65% 网络流+搜索1.4.1-1: 首先判断所有数的最大公约数(若>0，则无解)。
判断是否可以组合出，最大只用判断到255 * 256 - 255 - 256就可以了(原因见tenshi的论文)。
1.4.1-2: 几点搜索的技巧:1. proc Solve(k)是让程序搜索是否存在可切出k根rail的方案;2. 你可以用2分搜索法调用Solve(k)，也可以让k从0逐步增加;3. 用Solve(k)搜索时，先处理长的rail，再处理短的rail;4. 此题可以切完一根board后切另一根，也可以切完一块rail后切下一块，但前者更容易剪枝，故题推荐使用前者;5. 在此基础上再加一些剪枝。
1.4.1-5: 一道纯粹的枚举题，就看你的算法快不快。
比较好的枚举方法是，任取两个合法的数，然后以第1个数为a，两个数的差为b，再判断一下长度能否达到n。
最后再排一下序(最多只有10000个)。
以下有两个优化方法:1. 可以做一张表格纪录是否一个数可以表示为两个数的平方和;2. 先把所有可表示的数都列出来，放入一个表格，以待枚举。
1.4.3-1: 建议先把符合要求的素数都列出来。
这道题目要注意搜索顺序:1. 注意到第5行和第5列，数字只能填1,3,7,9，所以枚举量小多了，先把它们排好;2. 然后是两条对角线，都已经被填掉2个数，枚举量也变小了;3. 然后是第1行与第1列;4. 剩下的4个格子都可以推算出来，再judge以下是不是符合要求的素数就可以了。
1.4.3-3: 这道题目不用什么剪枝，只要编出来感觉对了，就尽管提交。
因为最大的数据，标程照样过不了，这样的数据不会出的(狂ft!@#$%^&*)。
1.4.4-3: 观察归纳可发现，移动有一定的规律:1. 把空位旁边的W向右移，再把1个B跳到左边;2. 把空位旁边的B向左移，再把2个W跳到右边;3. 把空位旁边的W向右移，再把3个B跳到左边;4. 把空位旁边的B向左移，再把4个W跳到右边;......(执行到第n步)以后的步骤就是跟上面的n步反一下，是完全对称的。
