2023-2024赛季，USACO美国计算机编程奥赛首次月赛在12月19日结束，今天给大家分享USACO竞赛试题和解析，参赛的同学来看看解题思路，没参赛的同学来看看难度如何？
这个题是个有意思的暴力问题
考虑一个子问题：
一个数初始是1，每一次操作是让它乘2，要求这个数小于等于n，求最多能操作多少次
这个问题的答案比较显然是log2n次
那考虑当前的问题，考虑第一头牛，如果牛比甘蔗矮，那么它吃完甘蔗后高度乘22；如果牛比甘蔗高，此轮吃甘蔗结束。
所以这一题直接暴力模拟做到甘蔗被吃完复杂度就是对的。
时间复杂度：O(nlog2n)
⭐犀牛解析⭐
第一行包含N，农夫约翰的奶牛数量。下一行包含一个N只有1的字符位字符串s和0
s其中1表示受感染的奶牛和0表示经过一些夜晚后未受感染的奶牛。
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
6
011101
考虑根据最终的排序结果来确定有多少条件，容易发现其实只有$n-1$个有效的不等式，即第1个小于第2个，第2个小于第3个，...
根据不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t对应的范围
最终对于所有不等式结果求出交集，如果不为空就输出最小值，否则输出-1
时间复杂度：O(n)
在第一个样本输入中，有6个测试用例。
在第一个测试案例中，只有一个工厂，因此在第0天满足条件。
在第二个测试案例中，我们需要第一个植物比第二个植物短。第1天之后，高度分别为15和13。第二天之后，高度都是23。第3天之后，高度分别为31和33，这是满足条件的第一天。
第三个和第四个测试用例与第二个类似。
在第五个测试案例中，两种植物的初始高度均为7，生长速率均为8。因此，它们总是有相同的高度，因此这种条件永远不会得到满足。
在第六个测试案例中，最初不满足条件，并且增长率相同。所以这个条件永远不能满足。
篇幅有限，本次试题和解析已打包，如有需要，扫码领取即可
USACO竞赛培训班针对不同基础的同学都有开设课程，轻松跨过入门的各种门槛，冲刺拿金奖。
我们按照USACO铜升银、USACO银升金、USACO金升铂金三个级别的考点分别设置了不同的课程，课程内容涵盖基础语法、简单算法、图论算法、高级算法、数据结构、真题讲解等，带着学员从入门到拿奖，逐步提高计算机编程能力。
回复“USACO”在线咨询
详情V：xnew13012833750
关键字：USACO竞赛,USACO计算机竞赛,USACO培训,
