2022年12月USACO铜级真题——Feeding The Cow解析

今天我们要给大家讲解的是一道 2022 年 12 月的铜级真题——Feeding The Cow。

英文好的小伙伴推荐看英文原版题目↓

觉得英文理解起来麻烦的同学也可以看翻译好的中文题：

解题分析：

题目要求得种植的草的数目要求最小，那么就意味所种植的草能够尽可能大的覆盖更多的?。

那么问题来了，草种在哪里才会被更多的?吃到呢？

我们现在假设有多头同品种的牛，愿意移动的最大步数为2，那么如下图选择草的位置能够保证之中的草的数量是最少的。

如上图所示，当从编号为i的牛开始考虑种草的位置时，我们可以将草种在第i+k的位置，这就意味距离location为i+k的草的距离小于k的牛都能够有草吃。

如果我们定草的位置为patch，牛的位置为cow，那么当满足cow-patch<=k时， 则无需考虑新种草；

反之，当 cow-patch>k，如上图编号为6的牛正好无法吃到，那么就需要确定下一个草的位置；

由上图可以看出，第二颗草的位置应该为6+k，即patch = 8；

同理，第三颗草的位置应该是编号11的牛的位置11+k，但是此时你可能已经注意到11+2已经超出了总共的牛的数量，那么此时我们只要将草种在编号为11的牛的脚下，即patch = 11，这样剩下的牛肯定都能被覆盖。

刚刚我们分析是基于所有的牛都是同品种的假设，那么如果是不同品种，分析过程会有变化么？

我们以题目中给出的测试案例来分析：

n=5；且牛的品种顺序为GHHGG

k=1；

由于第一头牛是G型牛，那么应该在patch_G= 2 的位置种G型草；

由于第二头牛的位置虽然被第一颗草的位置覆盖，但是由于品类不同，需要在patch_H= 3的位置种H型草；

第三头牛被patch_H=2 的草覆盖，所以不用考虑；

第四头牛是G型，且没有被任何草覆盖，因此需要在patch_G = 5的位置种值G型草；

第五头牛被patch_G = 5的草覆盖，所以不用考虑。

分析总结：

按顺序考虑 1…N 中的每头奶牛 i，判断是否需要种草。

如果当前的奶牛已经被覆盖，那么我们就不需要再种草了，我们可以继续判断下一头牛。

如果没有被覆盖，我们需要为这头牛种草，那么我们应该把它放在哪里呢？

为了每棵草能覆盖更多的牛，那么应该将其种在i+K 的位置。不仅奶牛 i 会被覆盖，而且在该草的 K 距离内的所有奶牛也将被覆盖。

当判断到最后几头奶牛时，可能会遇到一种情况：奶牛 i 需要喂食并且 i+K>N，我们可以将草种在位置 i，因为 i−1+K≥N，这个补丁覆盖了与奶牛 i 同品种的从 i 到 N 的所有奶牛。

当牛的品种大于等于2，会存在一种极端情况： 如果我们尝试在位置 i 种草，但那里已经有一个草（如下图）。在这种情况下，我们可以将草种在 i-1 处，因为i-1处和 i 处不可能已经有对应类型的草。

该解决方案的运行时间为 O(N)，因为我们只是对 N 头奶牛进行单次传递。

USACO计算机竞赛

USACO(United States of America Computing Olypiad)，即美国计算机奥林匹克竞赛，是针对美国中学生乃至全球学生的计算机编程在线竞赛。

编程作为一门使用技能会让学理工科的学生受益终生。即便是文商科的同学，编程训练本身带来的思维优势也可以极大地促进学习。

参赛语言：C、C++、Java、Python

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

为了便于大家理解，我们把 USACO 与 AMC 竞赛的难度做了简单的对比，参考如下?

铂金组≈AIME

黄金组≈AMC12

白银组≈AMC10

青铜组≈AMC 8

如果想要申请美国院校，USACO 一定是十分适合的选择。

USACO计算机暑期班火热招生

机构计算机教研组以 USACO 组织推荐的官方网站 USACO guide 上的知识点为主，对各组别算法进行了整理和更新，并创作了 500+的模拟真题，助力学生冲击 USACO 金银成绩！

USACO 课程体系设置

常规+冲刺

常规：知识讲解，夯实基础

冲刺：真题演练，高效备考

我们采用 Lecture + Lab 的授课形式。这是目前美国很多主流大学都在用的教育体系，我们经过改良优化后，利用该体系来高效备战 USACO 考试。

Lecture：2-6 人的Lecture帮助学生快速了解知识点内容；

Lab：1v1 形式的研讨和交流，旨在帮助学生深化对知识的理解以及激发学生的思维潜力。