2023-2024年USACO首次月考题目出炉！铜组第一题真题及解析

2023-2024赛季USACO首场月赛已经圆满结束，晋级赛的最新试题也已经公布。没能当场晋级的同学们可以耐心等待一周，一周内USACO官方将会公布本次晋级赛成绩。如果没有晋级，12月可以当做一个练手+熟悉赛制的环节，1、2月的月赛持续发力，USACO可以重复挑战。

今天给大家分享铜级试题和解析，参赛的同学来看看解题思路，没参赛的同学来看看难度如何？

铜组第一题

INPUT FORMAT（pipe stdin）：

第一行包含N和M。

下一行包含N的初始高度奶牛，每头都在[1-10^9]范围内。

下一行包含M的高度糖果手杖，每根在[1-10^9]范围内。

OUTPUT FORMAT (pipe stdout)：

每个N的最终高度奶牛在不同的线上。

请注意，此问题中涉及的大尺寸整数可能需要使用64位整数数据类型（例如，C/C++中的“long-long”）。

样本输入：

3 2

3 2 5

6 1

样本输出：

7

2

7

第一根甘蔗是6根单位高。

第一头牛吃掉第一根甘蔗糖的部分，直到高度3之后，第一根甘蔗糖的剩余部分占据高度[3，6]。

第二头牛不够高，吃不下第一根甘蔗糖的任何剩余部分。

第三头牛多吃两个单位的第一根甘蔗糖。第一根甘蔗糖的剩余部分，占据高度[5,6]，不吃。

接下来，每头奶牛的生长量与它的进食量相等，因此奶牛的高度变为[3+3，2+0，5+2]=[6,2,7]。

第二根甘蔗是1根

一个单位高，第一头牛吃掉了所有的。

范围

输入2-10：N，M≤10^3

输入11-14：无其他约束。

试题解析

这个题是个有意思的暴力问题

考虑一个子问题：

一个数初始是1，每一次操作是让它乘2，要求这个数小于等于n，求最多能操作多少次

这个问题的答案比较显然是log2n次

那考虑当前的问题，考虑第一头牛，如果牛比甘蔗矮，那么它吃完甘蔗后高度乘22；如果牛比甘蔗高，此轮吃甘蔗结束。

所以这一题直接暴力模拟做到甘蔗被吃完复杂度就是对的。

时间复杂度：O(nlog2n)

知识点：暴力，时间复杂度分析

核心代码如下：

USACO历年真题及参考书，扫码领取！【翰林提供报名指导服务】USACO历年真题及参考书

2023-2024年USACO活动时间

第一次月赛：2023年12月15日-18日

第二次月赛：2024年1月26日-29日

第三次月赛：2024年2月16日-19日

美国公开赛：2024年3月15日-18日

（中国学生只能参加到公开赛）

集训营：2024年5月23日-6月1日

EGOI：2024年7月21日-27日（荷兰）

IOI：2024年9月1日-8日（埃及）

报名方式：参赛者可随时在官网注册账号，注册。报名，只需在活动时间登陆完成答题即可。

官网地址：usaco.org

提交之后，官网会发送一份邮件到您邮箱，邮件中有账号密码

利用已知的账号于密码，登录USACO账号，即可开始考试