截至昨晚,2023-2024赛季UASCO竞赛第一场晋级赛正式结束,目前USACO晋级赛最新试题已经出炉,没能当场晋级的同学们可以耐心等待一周,一周内USACO官方将会公布本次晋级赛成绩。
今天为大家带来的是12月USACO竞赛第一次晋级赛的试题解析
USACO竞赛最新试题
P1Candy Cane Feast
农夫约翰的奶牛很爱吃甜食,它们特别喜欢吃甘蔗糖!FJ有N头牛,每头牛都有一定的初始身高,他想喂它们M每根也有不同高度(1≤N,M≤2·10^5)。
按照它们在输入中的顺序,FJ计划将甘蔗糖一根接一根地喂给奶牛。为了给奶牛喂甘蔗糖,他会把甘蔗糖挂起来,这样甘蔗糖一开始就刚好碰到地面。然后,奶牛将按照输入的顺序一头接一头地排队,走到甘蔗糖前,每头牛都吃到自己的高度(因为它们不能再高了)。即使在奶牛吃掉糖果棒的底部后,糖果棒也会悬挂在最初设置的位置,不会下降到地面。如果甘蔗的底部已经超过奶牛的高度,那么奶牛在轮到它的时候可能什么都不吃。
轮到每头牛后,奶牛的身高会根据它们吃了多少单位的甘蔗糖而增加,农民约翰挂上下一根甘蔗糖,奶牛再次重复这个过程(第一头牛再次成为第一个开始吃下一根拐杖糖的人)。INPUT FORMAT(pipestdin):第一行包含N和M。下一行包含N的初始高度奶牛,每头都在[1-10^9]范围内。下一行包含M的高度糖果手杖,每根在[1-10^9]范围内。OUTPUT FORMAT (pipe stdout):每个N的最终高度奶牛在不同的线上。
请注意,此问题中涉及的大尺寸整数可能需要使用64位整数数据类型(例如,C/C++中的“long-long”)。样本输入:3 23 2 56 1样本输出:727第一根甘蔗是6根单位高。第一头牛吃掉第一根甘蔗糖的部分,直到高度3之后,第一根甘蔗糖的剩余部分占据高度[3,6]。第二头牛不够高,吃不下第一根甘蔗糖的任何剩余部分。第三头牛多吃两个单位的第一根甘蔗糖。
第一根甘蔗糖的剩余部分,占据高度[5,6],不吃。接下来,每头奶牛的生长量与它的进食量相等,因此奶牛的高度变为[3+3,2+0,5+2]=[6,2,7]。第二根甘蔗是1根一个单位高,第一头牛吃掉了所有的。范围输入2-10:N,M≤10^3输入11-14:无其他约束。
⭐机构解析⭐
这个题是个有意思的暴力问题
考虑一个子问题:
一个数初始是1,每一次操作是让它乘2,要求这个数小于等于n,求最多能操作多少次
这个问题的答案比较显然是log2n次
那考虑当前的问题,考虑第一头牛,如果牛比甘蔗矮,那么它吃完甘蔗后高度乘22;如果牛比甘蔗高,此轮吃甘蔗结束。
所以这一题直接暴力模拟做到甘蔗被吃完复杂度就是对的。
时间复杂度:O(nlog2n)
知识点:暴力,时间复杂度分析
P2CowntactTracing2
农夫约翰有N排成一行的奶牛(1≤N≤3·10^5)。不幸的是,有一种疾病正在蔓延。
最初,一些奶牛开始被感染。每天晚上,受感染的奶牛都会将疾病传播给左右两侧的奶牛(如果存在的话)。一旦奶牛被感染,它就会继续被感染。
经过几个晚上,农夫约翰意识到问题已经失控,所以他对奶牛进行了测试,以确定谁生病了。找出可能开始患病的奶牛的最小数量。
INPUT FORMAT(pipe stdin):
第一行包含N,农夫约翰的奶牛数量。下一行包含一个N只有1的字符位字符串s和0
s其中1表示受感染的奶牛和0表示经过一些夜晚后未受感染的奶牛。
输出格式(pipe stdout):输出一个整数:可能开始生病的奶牛的最小数量。样本输入:511111样本输出:
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)
知识点:贪心,边界条件判断
P3Farmer John Actually Farms
农民约翰正在种植N(1≤N≤2·10^5)他的农场里种着芦笋!然而,他的一些植物有遗传差异,所以有些植物会比其他植物生长得更快。i的初始高度
第th株是hi英寸,每天之后
第th种植物生长ai英寸。
FJ比其他植物更喜欢他的一些植物,他希望一些特定的植物比其他植物高。他给你一组不同的值t1,…,tN包含0中的所有整数至N−1
他想要我第th株植物正好有ti其他比它高的植物。
找到最小天数,以便FJ的要求得到满足,或者确定这是不可能的。
INPUT FORMAT(标准输入):第一个将由一个整数T组成,表示独立测试用例的数量(1≤T≤10)。每个测试用例的第一行由一个整数N组成。第二行由N组成整数hi(1≤hi≤109)表示i的初始高度第th株(英寸)。第三行由N组成整数ai(1≤ai≤109)表示英寸数i每株植物每天都在生长。第四行由N组成不同整数ti表示FJ给你的数组。
保证N的总和在所有测试用例中,不超过2·10^5。输出格式(管道标准输出):输出T行,每个测试用例的答案在不同的行上。如果不可能,输出−1。
请注意,此问题中涉及的大尺寸整数可能需要使用64位整数数据类型(例如,C/C++中的“long-long”)。样本输入:61101027 38 101 023 610 80 127 38 91 027 78 80 127 38 81 0样本输出:0325-1-1
在第一个样本输入中,有6个测试用例。
在第一个测试案例中,只有一个工厂,因此在第0天满足条件。
在第二个测试案例中,我们需要第一个植物比第二个植物短。第1天之后,高度分别为15和13。第二天之后,高度都是23。第3天之后,高度分别为31和33,这是满足条件的第一天。
第三个和第四个测试用例与第二个类似。
在第五个测试案例中,两种植物的初始高度均为7,生长速率均为8。因此,它们总是有相同的高度,因此这种条件永远不会得到满足。
在第六个测试案例中,最初不满足条件,并且增长率相同。所以这个条件永远不能满足。
样本输入:257 4 1 10 123 4 5 2 12 1 0 3 454 10 12 7 13 1 1 4 52 4 3 1 0样本输出:47在第二个样本输入中,有2个测试用例。在第一个测试案例中,第4天之后的最终高度为19、20、21、18、16。在第二个测试案例中,第7天之后的最终高度为25、17、19、35、36。评分:输入3:N≤2输入4-5:N≤50且ai,hi≤103输入6-8:N≤103输入9-13:没有其他限制。
⭐机构解析⭐
考虑根据最终的排序结果来确定有多少条件,容易发现其实只有$n-1$个有效的不等式,即第1个小于第2个,第2个小于第3个,...
根据不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t对应的范围
最终对于所有不等式结果求出交集,如果不为空就输出最小值,否则输出-1
时间复杂度:O(n)
知识点:简单数学