USACO Tips 分析

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 1.1.4-1 Checker Challenge 1.1.4-2 Number Triangles 1.1.4-2 Superprime Rib

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% 动态规划

50% 英文表达 60% 深搜

20% 简单的动态规划 50% 穷举

1.2.4-2 Mother's Milk 50% 广搜+Hash 1.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% 广搜+Hash 1.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。最后再排一下