2023USACO竞赛12月晋级赛铜组考情分析~USACO竞赛冲刺培训招生中~

农夫约翰的奶牛很爱吃甜食，它们特别喜欢吃甘蔗糖!FJ有N头牛，每头牛都有一定的初始身高，他想喂它们M每根也有不同高度(1≤N，M≤2·10^5)。

按照它们在输入中的顺序，FJ计划将甘蔗糖一根接一根地喂给奶牛。为了给奶牛喂甘蔗糖，他会把甘蔗糖挂起来，这样甘蔗糖一开始就刚好碰到地面。然后，奶牛将按照输入的顺序一头接一头地排队，走到甘蔗糖前，每头牛都吃到自己的高度(因为它们不能再高了)。即使在奶牛吃掉糖果棒的底部后，糖果棒也会悬挂在最初设置的位置，不会下降到地面。

如果甘蔗的底部已经超过奶牛的高度，那么奶牛在轮到它的时候可能什么都不吃。轮到每头牛后，奶牛的身高会根据它们吃了多少单位的甘蔗糖而增加，农民约翰挂上下一根甘蔗糖，奶牛再次重复这个过程(第一头牛再次成为第一个开始吃下一根拐杖糖的人)。

试题解析：

这个题是个有意思的暴力问题，同学们考虑一个子问题：

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

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

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

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

时间复杂度：O(nlog2n)

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

农夫约翰有N排成一行的奶牛(1≤N≤3·10^5)。不幸的是，有一种疾病正在蔓延。

最初，一些奶牛开始被感染。每天晚上，受感染的奶牛都会将疾病传播给左右两侧的奶牛(如果存在的话)。一旦奶牛被感染，它就会继续被感染。

经过几个晚上，农夫约翰意识到问题已经失控，所以他对奶牛进行了测试，以确定谁生病了。找出可能开始患病的奶牛的最小数量。

试题解析：

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

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

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

最终将答案相加即可

时间复杂度：O(n)

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

农民约翰正在种植N(1≤N≤2·10^5)他的农场里种着芦笋!然而，他的一些植物有遗传差异，所以有些植物会比其他植物生长得更快。

i的初始高度

第th株是hi英寸，每天之后

第th种植物生长ai英寸。

FJ比其他植物更喜欢他的一些植物，他希望一些特定的植物比其他植物高。他给你一组不同的值t1，…，tN包含0中的所有整数至N−1

他想要我第th株植物正好有ti其他比它高植物。

找到最小天数，以便FJ的要求得到满足，或者确定这是不可能的。

试题解析

考虑根据最终的排序结果来确定有多少条件，容易发现其实只有$n-1$个有效的不等式，即第1个小于第2个，第2个小于第3个，...

根据不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t对应的范围

最终对于所有不等式结果求出交集，如果不为空就输出最小值，否则输出-1

时间复杂度：O(n)

知识点：简单数学

1. 建议每天会花至少1个小时时间来巩固选择编程语言(建议直接选择C++)。复习语法、变量、数据类型等基本概念。

2. 每周留有至少10小时学习算法和数据结构学习，每个组别算法有所不同。USACO青铜组别算法包括包括循环、条件语句、数组和字符串操作等。USACO白银组别包括贪心、动态规划、图算法等，还有常见数据结构，如树、图、堆等。这些是解决USACO问题基本工具，也是进一步挑战更高级别题目基础。

3. 刷历年的USACO竞赛试题，建议每天至少两道。有助于巩固所学基本概念，并在实际问题中进行了应用。