我和“ACGO之星”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1695017759936430080

AC地下党招新了！ 进入后资格测试取前五名当管理员哦！ 传送门加入

USACO 十二月份铜组比赛题解 Subtitle: USACO December Bronze Problem Solutions 特别提醒：对于本题解的代码有任何的问题，可以在讨论区评论处留言。 第一题 - CANDY COW FEAST： 作为USACO的第一道题目，这一题就是一道普普通通的模拟题目。根据题意模拟NNN头奶牛对MMM根糖果棒的进食行为即可。我们通过创建两个变量remainBegin和remainEnd来记录每一根糖果棒剩下的部分的区间即可。 注意事项： 若奶牛的高度为HHH，且remainBegin = 5, remainEnd = 7，如果 H>=remainBeginH >= remainBeginH>=remainBegin 即表示这一头奶牛可以吃到这根糖果棒的一部分，我们就需要考虑这头奶牛是否能吃完剩下的所有部分。若 remainEnd>H>=remainBeginremainEnd > H >= remainBeginremainEnd>H>=remainBegin，则代表奶牛无法吃完糖果棒，因此奶牛的新身高应该为 H += (H - remainBegin)。否则奶牛的新身高最多也就只有 H = H + remainEnd - remainbegin + 1。并且当这根糖果棒被吃完后，应当立即停止循环以免增加不必要的运行时间。 优化： 本题通过常规的模拟方法是可以通过官方的所有测试点的，但本题可以在此代码的基础上进一步地进行优化。通过观察题目中所给定的信息和数据来看，可以推断出能吃到糖果棒的奶牛们身高比定是从低到高排列的。举例而言，如果第iii头牛的身高比第i+1i+1i+1头奶牛的身高要高，那么第i+1i+1i+1头奶牛比定永远都吃不到糖果棒。也就是说，我们可以通过不断地维护一个单调上升的数组来保存每一头奶牛的信息，确保数组以内的所有奶牛都可以吃到糖果棒。并在每一回合的开始过滤掉那些不满足要求的奶牛，这样子可以大大的降低代码的时间成本。 本题的 C++ 代码如下： 第二题 - COWNTACT TRACTING： 这道题可以被理解成一个贪心最优化问题。解题的思路是先对题干中给定的数据进行分组，将连续地且同为受感染的奶牛分为一组并命名为感染块。通过观察预处理后的若干组感染块，为了使得一开始受感染的奶牛的数量尽可能的小，则可以推断出需要让受感染的天数尽可能的大才可以。因此现在的问题就被转换成了最多需要多少天才可以将初始状态感染成最终给定的感染状态。 为了寻找出最长的感染天数，我们就需要找到长度最短的那一个感染块 - 长度最短的感染块的长度限制了奶牛们被感染的最长天数。找到最短的那个长度后就可以随之找到最长感染的天数了。这里需要分类讨论，设 lenlenlen 为长度最短的感染块的长度： 1. 如果这个长度最短的感染块在奶牛队列的头尾：天数 TTT 的计算则为：T=len−1T = len - 1T=len−1。 2. 如果这个长度最短的感染块在奶牛队列的中间：需要稍微使用一下数学思维，天数 TTT 的计算则为：T=(len−1)/2T = (len-1) / 2T=(len−1)/2。 关于 TTT 的计算的推导过程就不列举了，可以通过自己手动写几个例子来尝试一下。 在求解出最短天数之后，对于最短天数的那一个感染块来说，只需要最少1头牛就可以在最短天数内感染该感染块中的所有奶牛。那么，若其他的感染块的长度为 KKK，可以证明对于一个长度为 KKK 的感染块来说，只需要最少 ceil(K/(T×2+1))ceil(K / (T \times 2 + 1))ceil(K/(T×2+1)) 头奶牛就可以覆盖完整一个感染块。其中， T×2+1T \times 2 + 1T×2+1 表示的是在 TTT 天内1头奶牛最多可以感染其他奶牛的个数。ceil()函数用于对数字向上取整（半头奶牛要算一头奶牛才行）。 最后根据以上公式逐一计算每一个感染组所需要的最少奶牛个数即可。 本题的C++代码如下： 第三题 - FARMER JOHN ACTUALLY FARMS： 本题不保证解法最优。本题所使用的方法是模拟 + 数学常规不等式（没学过不等式的同学可以在网上搜寻一下有关不等式的一些视频观看）。首先，我们需要对FJ给定的植物数组进行一个排序，使得数组呈单调递增或单调递减的性质，方便后期进行处理。为方便起见，这里将会按照FJ对于植物的预期高度从低到高进行排序。排序完成后，可以保证第iii盆花的高度必须要小于第i+1i+1i+1盆花的高度才可以。并且，第i+2i+2i+2盆花的高度也必须要大于第i+1i+1i+1盆花。 我们根据每一盆花的信息列出两条直线方程 y1y1y1 和 y2y2y2，设 XXX 为天数。我们需要做的是使得这个 XXX 尽量的小。 1. y1=arr[i].change∗X+arr[i].heighty1 = arr[i].change*X + arr[i].heighty1=arr[i].change∗X+arr[i].height 2. y2=arr[i+1].change∗X+arr[i+1].heighty2 = arr[i+1].change*X + arr[i+1].heighty2=arr[i+1].change∗X+arr[i+1].height 若要保证 y2>y1y2 > y1y2>y1，可列出以下不等式： arr[i].change∗X+arr[i].height<arr[i+1].change∗X+arr[i+1].heightarr[i].change*X + arr[i].height < arr[i+1].change*X + arr[i+1].heightarr[i].change∗X+arr[i].height<arr[i+1].change∗X+arr[i+1].height 对该不等式进行移项操作，使得所有的未知数在同一边： arr[i].change∗X−arr[i+1].change∗X<arr[i+1].height−arr[i].heightarr[i].change*X - arr[i+1].change*X < arr[i+1].height - arr[i].heightarr[i].change∗X−arr[i+1].change∗X<arr[i+1].height−arr[i].height 因式分解不等式左半部分： X∗(arr[i].change−arr[i+1].change)<arr[i+1].height−arr[i].heightX * (arr[i].change - arr[i+1].change) < arr[i+1].height - arr[i].heightX∗(arr[i].change−arr[i+1].change)<arr[i+1].height−arr[i].height 若 arr[i].change−arr[i+1].changearr[i].change - arr[i+1].changearr[i].change−arr[i+1].change，为正数，则不需要变号： X<(arr[i+1].height−arr[i].height)/((arr[i].change−arr[i+1].change))X < (arr[i+1].height - arr[i].height) / ((arr[i].change - arr[i+1].change))X<(arr[i+1].height−arr[i].height)/((arr[i].change−arr[i+1].change)) 1. 如果不等式右半部分为负数，则证明 XXX 无论如何都没有办法满足条件。说明第i+1i+1i+1盆花永远都无法超越第iii盆花，因此输出−1-1−1即可。 2. 如果不等式右半部分为正数，则整个程序所能接受的最大天数应为该不等式得解，即第i+1i+1i+1盆花在XXX天之后就会被超越。可以求解出X的上限 upperLimit。 若 arr[i].change−arr[i+1].changearr[i].change - arr[i+1].changearr[i].change−arr[i+1].change，为负数，则不等式符号需要变换方向： X>(arr[i+1].height−arr[i].height)/((arr[i].change−arr[i+1].change))X > (arr[i+1].height - arr[i].height) / ((arr[i].change - arr[i+1].change))X>(arr[i+1].height−arr[i].height)/((arr[i].change−arr[i+1].change)) 1. 如果不等式右半部分为负数，则在任意天数之后花的高度都不会被超越，说明永远都不会被超越。 2. 如果不等式右半部分为正数，则只有等到天数大于解的时候才可以达到FJ的要求，即第i+1i+1i+1盆花要超越第iii盆花至少要经过XXX天。可以求出X的下限 lowerLimit。 只有在 lowerLimit<=x<=upperLimitlowerLimit <= x <= upperLimitlowerLimit<=x<=upperLimit 的情况下才是合法的，才能保证每一盆花的高度都是符合FJ的心理预期。但同时也会出现 upperLimit<=lowerLimitupperLimit <= lowerLimitupperLimit<=lowerLimit 的情况，因此也需要输出−1-1−1。 根据以上不等式方程模拟代码即可。 本题的C++代码如下： 本题的Python代码如下：

input: ans: 但在本题可过的一份代码 输出的是 死因：可以不用反转

1 写了万能头文件还写iostream 2 直接写输出不好吗 3 你既然要输入还赋值 4 白写一行 今天想不出来了，明天再写，还有什么欢迎评论

判断到x的根号就行

前五个点是错的，但后五个是对的，有人解释下吗？

啊啊啊真无语了！！盯代码盯半天，结果数组开小了！？ 笑西我了…… 终身警告，数组要开大啊啊啊！！！

沙发

如题

我和“ACGO之星”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1695017759936430080

ACGO欢乐赛15题目解析 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1 ZXC的探险计划 题目大意 一条数轴上有两个整数，从原点出发每次移动一格，最少几次移动能到达两个整数。 题目思路 题目本身比较好理解，只需要注意不同的情况即可。 * 初步的想法是，如果a、b两个数字在原点同侧，只需要先到距离原点近的，再到远的即可；如果a、b两个数字在原点两侧则只需要依次到达两个数字即可。 * 进而我们想到，其实无论什么情况，都可以认为是先到两者距离原点近的，在经过两点之间的长度到达另一点。如此做法就可以避免判断，简化代码，直接计算即可。 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2 子序列转换 题目大意 给定一个序列，通过对原始序列进行操作，判断最终能否变成一个不下降序列。 题目思路 首先要针对题目的核心操作进行分析，经过分析后发现，操作其实就是将选中序列[ai,aj][a_i,a_j][ai ,aj ]倒置，因此我们可以想到冒泡排序或者选择排序，当kkk大于等于222时，经过操作一定是可以达到目标的，并且如果kkk为1，序列本身成不下降序列也是满足要求的。 时间复杂度分析 该算法的时间复杂度主要就是单层循环，因此是 O(n)O(n)O(n) 的复杂度。 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3 捞薯条 题目大意 nnn箱薯条，选择nk\frac{n}{k}kn 辆卡车来运输，每辆卡车运输连续的kkk箱薯条，求在所有可行的情况下，卡车最大载重和最小载重的差值。 题目思路 根据题意，每辆卡车必须装满kkk箱，且卡车数是nk\frac{n}{k}kn ，所以卡车数辆必须是nnn的约数。所以枚举每一个iii，代表车辆装载连续的iii箱，然后求出当下情况载重的最大差值。 考虑到要多次计算连续的一段的和，所以可以使用前缀和进行优化，降低计算区间和的时间复杂度。 时间复杂度分析 该算法的时间复杂度主要集中在枚举每个nnn的约数，然后统计序列中每段连续的nnn个数，然后求极差。解决问题函数时间复杂度在有前缀和优化后几乎等于 O(n)O(n)O(n) 。 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4 或矩阵 题目大意 当前有一个矩阵MMM，需要判定当前矩阵是否存在可以通过指定方式变换而来。变换的方式是M(i,j)M_{(i,j)}M(i,j) 是由aia_iai |aja_jaj 所得。 题目思路 根据题意，如果存在一个序列aaa按照指定方式变换成目标矩阵，那我们可以分析得到如下操作: aia_iai 这个位置只会影响到M(i,j)M_{(i,j)}M(i,j) 和M(i,j)M_{(i,j)}M(i,j) ,所以我们将aia_iai 转换为二进制，并且假设每一位上都是111。 因为aia_iai 上最多只能存在格子M(i,j)M_{(i,j)}M(i,j) 和格子M(i,j)M_{(i,j)}M(i,j) 二进制下存在的1，所以把两个格子的数值依次跟aia_iai 进行&运算即可。最后验证是否可以变成指定矩阵即可。 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5 音乐先辈YUILICE 题目大意 根据序列中的aia_iai 得到2ai2^{a_i}2ai 记为AAA，再找对应的aja_jaj ，得到2aj2^{a_j}2aj 记为BBB，如果ABA^BAB=BAB^ABA,则认为找到了一组答案。 题目思路 1. 读入每个样例的乐谱数据数量 nnn。 2. 使用 map 存储每个地址 AAA 的出现次数。 3. 遍历 map，对于每个地址 AAA，如果其出现次数大于等于2，计算能够组成的按键地址数量并累加。这个循环遍历map中的每个元素（即每个不同的aia_iai 及其出现次数）。如果某个 aia_iai 出现了至少两次（i.second >= 2），那么它可以与自己组合成完整的地址。组合数可以通过组合公式 C(n, 2) = n(n-1) / 2计算，即从这些重复的 aia_iai 中选择两个不同的进行组合。 4. 特殊情况。对于 aia_iai = 111 和aja_jaj = 222，它们对应的地址 AAA = 212^121 = 222 和 BBB = 222^222 = 444 满足$ A^B$ = BAB^ABA。因此，如果输入中有 111 和 222，那么它们之间可以相互配对。配对的总数是它们出现次数的乘积。 5. 输出最终的按键地址数量。 算法核心思想是通过 map 存储地址 AAA 的出现次数，然后遍历 map 计算满足条件的按键地址数量。最后输出结果。 时间复杂度分析 该算法的时间复杂度主要取决于遍历和统计 map 的操作，因此是 O(n)O(n)O(n) 的复杂度。 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6接力长跑 题目大意 再给定序列中，找满足条件的连续数值最大为多少。 题目思路 其中连续的数字要想累加，需要满足前后两个数的奇偶性想法才可以累加。同时因为学生们能力值存在负数，所以还需要考虑是否放弃该同学即前面内容。在整个过程中全程判断是否存在更优的情况，如果存在及时记录即可。该问题属于线性动态规划经典问题变形。 我们可以设定学生状态为dp[i]dp[i]dp[i]，从而列出以下状态转移方程 * aia_iai % 2 != ai−1a_{i-1}ai−1 % 2 : dp[i]=max(a[i],dp[i−1]+a[i])dp[i] = max(a[i],dp[i-1] + a[i])dp[i]=max(a[i],dp[i−1]+a[i]) 时间复杂度分析 该算法的时间复杂度主要集中在遍历序列中每一项，因此是 O(n)O(n)O(n) 的复杂度。 代码演示

注：本文由我一个字一个字手敲上键盘的，不喜勿喷哦！ 二维数组初始化 二维数组是指每个元素都是一维数组的数组。例如，以下是一个 3x4 的二维数组： 二维数组的每个元素都可以通过它的行和列来索引。例如，1是 a 数组中第一个元素，它位于第 0 行和第 0 列。 二维数组可以用多种方式来初始化。最简单、容易的方法是使用上面所示的代码初始化。 如果你想复杂点的话就用 & 来初始化： 输入二维数组 输入二维数组可以用for循环输入，可以参考下面的代码： 模板 完

才40%之过关

就一个测试点！

这含有不文明内容，我服了这个作者啊，必须禁言删帖啊！ 所以我们不可以做这道题！！