12月USACO竞赛第一次晋级赛试题解析来啦！很多人感觉这次月赛题目还是挺难的，本文给大家送上犀牛计算机产品负责人石老师带来的独家解析。一起来看看吧！
农夫约翰的奶牛很爱吃甜食，它们特别喜欢吃甘蔗糖！FJ有N头牛，每头牛都有一定的初始身高，他想喂它们M每根也有不同高度（1≤N，M≤2·10^5)。
按照它们在输入中的顺序，FJ计划将甘蔗糖一根接一根地喂给奶牛。为了给奶牛喂甘蔗糖，他会把甘蔗糖挂起来，这样甘蔗糖一开始就刚好碰到地面。然后，奶牛将按照输入的顺序一头接一头地排队，走到甘蔗糖前，每头牛都吃到自己的高度（因为它们不能再高了）。即使在奶牛吃掉糖果棒的底部后，糖果棒也会悬挂在最初设置的位置，不会下降到地面。如果甘蔗的底部已经超过奶牛的高度，那么奶牛在轮到它的时候可能什么都不吃。轮到每头牛后，奶牛的身高会根据它们吃了多少单位的甘蔗糖而增加，农民约翰挂上下一根甘蔗糖，奶牛再次重复这个过程（第一头牛再次成为第一个开始吃下一根拐杖糖的人）。
INPUT FORMAT（pipe stdin）：
下一行包含N的初始高度奶牛，每头都在[1-10^9]范围内。
下一行包含M的高度糖果手杖，每根在[1-10^9]范围内。
OUTPUT FORMAT (pipe stdout):
请注意，此问题中涉及的大尺寸整数可能需要使用64位整数数据类型（例如，C/C++中的“long-long”）。
第一头牛吃掉第一根甘蔗糖的部分，直到高度3之后，第一根甘蔗糖的剩余部分占据高度[3，6]。
第二头牛不够高，吃不下第一根甘蔗糖的任何剩余部分。
第三头牛多吃两个单位的第一根甘蔗糖。第一根甘蔗糖的剩余部分，占据高度[5,6]，不吃。
接下来，每头奶牛的生长量与它的进食量相等，因此奶牛的高度变为[3+3，2+0，5+2]=[6,2,7]。
⭐犀牛解析⭐
USACO竞赛这个题是个有意思的暴力问题
考虑一个子问题：
一个数初始是1，每一次操作是让它乘2，要求这个数小于等于n，求最多能操作多少次
这个问题的答案比较显然是log2n次
那考虑当前的问题，考虑第一头牛，如果牛比甘蔗矮，那么它吃完甘蔗后高度乘22；如果牛比甘蔗高，此轮吃甘蔗结束。
所以这一题直接暴力模拟做到甘蔗被吃完复杂度就是对的。
时间复杂度：O(nlog2n)
农夫约翰有N排成一行的奶牛（1≤N≤3·10^5)。不幸的是，有一种疾病正在蔓延。
最初，一些奶牛开始被感染。每天晚上，受感染的奶牛都会将疾病传播给左右两侧的奶牛（如果存在的话）。一旦奶牛被感染，它就会继续被感染。
经过几个晚上，农夫约翰意识到问题已经失控，所以他对奶牛进行了测试，以确定谁生病了。找出可能开始患病的奶牛的最小数量。
INPUT FORMAT（pipe stdin）：
第一行包含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
唯一可能导致这种最终状态的初始状态和夜晚数是，如果没有夜晚过去，输入的四头受感染的奶牛中的每一头都开始生病。
⭐犀牛解析⭐
首先我们可以根据输入计算出1的扩散时间最长是多少（时间越长需要的初始点就越少）
注意边界和中间的计算方式不同，中间扩散的结果是1,3,5,...,2*n-1，而边界是1,2,3,...,n$因为边界可以放在最角落开始）
计算出最长扩散时间max_time后我们就可以对每一段连续为1计算初始最少需要放几个1 : len = 2*max_time+1 (len代表连续1个数)
Farmer John Actually Farms
农民约翰正在种植N（1≤N≤2·10^5)他的农场里种着芦笋！然而，他的一些植物有遗传差异，所以有些植物会比其他植物生长得更快。i的初始高度
第th株是hi英寸，每天之后
第th种植物生长ai英寸。
FJ比其他植物更喜欢他的一些植物，他希望一些特定的植物比其他植物高。他给你一组不同的值t1，…，tN包含0中的所有整数至N−1
他想要我第th株植物正好有ti其他比它高的植物。
找到最小天数，以便FJ的要求得到满足，或者确定这是不可能的。
第一个将由一个整数T组成，表示独立测试用例的数量（1≤T≤10）。
第四行由N组成不同整数ti表示FJ给你的数组。保证N的总和
输出T行，每个测试用例的答案在不同的行上。如果不可能，输出−1。
请注意，此问题中涉及的大尺寸整数可能需要使用64位整数数据类型（例如，C/C++中的“long-long”）。
在第一个样本输入中，有6个测试用例。
在第一个测试案例中，只有一个工厂，因此在第0天满足条件。
在第二个测试案例中，我们需要第一个植物比第二个植物短。第1天之后，高度分别为15和13。第二天之后，高度都是23。第3天之后，高度分别为31和33，这是满足条件的第一天。
第三个和第四个测试用例与第二个类似。
在第五个测试案例中，两种植物的初始高度均为7，生长速率均为8。因此，它们总是有相同的高度，因此这种条件永远不会得到满足。
在第六个测试案例中，最初不满足条件，并且增长率相同。所以这个条件永远不能满足。
在第一个测试案例中，第4天之后的最终高度为19、20、21、18、16。
在第二个测试案例中，第7天之后的最终高度为25、17、19、35、36。
⭐犀牛解析⭐
考虑根据最终的排序结果来确定有多少条件，容易发现其实只有$n-1$个有效的不等式，即第1个小于第2个，第2个小于第3个，...
根据不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t对应的范围
最终对于所有不等式结果求出交集，如果不为空就输出最小值，否则输出-1
时间复杂度：O(n)
USACO竞赛真题集
添加微信小助手在线领取
详情V：xnew13012833750
在代码提交后，系统会自动给出评分，如果学生拿到了此轮满分，系统会提示直接晋级。
如果学生在此轮没有拿到满分，需要等待USACO官方公布晋级分数线，每场月赛结束后一周内，官方会通过电子邮箱发放参赛选手的程序的评测结果。
成功晋级的选手就可以在下一场月赛中参加更高级别的竞赛，没有成功晋级只能在下一场月赛中继续在原组别中打比赛。
同时进入官网，点击Contests，在相应的页面上可以找到比赛的最终结果总结、测试数据、题目解析、比赛的简要分析及参赛选手的成绩统计。
USACO竞赛培训班针对不同基础的同学都有开设课程，轻松跨过入门的各种门槛，冲刺拿金奖。
我们按照USACO铜升银、USACO银升金、USACO金升铂金三个级别的考点分别设置了不同的课程，课程内容涵盖基础语法、简单算法、图论算法、高级算法、数据结构、真题讲解等，带着学员从入门到拿奖，逐步提高计算机编程能力。
USACO竞赛辅导课程
添加微信小助手在线咨询
详情V：xnew13012833750 |
