|
USACO计算机奥赛是藤校计算机专业的敲门砖，就业前景好。而且USACO竞赛主要考察学生算法和运用两大方面的技能，旨在锻炼学生用计算机编程解决问题的能力。那么USACO不同级别的比赛需要掌握哪些算法?
铜级主要考察两种东西，一种是simulation，第二种就是 brute force，然后另外加上一些observation。Bronze这个级别要求学生掌握基本的bruteforce一些算法，比如说深度优先搜索和广度优先搜索，再加上对于代码有基本的调试能力。
此外，还有孩子比较容易忽视的阅读理解能力。USACO题目有的时候是很长的，看上去整整一页，像在讲一个故事，在这个故事讲完之后，孩子去做的事情，其实是把这个故事抽象成一个带有条件的解决问题
Bronze(铜级)：适合于刚学会编程的学生
考察的算法主要有：穷举算法(Complete Search)、模拟算法(Simu lation)、贪心算法(Greedya lgorithm)、全排列(Permutation)、杂类题目(Ad-hoc)、递归(Recursion);
银级通常有4个比较重要的 topics，第一个是叫two pointer，第二个就是 sweep line，第三个是binary search on answer。第四个是 prefix sum +graph + simple dp。
去年我们发现，以前只会在黄金级里面出现的问题，开始出现在银级考试中，会有一些graph题目以及简单的DP，DP就是动态程序设计。
银级这个级别，会发现算法已经不再是简单的代码了，它需要学生能够写50~100行的代码，甚至可能超过100行，也对于孩子的代码能力和调试代码的能力提出了更高的要求，同时对孩子的建模能力也提出了进一步的要求。
Silver(银级)：面向开始学习基本问题解决算法
考察的算法主要有：排序(Sorting)、二分查找(Binary Search)、递归搜索(Recursion)、图的遍历(DFS&BFS)、FLoodfill算法、前缀和(PrefixSum)、扫描线算法(Line Sweep)。
USACO竞赛黄金级别考的是几个比较大的 Topic，一个是graph theory，第二是 math，第三个是DP，第四个 range query，第五还有 misc，string 以及偏data structure 的内容比如 tree。
但通常来讲是结合前4个topic在考，这4个topic都是非常广阔的领域，比如说graph，虽然是一个单词，但包含着至少十几个小的subtopico DP仅基本的类型就有将近10个，每个类型下面根据不同的问题结构，它展可以展开的问题就更多了。
这些Topics有什么特点呢？就是变化特别多，基本上没有一种方法可以穷举完，或者说光靠漫无目的的刷题是很难的。此外，这两年的Gold竞赛变得特别难。
难到什么程度？最近两年每一场考试，Gold通过人数大概是20多人，个别考试像US Open可能会稍微多一点，那么像12月，一月二月这些Gold考试，一场只有20多个人通过，分到美国50个州的话，相当于是2个州分一个人。
Platinum相对来讲是跟gold的topic基本吻合的，基本上是Gold 有什么东西Platinum就有什么东西，但 Platinum 每一个 topic 里面有更深层次的要求。
比如DP的话，Gold级别把DP公式推出来，一般来讲也就做出题目了，很少需要做很高级的一些优化。在Platinum不做优化程序就会超时，这就要求就需要孩子有更进一步的能力。
普通编程课程，更多是学一些计算机通识问题，比较宽泛。自学是一个很艰难和缓慢的过程，计算机学习中涉及到大量的软硬件问题，同时也会有很多的发展方向，如果是没有经验的人，会将大量时间浪费在这些问题上，又或者在某些细节上迷失，偏移整个学习路线，从而事倍功半，中途而废。所以USACO竞赛备考不建议自学。
在这里也为大家整理了《usaco算法书》，这本是是备考USACO竞赛一站式指南，为USACO比赛的铜牌到银组、金组，再到铂金，提供了一系列有价值的参考资料。0基础开始学习USACO必备书籍。
TEL：13012833750（同微）
扫码添加老师
回复“USACO”即可领取 |
