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

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

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

铜组第二题

INPUT FORMAT（pipe stdin）：

第一行包含N，农夫约翰的奶牛数量。下一行包含一个N只有1的字符位字符串s和0

s其中1表示受感染的奶牛和0表示经过一些夜晚后未受感染的奶牛。

输出格式（pipe stdout）：

输出一个整数：可能开始生病的奶牛的最小数量。

样本输入：

5

11111

样本输出：

1

假设中间的奶牛是唯一一头开始被感染的奶牛。然后奶牛会按照以下顺序被感染：

0晚：00100（第三头奶牛最初被感染）

1晚：->01110（第二头和第四头奶牛现在被感染）

2晚：->11111（第一头和第五头奶牛现在被感染）

3晚：->11111（所有奶牛都已被感染，因此没有其他奶牛被感染）

->。。。

在两个或多个晚上之后，奶牛的最终状态看起来就像输入。还有许多其他初始状态和夜晚数可能会产生输入状态，例如：

0晚：10001

1晚：->11011

2晚：->11111

或者：

0晚：01001

1晚：->11111

或者：

0晚：01000

1晚：->11100

2晚：->11110

3晚：->11

111

所有这些初始状态都包含至少一头受感染的奶牛。

样本输入：

6

011101

样本输出：

4

唯一可能导致这种最终状态的初始状态和夜晚数是，如果没有夜晚过去，输入的四头受感染的奶牛中的每一头都开始生病。

评分：

输入3-7：N≤1000

输入8-12：无其他约束。

试题解析

首先我们可以根据输入计算出1的扩散时间最长是多少（时间越长需要的初始点就越少）

注意边界和中间的计算方式不同，中间扩散的结果是1,3,5,...,2*n-1，而边界是1,2,3,...,n$因为边界可以放在最角落开始）

计算出最长扩散时间max_time后我们就可以对每一段连续为1计算初始最少需要放几个1 : len = 2*max_time+1 (len代表连续1个数)

最终将答案相加即可

时间复杂度：O(n)

知识点：贪心，边界条件判断

核心代码如下：

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账号，即可开始考试