USACO,全称为 United States of America Computing Olympiad (美国计算机奥林匹克竞赛)。
USACO 是国际奥林匹克信息学竞赛(IOI) 美国国家队选手的预选比赛。由于 USACO 面向全球信息学爱好者开放,逐渐成为全球信息学竞赛爱好者参与的一项重要赛事。
由于 USACO 的设立目的是选拔美国国家队,所以题目形式和中国选择国家队的比赛很接近。但是赛制和比赛方式和国内比赛有些不同。
USACO 不是一场比赛。而是从第一年的 12 月开始,持续到第二年的三月。每月一场,一共四场。其中最后一场是“公开赛”,题目稍微难一点。除了最后一场的“公开赛”以外,每场比赛三道题,四小时。最后一场“公开赛”题目要难一些,比赛时间是五个小时。
USACO 的每一场比赛的比赛时间都是连续四天。参赛选手需要在这四天当中任选连续的四个小时(公开赛是五个小时)进行比赛。比赛通常安排在美国时间的周五到周一,这样全球任何一个地方都可以在周末参赛。也就是每一个选手的参赛时间是不同的,靠诚信约束选手不在比赛期间进行交流。
USACO 有一个“级别”的概念。分青铜、白银、黄金和白金四档。每个赛季的每一场比赛,这四个级别都会同时进行。新注册的选手必须从青铜级别打起,达到一定的分数才能在下一场比赛晋级到上一个级别。
晋级有两种情况:一种是满分晋级。如果选手在赛时拿到满分。可以在同一场比赛的时间段内再次参与高一个级别的比赛。也就是说,理论上可以在一场比赛的四天里面从青铜打到白金。另一种晋级的方式就是常规晋级,比赛结束后组织者根据全部选手的成绩划定分数线,分数线上的选手在下一场比赛的时候晋级到更高级别。
晋级分数线的划定不是固定的,是从这场比赛参赛选手的成绩根据比例反推的分数线。一般来说,在一场比赛的三道题当中,要拿到两道半才能晋级。
首先,美国大学的录取官,看重的是学生是否与众不同,是否愿意为自己感兴趣的事情不断地追求。竞赛成绩要放到证明自己“与众不同”、“为兴趣不断追求”的背景中体现,而不能孤立的成为申请学校的要素。
所以说,并不是 USACO 固定的哪个级别就一定能申请到什么样的学校。但是不同级别对应不同的晋级人数,很容易体现出“与众不同”。比如每年打入白金级的,只有几千人(全球,不限年龄)。这个难度是相当大的,所以如果能进入这个级别,基本上可以作为申请美国大学的拳头项目,可以让名校录取官眼前一亮的重要成就。由于参与编程比赛的女同学非常少,所以女生打到黄金一级,就已经比男生打入白金更稀缺,更有优势了。
当然,只有很少数同学能在竞赛中获得如此亮眼的成绩。但是,如果你真正热爱编程,可以把打竞赛作为“为兴趣不断追求”的大的叙事中的一个环节来体现。和科技项目、服务社会结合在一起,呈现出一个“为兴趣不断追求”,“用自己的专长服务社会”的立体的、阳光的形象。也能在众多申请书中脱颖而出,被录取官选中。
USACO 是对全球开放的,不限年龄,不收取费用。参赛者只需要在官网(http://usaco.org/)注册一个账户,就可以在比赛季参与。
12月赛程:12月15-12月18日; 1月赛程:1月26-1月29日; 2月赛程:2月16日-2月19日; 3月美国公开赛:3月15-3月18日
赛程时间内任选连续4小时时间参赛即可
注意:还未报名注册报名的考生抓紧时间啦! USACO官网注册报名网址:http://www.usaco.org
注册账号
登录USACO官网:http://www.usaco.org/点击Register for New Account按钮,注册新账户
填写信息并激活账号
Complete information and activate 注册后按照下图指引填写信息
注册结束后
在绑定的邮件中查收自己的账号和默认密码。并登陆官网 (24小时内首次登陆方可激活,登录后可修改密码),并点击“Login”
-
考试地点:线上比赛,个人参赛,通过登录USACO官网,在线提交代码
-
比赛语言:支持Java、Python、Pascal、C和C++,考生在考试时选择任意语言参加即可!
-
参赛费用:比赛参与是完全免费的
-
评分要求:代码运行正确性、算法时间效率、内存使用效率
为确保学术诚信,官方对本赛季的竞赛结构和规则作出了以下重要调整和澄清:
-
官方明确规定,在竞赛期间禁止使用生成式人工智能,同时美国学生不得使用VPN隐藏自己的IP地址。
-
其次,参与铂金级别竞赛的美国学生需在指定的时间内开始竞赛,即从周六美东时间中午12:00起,铂金级别的题目将于此时首次发布。
-
在这个时间段内参赛并获得认证分数的学生,在最终选拔决赛选手时,其分数将比非认证分数具有更大的影响力。值得注意的是,铂金级别的题目仅在指定时间窗口内对美国的考生开放,在时间窗口结束后的4到5小时内对所有其他学生开放。其它时间进行竞赛的分数,是非认证成绩。
-
目前,特殊的时间安排仅适用于铂金级别竞赛,其他级别竞赛不受影响。希望晋级决赛选手参加集训营的学生,应力争取得铂金级别认证分数。因为时间的缘故,只有三个而非四个认证分数的学生,我们也有可能考虑。赛季中期由金级别升至铂金级别的学生,若认证分数不足三个,同样有机会被考虑为决赛选手,认证分数越多越有利。
USACO每场比赛3-5个小时。可以在比赛规定时间开始后登陆USACO账号,从在线打开试题后开始计时。一套试题中有3-4道题,选手需要在时间结束前通过网络将写好的程序提交。
程序提交后官网会给出用test case检测程序的结果,并根据结果给出这一题的得分。可以使用C++、Java、Python、Pascal和C中的任意一种编程。比赛对于程序的大小,运行需要的内存以及运行的时间都有一些具体规定。
每次比赛,实力强的选手可以连续升级。在比赛窗口开放的4天时间内,选手可以选择任意时间开始比赛。
开始比赛3-5小时内,如果拿到了高分(接近满分或满分),系统会提示直接晋级,可以在这4天内继续挑战下一级,只要实力足够,一场考试可以升到满级铂金级。
USACO竞赛官网为美国有名的在线题库,更是美国中学生的官方赛事网站。专门为信息学竞赛选手准备,但必须在注册后才能进入题库,新注册的参赛选手需要从最低组别开始打起。
USACO竞赛一共有4个级别,青铜、白银、黄金、铂金四个级别,一进入USACO注册账号即为铜级,一级一级的比赛刷高自己的等级,如果你最终能够获得黄金或者铂金级别的奖项,绝对是提高竞争力的大杀器。
参赛资格:一进入USACO注册账号即为铜级。
难度等级:铜级考试只要基本编程常识,会至少一种编程语言。铜级的编程限制时间还是够用的,大部分初次参赛的选手都能在次考试中晋级白银级。
考核知识点:分支和循环,嵌套可变循环,列表、函数、二维列表,基础数组, 多重循环,复合判断、枚举算法
参赛资格:通过青铜级比赛的选手。
难度等级:需要基本的问题解决能力和简单算法(例如:贪心算法,递归搜索等),还需了解基础数据结构。从白银级开始,选手需要寻找更好的算法才能使程序在规定时间内跑完。
考核知识点:基本数据结构、贪心、递归、递推等基本算法
参赛资格:通过白银级比赛的选手。
难度等级:需要有一定的算法基础,理解一些抽象的方法(例:最短路径,动态规划),并且对数据结构有比较深的了解。
考核知识点:堆、栈、树、链表等高级数据结构,动态规划等高级算法,算法时间和空间复杂度
参赛资格:通过黄金级比赛的选手。
难度等级:需要有很高的编程基础,对算法有深入的了解。部分比赛问题最后的优化方案,可能不只一个,得出的答案也不只一个。
考核知识点:各类高级的数据结构,尤其是需要算法的时间和空间复杂度,总分1000分。每道题333.3分。
题单使用说明
Open Judge 是一个公开的刷题网站。其中 noi 小组里面整理了大量的好题,可以用来刷题练习。
地址是:http://noi.openjudge.cn/ 注册好账户之后,就可以做练习了。
练习方式
难度系数是这样判断的:难度 1 表示练习到平均 10 分钟就能 AC 就可以不继续练了; 难度 2 表示 20 分钟就能 AC,这种题就可以不练了。 依此类推。
没有拿到过提高组 100 分的同学,难度 4 以及以上的题目即便有能在 40 分钟内 AC 的,也值得练习。
比较简单的题目,如果实在没时间把代码写出来,可以写出文字思路。不要光想想,一定要用文字写下来,这样有利于认真思考每一个细节。
第一部分,简单题。
题目不难,希望能做到每题 15 分钟搞定。
OJ单元 |
题号 |
题目 |
难度 |
注释 |
1.5 |
16 |
买房子 |
2 |
利率问题 |
1.5 |
19 |
救援 |
2 |
麻烦的分支循环 |
1.5 |
21 |
角谷猜想 |
2 |
模拟 |
1.5 |
23 |
药房管理 |
2 |
北医的计算机课期末考题 |
1.5 |
24 |
正常血压 |
2 |
北医的计算机课期末考题 |
1.5 |
25 |
求特殊自然数 |
2 |
|
1.5 |
26 |
统计满足条件的四位数个数 |
2 |
|
1.5 |
27 |
级数求和 |
2 |
NOIP2002 普及组第一题 |
1.5 |
28 |
分离整数的各个数位 |
1 |
|
1.5 |
30 |
含 k 个 3 的数 |
1 |
|
1.5 |
31 |
开关灯 |
2 |
|
1.5 |
34 |
求阶乘的和 |
1 |
|
1.5 |
36 |
计算多项式的值 |
1 |
|
1.5 |
39 |
与 7 无关的数 |
2 |
|
1.5 |
40 |
数 1 的个数 |
2 |
拆位 |
1.5 |
41 |
数字统计 |
2 |
拆位 |
1.5 |
42 |
画矩形 |
1 |
|
1.5 |
43 |
质因数分解 |
1 |
NOIP2012 普及组第一题 |
1.5 |
44 |
第 n 小的质数 |
2 |
|
1.5 |
45 |
金币 |
2 |
模拟 |
1.8 |
1 |
矩阵交换行 |
2 |
|
1.8 |
3 |
计算矩阵边缘元素之和 |
2 |
|
1.8 |
4 |
错误探测 |
2 |
|
1.8 |
5 |
计算鞍点 |
2 |
|
1.8 |
6 |
图像相似度 |
2 |
|
1.8 |
7 |
矩阵归零消减序列和 |
2 |
|
1.8 |
9 |
矩阵乘法 |
2 |
|
1.8 |
12 |
变幻的矩阵 |
2 |
|
1.8 |
13 |
图像模糊处理 |
2 |
|
1.8 |
14 |
扫雷游戏地雷数计算 |
2 |
|
1.8 |
16 |
矩阵剪刀石头布 |
2 |
|
第二部分,字符串练习
学过字符串函数之后,可以做这部分练习。
OJ单元 |
题号 |
题目 |
难度 |
注释 |
1.6 |
9 |
向量点积计算 |
1 |
数学概念 |
1.6 |
14 |
求 100000 以内 n 的阶乘 |
2 |
麻烦,练习调试能力。 |
1.6 |
15 |
阶乘和 |
2 |
麻烦,练习调试能力。 |
1.7 |
4 |
石头剪子布 |
1 |
字符串练习 |
1.7 |
8 |
字符替换 |
1 |
理解字符串存储概念。 |
1.7 |
10 |
简单密码 |
1 |
字符串和数组的结合应用 |
1.7 |
15 |
整理药名 |
1 |
|
1.7 |
16 |
忽略大小写的字符串比较 |
1 |
|
1.7 |
19 |
字符串移位包含问题 |
2 |
|
1.7 |
20 |
删除单词后缀 |
2 |
|
1.7 |
21 |
字符串替换 |
2 |
|
1.7 |
23 |
过滤多余的空格 |
2 |
|
1.7 |
24 |
单词的长度 |
2 |
|
1.7 |
25 |
最长最短单词 |
2 |
|
1.7 |
26 |
字符串的最大跨距 |
3 |
|
第三部分,不含递归的综合应用
这部分练习,适合已经学习过一年以上的同学。 训练目标是搞定语法熟练度,从写代码时思考语法,到思考算法,代码自然从手中敲出。 通俗点讲,就是要做到写作文的时候,不用再考虑字、词、句。而是把注意力放到谋篇布局和整体结构的把握上。
有些题目是好想不好调的。一定要坚持调试,找到所有的坑。
OJ单元 |
题号 |
题目 |
难度 |
注释 |
1.13 |
1 |
数制转换 |
2 |
不同进制之间的转换 |
1.13 |
2 |
不吉利日期 |
2 |
日期是星期几 |
1.13 |
3 |
垂直直方图 |
2 |
|
1.13 |
5 |
素数回文数个数 |
2 |
拆位、素数判断。 |
1.13 |
6 |
循环数 |
2 |
拆位 |
1.13 |
8 |
特殊日历计算 |
2 |
特麻烦的题目 |
1.13 |
12 |
分数求和 |
2 |
涉及通分 |
1.13 |
13 |
人民币支付 |
2 |
贪心 |
1.13 |
14 |
求满足条件的三位数 |
2 |
拆位 |
1.13 |
15 |
求序列中的众数 |
3 |
字符串拆数 |
1.13 |
16 |
最长单词2 |
2 |
|
1.13 |
18 |
Tomorrow never knows? |
2 |
日期问题 |
1.13 |
19 |
啤酒厂选址 |
3 |
|
1.13 |
20 |
话题焦点人物 |
3 |
|
1.13 |
21 |
最大质因子序列 |
3 |
质数 |
1.13 |
22 |
因子分解 |
2 |
|
1.13 |
25 |
计算两个日期之间的天数 |
2 |
|
1.13 |
26 |
n-gram 串频统计 |
2 |
可以枚举,也可以哈希。 |
1.13 |
27 |
除以13 |
3 |
二分求大整数除法的商和余数。 |
1.13 |
28 |
出现次数超过一半的数 |
2 |
桶排 |
1.13 |
29 |
统计字符数 |
2 |
桶排 |
1.13 |
30 |
1的个数 |
2 |
求十进制数的二进制表示下 1 的个数 |
1.13 |
31 |
字符串中最长的连续出现的字符 |
2 |
|
1.13 |
32 |
日历问题 |
2 |
|
第四部分,冲击一等
这部分内容,涵盖比较复杂的分支循环,数学杂题,还有递归搜索。如果大部分题目能在 40 分钟内自行调试完毕,然后一次提交 AC,普及组一等奖肯定到手了。
注意,到这个阶段,要提高一次 AC 的比例了。正式比赛是只能提交一次的。
OJ单元 |
题号 |
题目 |
难度 |
注释 |
1.8 |
17 |
最好的草 |
3 |
染色问题。USACO 2008 公开赛铜。 |
1.8 |
18 |
肿瘤面积 |
4 |
类似于染色问题。北医期末考试。 |
1.8 |
19 |
肿瘤检测 |
4 |
北医期末考试 |
1.8 |
20 |
反反复复 |
3 |
麻烦的二维数组 |
1.8 |
21 |
二维数组右上左下遍历 |
3 |
|
1.8 |
23 |
二维数组回形遍历 |
3 |
|
1.8 |
24 |
蛇形填充数组 |
|
|
1.13 |
34 |
确定进制 |
3 |
各种进制转换 |
1.13 |
35 |
输出二进制补码 |
2 |
需要复习补码的定义。 |
1.13 |
40 |
提取数字串按数值排序 |
3 |
|
1.13 |
41 |
判断元素是否存在 |
3 |
队列? |
1.13 |
43 |
相关月 |
2 |
日历问题 |
1.13 |
45 |
十进制到八进制转换 |
2 |
|
1.13 |
46 |
八进制到十进制转换 |
2 |
|
1.13 |
47 |
大整数除法 |
3 |
|
1.13 |
50 |
数根 |
3 |
|
2.1 |
1749 |
数字方格 |
2 |
|
2.1 |
1809 |
两倍 |
2 |
|
2.1 |
1943 |
满足条件的整数 |
2 |
|
2.1 |
1973 |
确定进制 |
4 |
实现比较麻烦 |
2.1 |
1978 |
生理周期 |
3 |
|
2.1 |
2673 |
比赛排名 |
2 |
需要用枚举实现 |
2.1 |
2723 |
因子问题 |
2 |
|
2.1 |
2983 |
谁是你的潜在朋友 |
2 |
|
2.1 |
3526 |
最简真分数 |
2 |
|
2.1 |
6184 |
找和为K的两个元素 |
2 |
|
2.1 |
7213 |
垃圾炸弹 |
3 |
|
2.1 |
7217 |
猴子吃桃 |
3 |
|
2.1 |
7621 |
硬币面值组合 |
3 |
|
2.1 |
7623 |
五户共井问题 |
3 |
|
2.1 |
7647 |
余数相同问题 |
3 |
|
2.1 |
7649 |
我家的门牌号 |
3 |
|
2.1 |
7650 |
不定方程求解 |
2 |
|
2.1 |
7827 |
质数的和与积 |
2 |
|
2.1 |
7832 |
最接近的分数 |
2 |
|
第五部分,难题,冲击一等高分
这部分内容,需要灵活应用搜索、栈、队列,需要图和树的基本算法知识,而且也要求灵活应用。如果大部分题目能在 40 分钟内自行调试完毕,然后一次提交 AC,普及组可以冲击 300 分。 对应到北京市普及组前 50 名了。
这些题要挨个做,不要挑了。
OJ单元 |
题号 |
题目 |
难度 |
注释 |
2.1 |
1813 |
熄灯问题 |
4 |
|
2.1 |
1815 |
画家问题 |
3 |
|
2.1 |
1816 |
播种问题 |
4 |
|
2.1 |
8755 |
砝码称重 |
4 |
|
2.2 |
1696 |
逆波兰表达式 |
3 |
|
2.2 |
1751 |
分解因数 |
3 |
|
2.2 |
1777 |
文件结构“图” |
3 |
|
2.2 |
2705 |
括号匹配问题 |
3 |
|
2.2 |
7592 |
求最大公约数问题 |
2 |
|
2.2 |
8758 |
2的幂次方表示 |
5 |
|
2.2 |
9273 |
PKU2506Tiling |
5 |
铺瓷砖 |
2.3 |
6262 |
流感传染 |
3 |
2D 范围内的传染问题 |
2.4 |
2991 |
2011 |
3 |
快速幂 |
2.5 |
1159 |
Maze |
5 |
找 key 过关走迷宫。 |
2.5 |
1253 |
Dungeon Master |
4 |
3D 走迷宫 |
2.5 |
131 |
Channel Allocation |
6 |
搜索剪枝? |
2.5 |
1388 |
Lake Counting |
4 |
染色问题 |
2.5 |
156 |
LETTERS |
5 |
|
2.5 |
1789 |
算24点 |
4 |
建议先上网搜一下题解,看看思路。 |
2.5 |
1805 |
碎纸机 |
4 |
|
2.5 |
1817 |
城堡问题 |
4 |
|
2.5 |
1818 |
红与黑 |
3 |
|
2.5 |
2152 |
Pots |
5 |
在两个瓶子之间来回倒水 |
2.5 |
2971 |
抓住那头牛 |
5 |
|
2.5 |
2990 |
符号三角形 |
5 |
|
2.5 |
323 |
棋盘问题 |
4 |
|
2.5 |
4980 |
拯救行动 |
4 |
|
2.5 |
6044 |
鸣人和佐助 |
4 |
|
2.5 |
7221 |
拯救公主 |
3 |
|
实际上除了USACO备赛可用以外,后续大家备赛CSP、或者作为平时的知识点查漏补缺,都是非常有帮助的! 大家可以参考这个内容,在考前最后梳理一遍知识点内容,做最后的查漏补缺,期待各位考生的好成绩!
|