低门槛高含金量竞赛!USACO竞赛备赛全攻略!

USAC计算机竞赛2024年度新赛季已经开启。USACO竞赛备赛流程是学生备战USACO竞赛的关键步骤,通过系统的备考,学生可以提高编程能力和解题技巧,为顺利应对竞赛打下坚实基础。

1、熟悉赛制和要求

在开始备考之前,了解赛制和要求是至关重要的。USACO竞赛分为铜、银、金和白银四个级别,每个级别都有不同的难度和要求。仔细研究每个级别的考试内容和要求,制定相应的备考计划,这将有助于学生有针对性地备考,更好地应对考试挑战。

同时,对于家长来说,也可以通过深入了解赛制和要求,更好地指导孩子的备考计划,帮助孩子在竞赛中取得更好的成绩。

最后,了解赛制和要求也可以让家长更加了解USACO竞赛的专业性和挑战性,对孩子的成长有积极的促进作用。

2、建立坚实的编程基础

在算法竞赛中,出色的编程能力是必不可少的。首先,确保对常用的编程语言(如C++或Java)有扎实的掌握。这不仅有助于学生更好地理解和实现算法,也为日后的编程学习打下了坚实的基础。

其次,学习并理解常用的数据结构和算法,例如栈、队列、链表、图和排序算法等,可以帮助学生更好地应对USACO竞赛中的各种题目,提高解题效率。

对于家长来说,可以鼓励孩子在编程学习过程中保持耐心和毅力,这种坚持不懈的精神也是孩子成长过程中的宝贵财富。

3、刷题提升解题能力

刷题是提高解题能力的有效途径。通过刷USACO官方提供的历年试题和参考书籍上的习题,可以逐渐提高自己的解题思维和编程技巧。(需要真题及解析的同学可以扫描文末二维码免费领取)这有助于学生更好地理解题目要求,培养解题思路和分析问题的能力。

家长可以在刷题过程中给予孩子适当的指导和鼓励,帮助孩子建立自信心,同时也可以通过讨论问题的方式促进孩子的思维发展。

此外,刷题还可以帮助孩子巩固所学知识,加深对编程和算法的理解,为应对竞赛做好充分准备。

4、参加模拟考试和比赛

参加模拟考试和比赛是检验备考效果和积累实战经验的好方法。这可以帮助学生熟悉真实的竞赛环境和时间限制,并检验自己在规定时间内解决问题的能力。同时,通过模拟考试和比赛,学生还可以发现自己在编程和解题中的不足之处,及时调整备考策略。

家长可以在孩子参加模拟考试和比赛时给予积极的支持和鼓励,不管成绩如何,重要的是参与和经验的积累。同时,家长也可以从中了解孩子在备考过程中的表现,更好地指导和帮助孩子提高备考效果。

通过模拟考试和比赛的经验积累,学生可以更加自信地应对USACO竞赛,更好地展现自己的编程能力和解题技巧。

USACO学术活动长线备考班、冲刺班已开启,扫描文末二维码领取限时优惠及备赛真题资料~

金牌导师&精编讲义“强强联手”

2023-2024赛季USACO竞赛第三轮开考!USACO竞赛算法答题步骤了解一下!

USACO竞赛与国内NOI系列竞赛类似,都是为国际信息学奥林匹克竞赛选拔人才。2024年1月USACO计算机竞赛1月月赛已经结束了。不知不觉中USACO第三场的考试已经到来!

2023-2024赛季第三轮时间:2月16日~2月19日

USACO竞赛算法答题步骤:

1.审题

USACO的题目一般都很长,要多花时间认真审题并通过样例数据来验证对题目的理解。

2.分析

然后分析题目给出的数据,思考如何通过已知数据和处理规则得到最终的答案;建议可以在纸上多演算样例数据,从每一步数据的变化中找到规律。

3.编码

题目分析清楚后进行编码,尽量使用比较熟悉的函数和数据结构;编码时要小心谨慎以防出错!

4.检查提交

最后审查一些边界条件是否有问题,并对未知问题进行排查及整个代码的完善检查,完成代码提交。

USACO竞赛分为四个级别:铜级(Bronze)、银级(Silver)、金级(Gold)和铂金级(Platinum)。每个级别都有不同的难度和题目类型。

以下是对每个级别的简要介绍:

1. 铜级(Bronze):

- 难度:入门级别
- 内容:铜级考察基本的编程知识和算法思维。题目通常涉及排序、搜索、模拟等基本算法和数据结构的应用。
- 考试时间:通常为4小时,需要在规定时间内完成3道题目。

2. 银级(Silver):

- 难度:中级水平
- 内容:银级考察递归、动态规划、贪心算法等更高级的算法和数据结构。题目要求更复杂,需要综合运用多个算法和数据结构来解决问题。
- 考试时间:通常为4小时,需要在规定时间内完成3道题目。

3. 金级(Gold):

- 难度:高级水平
- 内容:金级考察更复杂的算法和数据结构,如图论、最短路径算法、网络流等。题目要求解决实际问题,并考虑算法的效率和优化。
- 考试时间:通常为4小时,需要在规定时间内完成3道题目。

4. 铂金级(Platinum):

- 难度:最高级别
- 内容:铂金级考察高级算法和数据结构的应用,如高级图算法、动态规划优化等。题目更加开放和复杂,可能需要自行设计算法和数据结构来解决问题。
- 考试时间:通常为4小时,需要在规定时间内完成3道题目。

每个级别的考试时间和题目数量都相同,但题目的难度和要求会逐级提高。参加USACO竞赛需要具备扎实的编程基础和算法思维能力,以及解决实际问题的能力。

USACO长线备考班、冲刺班已开启,扫描文末二维码领取限时优惠及备赛真题资料~

金牌导师&精编讲义“强强联手”

USACO赛制是如何设置的?USACO竞赛各组别备考周期应该如何安排?

USACO美国信息学奥林匹克竞赛是一个知名的计算机编程竞赛,对于对算法和编程有浓厚兴趣的学生来说,是一个很好的锻炼机会。

USACO赛制

USACO采用积分赛制,分为月赛和公开赛,以及最终的美国国家队选拔。

USACO分为三次月赛,分别在每年的12月、1月和2月进行。选手有4小时的时间进行比赛,可以使用C++,Java,Python,Pascal或C等编程语言进行编程,在时间结束前通过网络提交程序。

3月份会组织一次USACO Open(公开赛),比赛时间为5小时。选手在比赛中需要解决多道题目,通过网络提交程序,获得评测结果。

在5-6月期间,USACO组织美国国家队集训,选拔出IOI(国际信息学奥林匹克竞赛)的美国国家队成员。这是一个非常具有挑战性的选拔过程,要求参与者具备深厚的算法和编程能力,并且是美国籍学生。

USACO竞赛各组别备考周期建议

从青铜到白银:通常需要2-4个月的时间来准备。在这段时间内,学生可以建立起基本的编程和算法基础,并熟悉竞赛的题型和要求。学生可以通过刷题和参加一些初级竞赛来提高自己的水平。

从白银到黄金:通常需要5-8个月的时间来准备。在这个阶段,学生需要进一步提高算法和数据结构的能力,并开始解决更加复杂的问题。学生可以通过刷题、参加中级竞赛和参加一些训练营来提高自己的水平。

从黄金到白金:通常需要6-12个月的时间来准备。在这个阶段,学生需要深入学习高级算法和数据结构,并能够灵活运用它们解决竞赛中的难题。学生可以通过刷题、参加高级竞赛和参加一些专业的培训课程来提高自己的水平。

从白金到集训队:通常需要3-5个月的时间来准备。在这个阶段,学生需要进一步提升算法和编程能力,并参加更多的模拟比赛和训练,以适应集训队选拔的要求。学生可以通过刷题、参加模拟比赛和参加一些集训队的选拔培训来提高自己的水平。

USACO学术活动长线备考班、冲刺班已开启,扫描文末二维码领取限时优惠及备赛真题资料~

金牌导师&精编讲义“强强联手”

USACO获奖需要具备什么能力?USACO等级是如何划分的?

USACO竞赛是美国知名度最高的计算机竞赛,在比赛中取得优异的成绩,也会受到众多顶尖美本的特别重视。

USACO获奖需要具备什么能力?

算法分析能力

对拿到的每道题目能够根据题目条件,确定对应算法进行解题,并对解题过程进行梳理。

代码编写能力

能够将梳理过的解题步骤转化为代码,并进行计算机求解。

数理逻辑能力

需要具备一定的英语阅读能力和数学逻辑能力。

注重实操

在学习编程初期,要多了解各种编程的区别,并通过大量刷题,培养提升自己的解题和编程能力以及总结相关算法模板。

USACO等级划分

在每场月赛中,根据之前题目的完成情况,选手会被分为不同的段位(青铜,白银,黄金与铂金),不同段位的题目难度依次递增。

新注册的参赛选手需要从青铜起步,在规定时间内完成三道题目,如果完成度较好将会被提升到更高段位,厉害的选手甚至可以在一次月赛开放期内连升多级到铂金段位。

青铜

参赛资格:一进入USACO注册账号即为铜级。

难度等级:铜级考试只要基本编程常识,会至少一种编程语言。铜级的编程限制时间还是够用的,大部分初次参赛的选手都能在第一次考试中晋级白银级。

白银

参赛资格:通过青铜级比赛的选手。

难度等级:需要基本的问题解决能力和简单算法(例如:贪心算法,递归搜索等),还需了解基础数据结构。从白银级开始,选手需要寻找更好的算法才能使程序在规定时间内跑完。

黄金

参赛资格:通过白银级比赛的选手。

难度等级:需要有一定的算法基础,理解一些抽象的方法(例:最短路径,动态规划),并且对数据结构有比较深的了解。

白金

参赛资格:通过黄金级比赛的选手。

难度等级:需要有很高的编程基础,对算法有深入的了解。部分比赛问题最后的优化方案,可能不只一个,得出的答案也不只一个。

USACO长线备考班、冲刺班已开启,扫描文末二维码领取限时优惠及备赛真题资料~

金牌导师&精编讲义“强强联手”

USACO竞赛常用语言解析!不同语言有什么特点?

USACO的比赛形式灵活多样,允许参赛者使用不同的编程语言,以便他们能够发挥自己的编程优势。选择合适的编程语言对于解决问题和提高效率非常重要。

不同的编程语言各有自己的优势和特点。在USACO中,一些常见的编程语言选择包括C++、Python、Java和Pascal等。下面将详细介绍一些常见的编程语言,并探讨它们在USACO学术活动中的应用情况。

首先,C++是最常用的编程语言之一。它以其高效性和强大的标准库而受到广泛欢迎。C++的语法较为复杂,但它提供了丰富的数据结构和算法库,使得解题过程更加方便快捷。许多获奖选手使用C++作为他们的首选语言,因为它在学术活动中的表现非常出色。

其次,Python是一门易学易用的编程语言,它以其简洁的语法和强大的库而备受青睐。Python的编写代码速度快,而且它也是一种解释型语言,这意味着没有繁琐的编译过程,能够更快地进行调试和测试。然而,Python在性能方面稍逊一筹,对于一些需要高效率的问题,可能不太适合。

另外,Java也是一门常用的编程语言之一,它具有良好的可读性和可维护性,尤其对于复杂的项目更为适用。Java也有着强大的面向对象编程能力,并且拥有广泛的开发社区和资源支持。然而,相对于C++和Python,Java的代码量通常较多,这可能在学术活动时显得有些不利。

此外,Pascal是一种古老但仍然被广泛使用的编程语言,它有着清晰的语法和强大的调试和错误定位能力。Pascal通常被用作学习编程的教育工具,它的简洁性和易用性使得初学者更容易上手。然而,在USACO中,Pascal的应用相对较少,因此可能缺乏相关的学术活动资源和支持。

需要注意的是,选择参赛使用的编程语言并不是唯一的决定因素。更为重要的是熟悉并深入掌握所选择的语言,因为解题能力和算法实现才是USACO竞赛的关键。当然,如果参赛选手在多种编程语言中都具备相当熟练的能力,那么他们可以根据不同题目的特点选择最适合的语言来解答问题。

扫码试听课程、免费领取必备学术活动资料

USACO竞赛规则详解!附USACO竞赛常见误区!

USACO竞赛已经成为计算机专业攀爬名校的必备利器。不论是在国内还是国际,USACO竞赛无疑是学生们展示自己计算机能力和取得成就的绝佳机会。

USACO竞赛出分快、备赛时间短、含金量高,想要短期内增加申请竞争力的同学就不要错过下一场月赛了!

竞赛规则

1.USACO每场比赛3-5个小时。可以在比赛规定时间开始后登陆USACO账号,从在线打开试题后开始计时。一套试题中有3-4道题,选手需要在时间结束前通过网络将写好的程序提交。

2.程序提交后官网会给出用test case检测程序的结果,并根据结果给出这一题的得分。可以使用C++、Java、Python、Pascal和C中的任意一种编程。比赛对于程序的大小,运行需要的内存以及运行的时间都有一些具体规定。对于后续有志于冲刺Camp的选手来说,建议一开始就选择C++语言,避免后续更换编程语言。

3.每次比赛,实力强的选手可以连续升级。在比赛窗口开放的4天时间内,选手可以选择任意时间开始比赛。

4.在比赛时间内,如果拿到了高分(接近满分或满分),系统会提示直接晋级,可以在这4天内继续挑战下一级,只要实力足够,一场考试可以升到满级铂金级。

USACO竞赛常见误区

USACO竞赛考试时间只有一天

USACO竞赛每一场考试考试都是有四天时间,学生可以在任意一天的当中的任意时间登陆进行时长为四小时的比赛。每一个选手的参赛时间是不同的,靠诚信约束选手不在比赛期间进行交流。

USACO竞赛不是晋级的比赛

USACO 的等级分为青铜、白银、黄金和白金四个档次。每个赛季的每一场比赛,这四个级别都会同时进行。学生注册就是青铜从青铜级别打起,达到一定的分数才能在下一场比赛晋级到上一个级别。

USACO竞赛晋级方式单一

USACO有两种晋级方式:一种是满分晋级,另一种是常规晋级。

如果选手在比赛中拿到满分。可以在同一场比赛中直接晋级到下一个等级比赛。如果学生实力够强可以在一场考试中从青铜直接晋级到白金。如果不是满分,需要在比赛结束后组织者根据全部选手的成绩划定分数线,分数线上的选手在下一场比赛的时候晋级到更高级别。

USACO的晋级分数线的划定不是固定的,是从这场比赛参赛选手的成绩根据比例反推的分数线。一般来说,在一场比赛的三道题当中,要拿到两道半才能晋级。

USACO学术活动长线备考班、冲刺班已开启,扫描文末二维码领取限时优惠及备赛真题资料~

金牌导师&精编讲义“强强联手”

扫码了解更多USACO竞赛规划

USACO竞赛有什么特点?参加USACO竞赛有意义吗?

对计划留学美国的学生来说,它具有非常大的含金量。参加USACO竞赛不仅能够为你的大学申请增添亮点,还能够培养和提高你的计算机科学技能。

在USACO竞赛中,你将面对一系列具有挑战性的计算机编程题目,要求你动用自己的逻辑思维和计算机编程能力来解决问题。

USACO(美国计算机奥林匹克竞赛)具有以下特点:

门槛低:USACO没有学校和地区级的限制,也没有报名费,任何学员都可以通过互联网参加,这为更多的学生提供了参与的机会。

赛程短:USACO赛程短,每月举行一次比赛,只要学生足够有能力,一次月赛就可以冲击最高奖,这为有志于参加的学生提供了更多的机会。

出分快:USACO比赛现场出分,学生可以及时了解自己的成绩,这有助于学生及时调整学习策略。

难度高:USACO分为铜、银、金、白金四个等级,难度逐级递增,对学生的编程能力和算法思维提出了更高的要求,因此USACO竞赛的难度相对较高。

USACO竞赛具有门槛低、赛程短、出分快和高难度等特点,为有志于参加计算机竞赛的学生提供了一个很好的平台。

参加USACO竞赛有何意义?

刷题练习:USACO的训练场和比赛堪称信息学奥赛的经典,许多国内命题也会参考USACO的历史原题。因此,通过参加USACO竞赛,可以进行大量的刷题练习,积累丰富的编程和算法经验,为国内信息学奥赛的备战提供宝贵的经验和素材。

赛事经验:USACO每年有4场比赛,每一场都有不同的题目和难度,这为选手提供了更多的赛事经验机会。相比之下,国内信息学奥赛每年只有一次,因此USACO的多场比赛可以帮助选手更快地积累赛事经验,提高应对竞赛的能力。

出国履历:USACO竞赛是国际知名的编程竞赛,取得优异成绩可以为学生增加出国履历,提高申请国外高校的竞争力。此外,USACO竞赛也为一些国际信息学奥赛(如IOI和EGOI)的选拔提供了重要的选拔依据,因此参加USACO竞赛对于有志于参加国际信息学奥赛的学生来说具有重要意义。

USACO秋季课程 正在火热组班中

金牌导师&精编讲义“强强联手”

背景提升利器!不同基础如何备考USACO?

美国USACO竞赛每年都在MIT官网上刷屏,它对于申请STEM专业的学生来说是一项重要的优势。达到白银级别及以上的等级在文科申请中具有一定的优势,而达到黄金级别对于申请美国计算机科学专业前30名的大学更具有说服力。甚至达到铂金级别会更容易获得像MIT、卡梅伦、佐治亚理工或加州伯克利等知名大学的计算机专业录取通知。

USACO比赛规则

学术活动赛制:采取积分赛制,分为月赛和公开赛两轮。USACO分为铜、银、金、铂金四个级别,难度依次递增。

晋级路径:青铜级→白银级→黄金级→铂金级,难度逐级递增。新注册的参赛选手需要从最低组别开始打起。

编程语言:

USACO支持多种编程语言的解决方案,包括C++、C、Java和Python。

由于Java和Python相比于C++/C语言的运行速度较慢,因此USACO允许Java和Python的运行时间是C++和C的两倍。

相比于国内的NOIP只接受C++作为考试语言,USACO提供了更加灵活的支持,使得喜欢Java和Python的人也有机会参与算法学术活动。

不同基础如何备考USACO?

新手入门:

对于没有编程基础的新手,建议从Python开始学习,因为Python上手比较快。学习重点应放在编程语言的语法和基本数据结构上,并进行一定强度的练习。通过这样的学习,可以基本掌握USACO青铜级别的选拔,顺利晋级到银组。

有一定编程基础:

如果已经有一定的编程基础,可以在Python的基础上学习C和C++。特别是想要一直晋级到铂金级别的学生,学习C++是必不可少的。在未来的学习和工作中,对于进一步提升编程能力和应对更复杂问题会有很大帮助。

编程熟练:

对于已经熟练掌握编程的学生,可以直接将目标放在冲击金和铂金级别上。专攻数据结构和算法,并大量练习USACO银升金、金升铂金组别的真题作为辅助。通过大量的练习和挑战,不断提升自己的解题能力和算法分析能力,从而在竞赛中取得更好的成绩。

无论基础如何,备考USACO都需要学习编程语言的基础知识、数据结构和算法,并进行大量的练习和挑战。不断提升自己的编程能力和解题能力,才能在USACO竞赛中取得好的成绩。

扫码免费领取USACO知识点思维导图 + 备考书单

USACO竞赛冬季班课开启,提前锁定席位,扫码了解课程详情!

2024 年 1 月比赛——最终结果

2024 年 1 月的比赛以算法编程问题为特色,涵盖了广泛的技术和难度级别。

在为期 4 天的比赛中,共有 12746 名不同的用户登录了比赛。共有来自125个不同国家的10101名参与者提交了至少一个解决方案:

4725 USA 3375 CHN 354 CAN 261 KOR 131 ROU 108 IND 78 MYS
77 SGP 64 HKG 57 TWN 46 DEU 44 GBR 44 AUS 40 SYR
34 TUR 33 POL 32 ISR 30 AZE 26 GEO 26 EGY 26 BLR
23 VNM 21 JPN 20 BRA 17 KAZ 17 ABW 16 IRN 15 SLV
15 FRA 15 COL 15 ARM 14 BOL 13 IDN 12 SAU 12 CUB
11 UZB 10 THA 10 NZL 10 MEX 10 ESP 10 BGD 9 PAK
8 ZAF 8 RUS 8 ARG 7 SWE 7 NLD 5 UKR 5 EST
5 CHL 5 AUT 5 ATG 5 AFG 4 SRB 4 MKD 4 KGZ
4 GRC 4 BEL 4 ARE 4 AND 3 ZWE 3 UMI 3 TUN
3 PHL 3 ANT 3 ALB 3 ALA 3 AGO 2 VIR 2 TKM
2 PRK 2 NPL 2 NER 2 MNG 2 MLT 2 MAC 2 LTU
2 ITA 2 IRL 2 HRV 2 GHA 2 FIN 2 CMR 2 CHE
2 BWA 2 ASM 1 YEM 1 VGB 1 VAT 1 TZA 1 TKL
1 TJK 1 SEN 1 QAT 1 PSE 1 PER 1 NOR 1 MMR
1 MDA 1 MCO 1 MAR 1 LAO 1 KHM 1 KEN 1 JEY
1 IMN 1 HUN 1 HTI 1 GIB 1 FSM 1 DNK 1 CZE
1 CYP 1 CXR 1 CRI 1 CCK 1 CAF 1 BTN 1 BRN
1 BLZ 1 BIH 1 BHR 1 BGR 1 BDI 1 ATF

总共有 26414 份分级提交,按语言细分如下:

13779 C++17
4504 C++11
4018 Python-3.6.9
3975 Java
117 C
21 Python-2.7.17

以下是白金、黄金、白银和铜牌比赛的详细结果。 您还可以找到每个问题的解决方案和测试数据。

USACO 2024 年 1 月比赛,白金奖

白金组共有489名参与者,其中347名是大学预科生。得分最高的结果在这里。恭喜所有顶尖参赛者取得优异成绩!

1 Island Vacation
查看问题 | 测试数据 | 解决方案
2 Merging Cells
查看问题 | 测试数据 | 解决方案
3 Mooball Teams III
查看问题 | 测试数据 | 解决方案

USACO 2024 年 1 月比赛,金牌

金牌组共有940名参与者,其中641名是大学预科生。所有在本次比赛中获得 800 分或更高分的参赛者将自动晋升为白金组。所有晋升者的详细结果都在这里。

1 Walking in Manhattan
查看问题 | 测试数据 | 解决方案
2 Cowmpetency
查看问题 | 测试数据 | 解决方案
3 Nap Sort
查看问题 | 测试数据 | 解决方案

USACO 2024 年 1 月比赛,银奖

白银组共有3920名参与者,其中2956名是大学预科生。所有在本次比赛中获得 750 分或更高分的参赛者将自动晋升为黄金组。

1 Cowmpetency
查看问题 | 测试数据 | 解决方案
2 Potion Farming
查看问题 | 测试数据 | 解决方案
3 Cowlendar
查看问题 | 测试数据 | 解决方案

USACO 2024 年 1 月比赛,铜牌

铜牌组共有8454名参赛者,其中6556名是大学预科生。所有在本次比赛中获得 750 分或更高分的参赛者将自动晋升为银牌组。

1 Majority Opinion
查看问题 | 测试数据 | 解决方案
2 Cannonball
查看问题 | 测试数据 | 解决方案
3 Balancing Bacteria
查看问题 | 测试数据 | 解决方案

结语

从科学的角度来看,2024 年 1 月的比赛进行得很顺利, 所有级别都有强大的问题阵容,并且有相当数量的学生得到提升。不幸的是,我们在比赛期间经历了两次大规模的拒绝服务攻击,这干扰了大量参赛者的比赛运作。因此,我们正在努力迁移到更强大的新托管平台,该平台具有更强大的对策来应对这种情况。对于那些受到这些中断影响的人,我们理解并分享你们的沮丧。 不幸的是,对于超出我们控制范围的中断,我们的一般政策不允许我们为受影响的人提供额外的时间,这是出于维护我们比赛的完整性的需要,这确实是美国IOI和EGOI团队的选拔机制。对于美国大学预科白金选手:由于认证白金窗口不受影响,本次比赛的分数将被计算在内,在决赛选择期间,我们的教练将确保不会对本次比赛中可能受到中断影响的非认证白金分数进行处罚。例如,在本次比赛中,3个认证分数加上一个可能受到损害的非认证分数将得到充分考虑。

对于那些尚未晋升的人,请记住,你得到的练习越多,你的算法编码技能就会越好——请坚持下去!USACO的竞赛旨在挑战最优秀的学生,要想在竞赛中脱颖而出,可能需要付出大量的努力。

许多人为USACO比赛的质量和成功做出了贡献。参与本次比赛的有Benjamin Qi、Dhruv Rohatgi、Nick Wu、Suhas Nagar、Rohin Garg、Brandon Wang、Rain Jiang、Danny Mittal、Timothy Qian Anand John、Ben Chen、Andi Qu、Bing-Dong Liu、Richard Qi、Andrew Gu、Claire Zhang、Nathan Wang和Spencer Compton。也感谢我们的翻译和克莱姆森CCIT提供我们的比赛基础设施。最后,我们感谢USACO赞助商的慷慨支持:Citadel、Ansatz、X-Camp、TwoSigma、VPlanet Coding、EasyFunCoding、Orijtech和Jump Trading。

我们期待在 2024 年 2 月的比赛中再次见到大家。

祝您编码愉快!

2024年1月美国计算机奥赛USACO竞赛铜奖组问题三—Balancing Bacteria

Farmer John has N (1≤N≤2⋅105) patches of grass in a line, where patch i
has a level of bacteria that differs by ai from that of healthy grass (−1015ai≤1015). For example, if ai=−3, then patch i has a level of bacteria 3 lower than normal, and would need exactly 3 additional units of bacteria added to raise it to the point where it is considered healthy.

Farmer John wants to ensure every patch of grass is corrected to have a healthy level of bacteria. Conveniently, he owns two brands of pesticide that he can spray on his field, one that adds bacteria and one that removes bacteria. When Farmer John sprays either type of pesticide, he stands in patch N (the rightmost patch) and selects a power level L for his sprayer (1≤LN).

The sprayer has the most impact on patches near Farmer John, with diminishing effect farther away. If Farmer John chooses the pesticide that adds bacteria, then L units of bacteria will be added to patch N, L−1 units to patch N−1, L−2 units to patch N−2, and so on. Patches 1…N−L will receive no bacteria, since the sprayer isn't set to a level powerful enough to reach them. Similarly, if Farmer John chooses the pesticide that removes bacteria, then L units of bacteria will be removed from patch N, L−1 units will be removed from patch N−1, and so on. Again, patches 1…NL will be unaffected.

Find the minimum number of times Farmer John has to apply his sprayer such that every patch of grass has the recommended value of bacteria for healthy grass. It is guaranteed that the answer is at most 109.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N .

The second line contains N integers a1,a2,…,aN , the initial bacteria levels of each patch of grass.

OUTPUT FORMAT (print output to the terminal / stdout):

The minimum number of applications necessary to make every patch of grass have the recommended value of bacteria for healthy grass.

SAMPLE INPUT:
2
-1 3

SAMPLE OUTPUT:

6

Use the type of pesticide that removes bacteria, at a power level of 1, five times. Then use the type of pesticide that adds bacteria, with a power level of 2, one time.

SAMPLE INPUT:

5
1 3 -2 -7 5

SAMPLE OUTPUT:

26

SCORING:

Inputs 3-5: N≤103, the answer is at most 103
Inputs 6-10: N≤103
Inputs 11-15: No additional constraints.

Problem credits: Rohin Garg

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划