国际竞赛、国际学科、标化语言、出国留学 12月USACO计算机竞赛第一次晋级赛试题解析来啦！USACO竞赛难度如何？USACO竞赛即美国计算机奥林匹克竞赛，它是一项在线计算机编程竞赛，同时也是美国国家队的选拔赛，最终晋级的学生将会参加国际信息学奥林匹克(IOI)。 2023-2024赛季UASCO竞赛12月晋级赛刚结束，很多同学不知道能不能晋级，今天老师给大家带来了12月USACO竞赛晋级赛的独家试题解析，需要历年真题的同学可以扫描文末二维码免费领取！
国际竞赛、国际学科、标化语言、出国留学 12月USACO计算机竞赛第一次晋级赛试题解析来啦！USACO竞赛难度如何？USACO竞赛即美国计算机奥林匹克竞赛，它是一项在线计算机编程竞赛，同时也是美国国家队的选拔赛，最终晋级的学生将会参加国际信息学奥林匹克(IOI)。 2023-2024赛季UASCO竞赛12月晋级赛刚结束，很多同学不知道能不能晋级，今天老师给大家带来了12月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表示经过一些夜晚后未受感染的奶牛。 输出格式（pipe stdout）： 输出一个整数：可能开始生病的奶牛的最小数量。 样本输入： 5 11111 样本输出： 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) 知识点：贪心，边界条件判断
农民约翰正在种植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”）。 样本输入： 6 1 10 1 0 2 7 3 8 10 1 0 2 3 6 10 8 0 1 2 7 3 8 9 1 0 2 7 7 8 8 0 1 2 7 3 8 8 1 0 样本输出： 0 3 2 5 -1 -1 在第一个样本输入中，有6个测试用例。 在第一个测试案例中，只有一个工厂，因此在第0天满足条件。 在第二个测试案例中，我们需要第一个植物比第二个植物短。第1天之后，高度分别为15和13。第二天之后，高度都是23。第3天之后，高度分别为31和33，这是满足条件的第一天。 第三个和第四个测试用例与第二个类似。 在第五个测试案例中，两种植物的初始高度均为7，生长速率均为8。因此，它们总是有相同的高度，因此这种条件永远不会得到满足。 在第六个测试案例中，最初不满足条件，并且增长率相同。所以这个条件永远不能满足。 样本输入： 2 5 7 4 1 10 12 3 4 5 2 1 2 1 0 3 4 5 4 10 12 7 1 3 1 1 4 5 2 4 3 1 0 样本输出： 4 7 在第二个样本输入中，有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) 知识点：简单数学
