2023-2024年USACO计算机竞赛第一场月赛赛题出炉！让我们一起来了解一下吧~
USACO 2023 DECEMBER CONTEST
BRONZE（铜级）
第一题糖果盛宴
题目描述:
农夫约翰的奶牛很爱吃甜食，它们特别喜欢吃甘蔗糖！FJ有N头牛，每头牛都有一定的初始身高，他想喂它们M每根也有不同高度（1≤N，M≤2·10^5)。
按照它们在输入中的顺序，FJ计划将甘蔗糖一根接一根地喂给奶牛。为了给奶牛喂甘蔗糖，他会把甘蔗糖挂起来，这样甘蔗糖一开始就刚好碰到地面。然后，奶牛将按照输入的顺序一头接一头地排队，走到甘蔗糖前，每头牛都吃到自己的高度（因为它们不能再高了）。即使在奶牛吃掉糖果棒的底部后，糖果棒也会悬挂在最初设置的位置，不会下降到地面。
如果甘蔗的底部已经超过奶牛的高度，那么奶牛在轮到它的时候可能什么都不吃。轮到每头牛后，奶牛的身高会根据它们吃了多少单位的甘蔗糖而增加，农民约翰挂上下一根甘蔗糖，奶牛再次重复这个过程（第一头牛再次成为第一个开始吃下一根拐杖糖的人）。
第二题感染奶牛追踪
题目描述:
农夫约翰有N排成一行的奶牛（1≤N≤3·10^5)。不幸的是，有一种疾病正在蔓延。
最初，一些奶牛开始被感染。每天晚上，受感染的奶牛都会将疾病传播给左右两侧的奶牛（如果存在的话）。一旦奶牛被感染，它就会继续被感染。
经过几个晚上，农夫约翰意识到问题已经失控，所以他对奶牛进行了测试，以确定谁生病了。找出可能开始患病的奶牛的最小数量。
第三题Farmer John Actually Farms
题目描述:
农民约翰正在种植N（1≤N≤2·10^5)他的农场里种着芦笋！然而，他的一些植物有遗传差异，所以有些植物会比其他植物生长得更快。i的初始高度
第th株是hi英寸，每天之后
第th种植物生长ai英寸。
FJ比其他植物更喜欢他的一些植物，他希望一些特定的植物比其他植物高。他给你一组不同的值t1，…，tN包含0中的所有整数至N−1
他想要我第th株植物正好有ti其他比它高的植物。
找到最小天数，以便FJ的要求得到满足，或者确定这是不可能的。
USACO 2023 DECEMBER CONTEST
SILVER（银级）
第一题Bovine Acrobatics
题目描述:
农场主约翰决定让他的奶牛表演一些杂技！首先，约翰称了一下他的奶牛，发现它们有 N（1≤N≤2⋅10*5）个不同的重量。特别是，对于每个 i∈[1,N]，他的牛中有 ai 重量为 wi（1≤ai≤109,1≤wi≤109）。
他最受欢迎的绝技是让奶牛组成平衡塔。塔是一连串的奶牛，每头奶牛都叠在下一头奶牛的上面。如果每头牛与正上方的牛的重量至少比正上方牛的重量大 K（1≤K≤109），那么这个塔就是平衡的。任何一头牛最多只能成为一个平衡塔的一部分。
如果 FJ 想创建最多 M 个（1≤M≤109）平衡的牛塔，那么最多有多少头牛可以成为某个牛塔的一部分？
第二题Cycle Correspondence
题目描述:
农场主约翰有 N 个谷仓（3 <= N <= 5.105），其中有 K（3 <= K <= N）对不同的谷仓相连。
首先，安娜贝尔给每个谷仓分配一个范围为[1，N]的不同整数标签，并观察到标签为 a1...ak 的谷仓依次循环连接。也就是说，在所有 1 <= i < K 的情况下，谷仓 ai 和 a(i+1) 是相连的，谷仓 ak 和 a1 也是相连的。接下来，贝西还为每个谷仓分配了一个范围为[1，N]的不同整数标签，并观察到标签为 b1，...bk 的谷仓依次连接成一个循环。所有 bi 都是不同的。
安娜贝尔和贝西给某些（可能没有或全部）谷仓分配了相同的标签。计算被安娜贝尔和贝西赋予相同标签的谷仓的最大可能数目。
第三题Target Practice
题目描述:
贝西是一个机器人，也叫牛伯格。它在一条数字线上，试图射中一系列位于不同位置的 T（1≤T≤105）目标。贝西从位置 0 开始，执行一串 C（1≤C≤105）指令，每个指令都是 L、F 或 R：
L: 贝西向左移动一个单位。
R：贝西向右移动一个单位。
F: 贝西开火。如果贝西当前位置有目标，则该目标会被击中并摧毁，且无法再次击中。
如果允许在贝西开始执行命令之前将字符串中的一个命令改为另一个命令，那么贝西最多可以击中多少个目标？
USACO 2023 DECEMBER CONTEST
GOLD（金级）
第一题飞行路线
题意:
给定n个机场，编号1-n，约定只有小的数字到大的数字有航班，而且两点之间最多只有一趟航班。告知每两个机场之间总航班数量的奇偶性（奇数个航班用1表示，偶数个用0表示），计算两点之间有直达航班的数量。
第二题Cycle Correspondence
题意:
给定一个n个点m条边的有向无环图（DAG)，计算从每个点出发最长的链的长度和总长度。如果有多个路径长度都最大，取路径上边长序列字典序最小的链。
第三题Target Practice
题意:
有n个谷仓，给定每个谷仓的位置，现要把所有谷仓的草都运送到一个谷仓y。运送草的代价是y左边的谷仓x的代价是a*(y-x), y右边的谷仓x的代价是b*(x-y)。给q次查询，每次输入a和b的值，求最小的运输总代价。
USACO什么学生能参加？
USACO竞赛适合对计算机编程感兴趣的学生或者要申请计算机专业的学生，适合任意年级的中学生参加。
（小学生也可以参加；即使是高三学生，也可以参加12月的比赛）
官方网站：http://www.usaco.org/
你是否适合参加USACO竞赛？
1、兴趣是最重要的
从USACO的初阶到高阶赛，需要进行反复、大量的训练。需要确认自己是否对每周5-8小时的算法训练能够持续保持兴趣和热情。
2.数学基础非常必要
在编程的世界中，有时候思维比代码本身更为重要。
虽然数学和编程有本质上的区别，但它们之间存在着紧密的联系：数学帮助我们按步骤完成计算，而编程帮助我们实现每个计算步骤。
编程的基础是建立在数学之上的。例如，树、图、堆等数据结构以及贪心算法、动态规划等算法都需要应用数学思维和方法。
学好编程需要打好数学基础，包括：
计数能力：在for循环中经常用到，类似小学数学的知识。
数字的加减乘除：每种编程语言都内置支持，不需要手动计算。
余数和模运算：偶尔会用到。
集合运算：交集、并集、差集，编程中用到的不多。
布尔运算：AND、OR等逻辑运算。
各种进制：二进制、十进制、十六进制等。
USACO不同级别难度如何？
USACO竞赛根据编程技能水平划分为四个级别：铜级、银级、金级和铂金级。
新注册的选手从铜级开始，需要在规定的时间内完成三道题目，每个级别的题目均为三道，如果通过则可以晋级到更高级别。
青铜级别：
首次参加USACO竞赛的学生都属于青铜级别，只要注册USACO账号即为铜级。
难度等级：适用于刚学会编程的学生，需要掌握基本的排序和二进制搜索等概念，但没有算法方面的培训。在这个级别，学生需要能够解释一个编程问题，并能够用基本的算法和逻辑将自己的想法转化为代码。
白银级别：
通过铜级比赛的选手可以参加白银级别。
难度等级：它涉及到递归搜索、贪心算法等基本的问题求解技术，还需要了解基础的数据结构，并会考察效率问题。从白银级别开始，选手需要寻找更好的算法来确保程序在规定时间内运行完毕。
黄金级别：
通过白银级比赛的选手可以参加黄金级别。
难度等级：需要具备一定的算法基础，理解一些抽象的方法，例如最短路径、动态规划等，并对数据结构有较深的了解。
白金级别：
通过黄金级比赛的选手可以参加白金级别。
难度等级：需要具备较高的编程基础，对算法有深入了解，能解决复杂问题、开放问题。题目复合多种算法，还会涉及高难度辅助算法，不但思维难度大，编码工作量也在加大。
【竞赛报名/项目咨询请加微信：mollywei007】
