USACO 2019-2020赛季题解（Dec）

USACO竞赛2020-2021新赛季已开启 ，不少同学已进入最后的冲刺准备阶段，在疯狂刷刷刷刷刷刷题~~~为方便同学了解题目思路，奇思孵化准备了四期《USACO题解》专题，提供 2019-2020赛季各级别晋级题目题解参考，希望能为同学们提供有用的帮助。

1

题目1：Cow Gymnastics为了提高健康水平，奶牛们开始进行体操训练了！Farmer John 选定了他最喜爱的奶牛 Bessie 来执教其他 N头奶牛，同时评估她们学习不同的体操技术的进度。

K次训练课的每一次（1≤K≤10），Bessie 都会根据 N 头奶牛的表现给她们进行排名（1≤N≤20）。之后，她对这些排名的一致性产生了好奇。称一对不同的奶牛是一致的，如果其中一头奶牛在每次训练课中都表现得都比另一头要好。请帮助 Bessie 计算一致的奶牛的对数。输入格式（文件名：gymnastics.in）：输入的第一行包含两个正整数 K 和 N。以下 K 行每行包含整数 1…N 的某种排列，表示奶牛们的排名（奶牛们用编号 1…N进行区分）。如果在某一行中 A 出现在 B 之前，表示奶牛 A 表现得比奶牛 B 要好。输出格式（文件名：gymnastics.out）：输出一行，包含一致的奶牛的对数。输入样例：3441 2 341 3 242 1 3输出样例：4一致的奶牛对为 (1,4)、(2,4)、(3,4) 和 (1,3).题解先开两个二维数组，一个来存储数据，另一个【i】【j】来存储第i天第j头奶牛的排名，再通过暴力来求出个数。

题目2：Where Am IFarmer John 出门沿着马路散步，但是他现在发现可能迷路了！沿路有一排共 N 个农场（1≤N≤100）。不幸的是农场并没有编号，这使得 Farmer John 难以分辨他在这条路上所处的位置。然而，每个农场都沿路设有一个彩色的邮箱，所以 Farmer John 希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。每个邮箱的颜色用 A..Z 之间的一个字母来指定，所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A..Z 组成的字符串来表示。某些邮箱可能会有相同的颜色。Farmer John 想要知道最小的 K 的值，使得他查看任意连续 K 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。

例如，假设沿路的邮箱序列为 'ABCDABC' 。Farmer John 不能令 K=3，因为如果他看到了 'ABC'，沿路有两个这一连续颜色序列可能所在的位置。最小可行的 K 的值为 K=4，因为如果他查看任意连续 4 个邮箱，这一颜色序列可以唯一确定他在道路上的位置。
输入格式（文件名：whereami.in）：
输入的第一行包含 N，第二行包含一个由 N 个字符组成的字符串，每个字符均在 A..Z 之内。
输出格式（文件名：whereami.out）：输出一行，包含一个整数，为可以解决 Farmer John 的问题的最小 K 值。
输入样例：
7ABCDABC
输出样例：
4
题解：
暂且称“ABC”那样有两个（或以上）完全相等的东西为“小字符串”。可以得出，当小字符串长度=3时，k=4。所以我们就要求出最长的小字符串的长度，并且加一后输出。

题目3：Livestock Lineup
每天，Farmer John 都要给他的 8 头奶牛挤奶。她们的名字分别是 Bessie，Buttercup，Belinda，Beatrice，Bella，Blue，Betsy，和 Sue。不幸的是，这些奶牛相当难以伺候，她们要求 Farmer John 以一种符合 N 条限制的顺序给她们挤奶（1≤N≤7）。每条限制的形式为“X 必须紧邻着 Y 挤奶”，要求奶牛 X 在挤奶顺序中必须紧接在奶牛 Y 之后，或者紧接在奶牛 Y 之前。
请帮助 Farmer John 求出一种满足所有限制的奶牛挤奶顺序。保证这样的顺序是存在的。如果有多种顺序都满足要求，请输出字典序最小的一种。也就是说，第一头奶牛需要是所有可能排在任意合法奶牛顺序的第一位的奶牛中名字字典序最小的。在所有合法的以这头字典序最小的奶牛为首的奶牛顺序中，第二头奶牛需要是字典序最小的，以此类推。
输入格式（文件名：lineup.in）
输入的第一行包含 N。以下 N 行每行包含一句句子，以 "X must be milked beside Y" 的格式描述了一条限制，其中 X 和 Y为 Farmer John 的某些奶牛的名字（上文列举了八个可能的名字）。
输出格式（文件名：lineup.out）：
请用 8 行输出一个奶牛的顺序，每行输出一头奶牛的名字，满足所有的限制。如果由多种顺序符合要求，输出字典序最小的奶牛顺序。
输入样例：
3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice
输出样例：
Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup
题解：
用next_permutation函数模拟字典序从小到大的情况，然后用map存放序号，判断顺序是否符合要求就可以！

2
题目1 ：MooBuzzFarmer John 的奶牛们最近成为了一个简单的数字游戏“FizzBuzz”的狂热玩家。这个游戏的规则很简单：奶牛们站成一圈，依次从一开始报数，每头奶牛在轮到她的时候报一个数。如果一头奶牛将要报的数字是 3 的倍数，她应当报“Fizz”来代替这个数。如果一头奶牛将要报的数字是 5 的倍数，她应当报“Buzz”来代替这个数。如果一头奶牛将要报的数字是 15 的倍数，她应当报“FizzBuzz”来代替这个数。于是这个游戏的开始部分的记录为：1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16由于词汇的匮乏，奶牛们玩的 FizzBuzz 中用“Moo”代替了 Fizz、Buzz、FizzBuzz。于是奶牛版的游戏的开始部分的记录为：1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16给定 NN（1≤N≤109），请求出这个游戏中第 N 个被报的数。测试点性质：测试点 2-5 满足 N≤106。输入格式（文件名：moobuzz.in）输入包含一个整数 N。输出格式（文件名：moobuzz.out）：输出游戏中被报出的第 N 个数。输入样例：4输出样例：7第 4 个被报的数是 7。前 4 个被报的数是 1、2、4、7，因为我们在奶牛说“Moo”时就会跳过数字。解析题目大意：求从一开始第n个既不是三的倍数又不是五的倍数的数我们将所有 3 的倍数和 5的倍数去除，剩余的列表（报出的数）前段如下：1 2 4 7 8 11 13 14/16 17 19 22 23 26 28 29/31 32 34 37 38 41 43 44...设第 i 个列表中的数为fi。上面，/符号将列表分成了若干部分，其中每一个部分有 8 个数。对于每部分的最后一个数找规律，易得如下公式（kk 为正整数）：f8k = 15k-1得到这个公式后，对于 N 为 8 的倍数的情况，可以直接套用公式求解。如果不是呢？不妨设 N=8k+a（1≤a≤7），问题就转化为从 15k开始的被报出的第 a 个数。由于 a 很小，这一部分只要暴力即可。

题目2：Meetings有两个牛棚位于一维数轴上的点 0 和 L 处（1≤L≤109）。同时有 N 头奶牛（1≤N5⋅104）位于数轴上不同的位置（将牛棚和奶牛看作点）。每头奶牛 i 初始时位于某个位置 xi ，并朝着正向或负向以一个单位每秒的速度移动，用一个等于 1 或 −1 的整数di 表示。每头奶牛还拥有一个在范围 [1,103]内的重量。所有奶牛始终以恒定的速度移动，直到以下事件之一发生：如果奶牛 i 移动到了一个牛棚，则奶牛 i 停止移动。
当奶牛 i 和 j 占据了相同的点的时候，并且这一点不是一个牛棚，则发生了相遇。此时，奶牛 i 被赋予奶牛 j 先前的速度，反之亦然。注意奶牛可能在一个非整数点相遇。
令 T 等于停止移动的奶牛（由于到达两个牛棚之一）的重量之和至少等于所有奶牛的重量之和的一半的最早时刻。请求出在时刻 0…T（包括时刻T）之间发生的奶牛对相遇的总数。测试点性质：测试点 2-4 满足 N≤102，并且对所有 i，wi =1。测试点 5-7 满足 N≤102。输入格式（文件名：meetings.in）：输入的第一行包含两个空格分隔的整数 N 和 L。以下 N 行，每行包含三个空格分隔的整数wi，xi 以及 di 。所有的位置 xixi 各不相同，并且满足 0

题目3：Grass Planting S到了一年中Farmer John在他的草地里种草的时间了。整个农场由N块草地组成（1≤N≤105），方便起见编号为1…N，由N−1条双向的小路连接，每块草地都可以经过一些小路到达其他所有的草地。 Farmer John当然可以在每块草地里种不同种类的草，但是他想要使得使用的草的种类数最小，因为他用的草的种类数越多，他就需要负担更高的花费。不幸的是，他的奶牛们对选择农场上的草表现得十分苛刻。如果两块相邻（由一条小路直接相连）的草地种了同一种草，或者即使是两块接近相邻（均可由一条小路直接连向同一块草地）的草地，那么奶牛们就会抱怨她们进餐的选择不够多样。Farmer John能做的只能是抱怨这些奶牛，因为他知道她们不能被满足的时候会制造多大的麻烦。请帮助Farmer John求出他的整个农场所需要的最少的草的种类数。输入格式输入的第一行包含N。以下N−1行每行描述了一条小路连接的两块草地。输出格式输出Farmer John需要使用的最少的草的种类数输入样例1 24 32 3输出样例3解析考虑在一个点的父节点，子节点，这个点本身涂不同的颜色。而在这个点的孙节点（或祖节点）可以用同一个颜色集合来涂色。所以统计每个点的度，找到度最大的点，输出 这个点的度+1。

3
题目1：Milk PumpingFarmer John 最近为了扩张他的牛奶产业帝国而收购了一个新的农场。这一新的农场通过一个管道网络与附近的小镇相连，FJ 想要找出其中最合适的一组管道，将其购买并用来将牛奶从农场输送到小镇。这个管道网络可以用 NN 个接合点（管道的端点）来描述，将其编号为1…N（2≤N≤1000）。接合点 1 表示 FJ 的农场，接合点 N 表示小镇。有 MM 条双向的管道（1≤M≤1000），每条连接了两个接合点。使用第 i 条管道需要 FJ 花费 ci 美元购入，可以支持每秒 fi 升牛奶的流量。FJ 想要购买一条管道组成一条单一路径，路径的两端点分别为接合点 1 和 NN。这条路径的花费等于路径上所有管道的费用之和。路径上的流量等于路径上所有管道的最小流量（因为这是沿这条路径输送牛奶的瓶颈）。FJ 想要最大化路径流量与路径花费之比。保证存在从 1 到 N之间的路径。测试点性质：测试点 2-5 满足 N,M≤100。输入格式（文件名：pump.in）：输入的第一行包含 N 和 M。以下 M 行每行以四个整数描述一条管道：a 和 b（管道连接的两个不同的接合点），c（管道的花费），以及 f（管道的流量）。花费和流量均为范围 1…1000之内的正整数。输出格式（文件名：pump.out）：输出 106乘以最优解的值，并向下取整（也就是说，如果这个数本身不是整数，输出小于它的最接近它的整数）。输入样例：3 22 1 2 42 3 5 3输出样例：428571在这个例子中，仅由一条路径从1 到 N。它的流量为 min(3,4)=3=3，花费为 2+5=7。解析有两个条件，考虑先枚举 f。既然要使分母∑ci 最小，那不相当于以 c 为边权跑最短路？于是我们可以跑 dijkstra 或 spfa。不过为了达到枚举 f 起的限制作用，我们在每次松弛操作之前，要先判断这条边的限制是否大于 f。否则不把这条边计算的最短路中，因为它不满足当前限制。跑完最短路更新答案即可。这里使用堆优化的 dijkstra，时间复杂度约为 O(n2log n)，可以通过本题。实现细节①建图注意是无向图。②由于需要多次跑最短路，记得清空某些数组。③重载priority_queue的时候，符号不要写错。

题目2：Milk VisitsFarmer John 计划建造 N（1≤N≤105）个农场，用 N−1条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为更赛牛或荷斯坦牛之一。Farmer John 的 M 个朋友（1≤M≤105）经常前来拜访他。在朋友 i 拜访之时，Farmer John 会与他的朋友沿着从农场Ai 到农场 Bi 之间的唯一路径行走（可能有Ai =Bi）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。请求出每个朋友在拜访过后是否会高兴。测试点性质：测试点 2-5 满足 N≤103,M≤2⋅103。输入格式（文件名：milkvisits.in）：输入的第一行包含两个整数 N 和 M。第二行包含一个长为 N 的字符串。如果第 i 个农场中的奶牛是更赛牛，则字符串中第 i 个字符为 'G'，如果第 i 个农场中的奶牛是荷斯坦牛则为 'H'。以下 N−1行，每行包含两个不同的整数 X 和 Y（1≤X,Y≤N），表示农场 X 与 Y 之间有一条道路。以下 M行，每行包含整数 Ai ，Bi，以及一个字符 CiCi。Ai 和 Bi 表示朋友 i 拜访时行走的路径的端点，Ci 是 'G' 或 'H' 之一，表示第 i 个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。输出格式（文件名：milkvisits.out）：输出一个长为 M的二进制字符串。如果第 i 个朋友会感到高兴，则字符串的第 i 个字符为 '1'，否则为 '0'。输入样例：5 5HHGHG1 22 32 41 51 4 H1 4 G1 3 G1 3 H5 5 H输出样例：10110在这里，从农场 1 到农场 4 的路径包括农场 1、2 和 4。所有这些农场里都是荷斯坦牛，所以第一个朋友会感到满意，而第二个朋友不会。解析考虑求点u到点v的路径上是否有颜色为c的路径。我们可以考虑遍历这条路径，我们需要求这两个点的lca 然后从两个点分别遍历到lca，并且检查路径上是否有颜色为c的节点。这样很明显，复杂度是O(n2+nlogn)的，在使用树剖之后，我们做到了小常数求lca，但是这样远远不够。这个时候，我们考虑优化寻找某种颜色的节点的方法，注意到在重链上的dfn序是连续的，所以事实上我们是在每条重链上的[dfn[top[u]],dfn[u]]区间内寻找颜色为c的节点。可以将所有颜色为c的节点的dfn序存到一个vector之中，然后问题就转化成了问一个数列中，是否存在一个数，在[dfn[top[u]],dfn[u]]内。这个问题可以通过二分求大于等于dfn[top[u]]的最小的数x 判断x < dfn[u]是否成立就可以解决这个问题，这样对于每个链上做到了O(logn)的判断是否有颜色为c的节点。这样的总复杂度是O(nlog2n)。

题目3： Moortal CowmbatBessie 玩格斗游戏真牛快打已经有很长时间了。然而，最近游戏开发者发布了一项更新，这迫使 Bessie 改变她的打法。游戏总共使用 M 个按键，标记为前 M 个小写字母（1≤M≤26）。Bessie 在游戏中最喜欢的组合键是一个长为 N 的按键字符串 S（1≤N≤105）。然而，由于最近的更新，现在每种组合键必须由一些“连击”所组成，其中连击的定义为相同的按键连续按下至少 K 次（1≤K≤N）。Bessie想要修改她最喜欢的组合键，创造一个同样长为 N 的新组合键，然而这一新组合键由按键连击所组成，以适应规则的变化。Bessie 需要消耗 aij天来训练她在组合键中某个特定的位置用按键 j 来取代按键 i（也就是说，将 S 中的某个特定的字符由 i 变为 j 的代价为 aij）。注意有可能将按键 i 换成某种中间按键 k 然后再从按键 k 换成按键 j 会比直接从按键 i 换成按键 j 消耗更短的时间（或者更一般地说，可能有一条起点为 i 终点为 j 的更改路径给出了从按键 i 最终更改为按键 j 的最小总代价）。帮助 Bessie 求出她创建一个满足新要求的组合键所需要的最小天数。测试点性质：测试点 2-4 满足 N≤1000,K≤50。测试点 5-8 满足 N≤30,000,K≤50。输入格式（文件名：cowmbat.in）：输入的第一行包含 N，M 和 K。第二行包含 S，最后 M 行包含一个 M×M 的数字方阵 aijaij，其中 aij为一个范围为 0…10000的整数，并且对于所有的 i，有 aii=0。输出格式（文件名：cowmbat.out）：输出一个整数，表示 Bessie 将她的组合键改为一个满足新要求的新的组合键所需要的最小天数。输入样例：5 5 2abcde0 1 4 4 42 0 4 4 46 5 0 3 25 5 5 0 43 7 0 5 0输出样例：5在这个例子中的最优方案是将 a 改为 b，将 d 改为 e，再将两个 e 都改为 c。这总共消耗1+4+0+0=5天，最终的组合键为 bbccc。解析给定一个字符串和一个 M×M 的矩阵 a，表示可以消耗ai,j 的代价把字符 i改成字符 j，求把原字符串改成每个连续段长度都不小于 K的最小代价。n,K≤105,M≤26首先直接用原矩阵的交换方法不一定最优，拿到手先跑一遍 floyd。然后考虑 dp ，fi表示前 i个中每个连续段都≥k 的最小代价，显然有转移.fi=min{ fi+cost(i,j,c)} (j≤i−k)其中 cost(i,j,c) 表示把 [i,j]全都改成字符 cc的最小代价，这个可以前缀和预处理。观察转移，发现可以在枚举到 i 时再把 i-k的决策加进去，这样维护一个前缀 min 即可做到 O(1)转移。复杂度 O(n×M)。