USACO 2019-2020赛季题解（OPEN）

USACO竞赛2020-2021新赛季第一场即将开始，为方便同学了解题目思路，奇思孵化准备了四期《USACO题解》专题，本期进入第四期解题思路提供 2019-2020赛季各级别晋级题目题解参考，希望能为同学们提供有用的帮助。

1
Task1
题目：
由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们的健康。为了限制疾病的传播，Farmer John 的 N 头奶牛（2≤N≤105）决定践行“社交距离”，分散到农场的各处。农场的形状如一维数轴，上有 M 个互不相交的区间（1≤M≤105），其中有可用来放牧的青草。奶牛们想要使她们位于不同的整数位置，每个位置上均有草，并且最大化 D 的值，其中 D 为最近的两头奶牛之间的距离。请帮助奶牛们求出 D 的最大可能值。
输入格式（文件名：socdist.in）：
输入的第一行包含 N 和 M。以下 M 行每行用两个整数 a 和 b 描述一个区间，其中 0≤a≤b≤1018。没有两个区间有重合部分或在端点处相交。位于一个区间的端点上的奶牛视为在草上。
输出格式（文件名：socdist.out）：
输出 D 的最大可能值，使得所有奶牛之间的距离均不小于 D 单位。保证存在 D>0 的解。
输入样例：
5 3
0 2
4 7
输出样例：
2
取到 D=2 的一种方式是令奶牛们处在位置 0、2、4、6 和 9。
测试点性质：
测试点 2-3 满足 b≤105。
测试点 4-10 没有额外限制。
解析：本题用二分去做，我们二分 D 的值，然后再 Θ(N+M) 贪心扫一遍，如果可以放得下就往大的找，否则往小的找。我们二分的范围是从 0 到maxbi，因为最坏的情况是每头牛都紧紧挨着一起，最优的情况是一头牛在数轴原点，另一头牛在数轴的最大值处。虽然数轴是无限长的，但是在本题中，小于 00的部分对答案没有贡献，大于maxbi的部分也对答案没有贡献，所以我们假设数轴是从 0 到maxbi 的。二分的复杂度为Θ(log(maxbi ))，判断是否满足条件的复杂度为Θ(N+M)。

Task 2
题目：Farmer John 的奶牛们的早餐最爱当然是麦片了！事实上，奶牛们的胃口是如此之大，每头奶牛一顿饭可以吃掉整整一箱麦片。最近农场收到了一份快递，内有 M 种不同种类的麦片（1≤M≤105）。不幸的是，每种麦片只有一箱！N 头奶牛（1≤N≤105）中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片，奶牛会执行如下的过程如果她最爱的麦片还在，取走并离开。否则，如果她第二喜爱的麦片还在，取走并离开。否则，她会失望地哞叫一声然后不带走一片麦片地离开。奶牛们排队领取麦片。对于每一个 0≤i≤N−1，求如果 Farmer John 从队伍中移除前 i 头奶牛，有多少奶牛会取走一箱麦片。
输入格式（文件名：cereal.in）：输入的第一行包含两个空格分隔的整数 N 和 M。对于每一个 1≤i≤N，第 i 行包含两个空格分隔的整数 fi 和 si（1≤fi，si≤M，且 fi≠si），为队伍中第 i 头奶牛最喜爱和第二喜爱的麦片。 输出格式（文件名：cereal.out）：对于每一个 0≤i≤N−1，输出一行，包含对于 i 的答案。
输入样例：4 21 21 21 21 2
输出样例：2221如果至少两头奶牛留下，那么恰有两头奶牛取走了一箱麦片。 测试点性质：测试点 2-3 满足 N,M≤1000。测试点 4-10 没有额外限制。
解析：Level 1：我们很容易想到，从 00 到 N-1N−1 枚举，然后模拟奶牛选择麦片的过程。其中 hi 表示第 i 种麦片被选择的情况，ci表示第 i 头奶牛喜欢的麦片。我们从 0 到 N−1 都进行了枚举，而每次算答案的时候要遍历每一头牛，所以时间复杂度为 Θ(N2)。这里N≤105，所以我们的复杂度是不行的。因为我们要算出 NN 个答案，所以复杂度至少为Θ(N)，故我们只能优化 solve函数。Level 2：我们想想，当减少一头牛时，会发生什么情况？如果它选择了麦片，那么它的麦片可能被其他奶牛选择；如果没有选择麦片，那么答案不会改变。但是，这样还是要找一下有哪头奶牛需要这个麦片，所以优化不了多少。怎么办呢？如果我们增加奶牛，即倒着求每个答案，最后倒着输出就行了。如果增加一头奶牛，又会出现什么情况呢？如果它最喜欢的麦片没有被选择，那么它就会选它，且不影响其他奶牛；如果它最喜欢的麦片被选择，因为它的优先级比其他牛都高，所以会把其他牛的麦片“抢”过来，其他牛只能“退而求其次”。这样代码就很好写啦，递归求解即可，因为所有奶牛最多选两次，所以 solve函数的复杂度是Θ(1) 的，整个代码的时间复杂度为Θ(N)。实现方法见代码注释：ci表示第 i 头奶牛的喜好，hi表示拿走第 i 种麦片的牛的编号，resi表示移走 i-1 头牛的答案，cur 是计算答案的计数器。因为领麦片的牛越多，领到麦片的牛就越多，所以越往后面，cur就越大，故每次计算的时候 cur不需要清零。

Task 3题目：在 COWVID-19 爆发期间 Farmer John 的奶牛们为了安全进行了隔离，她们想到了一种全新的方式缓解无聊：研究高等物理！事实上，她们甚至成功发现了一种新的亚原子粒子，她们将其命名为“哞粒子”。
奶牛们正在进行一项有关 N 个哞粒子的实验（1≤N≤105）。粒子 i 的“自旋”可以用范围在 −109…109 之间的两个整数 xi 和 yi 来描述。有时两个哞粒子会发生相互作用。自旋为 (xi,yi) 和 (xj,yj) 的两个粒子之间仅当 xi≤xj 并且 yi≤yj 时会发生相互作用。在这些条件下，有可能这两个粒子中的一个会消失（另一个粒子不会发生任何变化）。在任意给定的时刻，至多只有一次相互作用会发生。
奶牛们想要知道在经过一些任意的相互作用之后剩余的哞粒子的最小数量。

输入格式（文件名：moop.in）：输入的第一行包含一个整数 N，为哞粒子的初始数量。以下 N 行每行包含两个空格分隔的整数，为一个粒子的自旋。每个粒子的自旋各不相同。
输出格式（文件名：moop.out）：输出一个整数，为经过一些任意的相互作用之后剩余的哞粒子的最小数量。
输入样例：41 00 1-1 00 -1
输出样例：1一个可能的相互作用顺序：粒子 1 和 4 相互作用，粒子 1 消失。粒子 2 和 4 相互作用，粒子 4 消失。粒子 2 和 3 相互作用，粒子 3 消失。仅留下粒子 2。 输入样例：30 01 1-1 3
输出样例：2粒子 3 不能与任何其他两个粒子相互作用，所以它必然会留下。粒子 1 和 2 中必然留下至少一个。 测试点性质：测试点 3-6 满足 N≤1000。测试点 7-12 没有额外限制。
解析：题意简述有 N 个粒子，每个粒子都有描述其自身的参数 x,y 。规定两个粒子可以相互作用当且仅当其中任意一个粒子的 x,y都分别比另一个粒子的 x,y 大。相互作用的规则是删掉其中任意一个，保留另一个。其中1≤N≤105。题目分析我们可以这样想，把所有可以相互作用的点之间连边，将输入数据表示成一张图，这张图中可能含有许多互不联通的子图。
上图是一种 N=9时的情况，拿 8,5,1,4 这一组说，我们每次可以删去其中任意一个点，而只要删掉的不是割点，我们下一次就还可以继续删。由于没有一个图可以满足所有点都是割点，所有我们每次都一定可以找到一个非割点并删去，知道只剩一个点。所以我们只需要找到其中有多少个互不联通的子图就可以了。现在我们已经可以得到一半的分了，但想要 AC就必需在小于 O(n2) )的时间内找出集合数，当然这就需要再次从题目中找特殊性质了。那么第二个技巧就是把 x,y在数轴上表示出来（看到 x,y就放到数轴上是个不错的习惯）。总结一下就是先对数据按 x 排序，如果当前的 i 的 yi≤min(y1，y2 ......yi-1 ) 因为排序后它是满足 xi ≥max(x1，x2 ......xi-1 ) 的，所以此时这个 i 不会和前面任意一个数分到一组，则它会是新的一组，那就把统计的 cnt+1就好了。所以只要O(n log(n)) 排个序再加上 O(n)边遍历边统计就完事了！：

2
Task 1题目：疲于对付他难以整平的头发，Farmer John 决定去理发。他有一排 N（1≤N≤105）缕头发，第 i 缕头发初始时长度为 Ai 微米（0≤Ai≤N）。理想情况下，他想要他的头发在长度上单调递增，所以他定义他的头发的“不良度”为逆序对的数量：满足 i<j 及 Ai>Aj 的二元对 (i,j)。对于每一个 j=0,1,…,N−1，FJ 想要知道他所有长度大于 j 的头发的长度均减少到 j 时他的头发的不良度。（有趣的事实：人类平均确实有大约 105 根头发！）

输入格式（文件名：haircut.in）：输入的第一行包含 N。第二行包含 A1,A2,…,AN。
输出格式（文件名：haircut.out）：对于每一个 j=0,1,…,N−1，用一行输出 FJ 头发的不良度。注意这个问题涉及到的整数大小可能需要使用 64 位整数型存储（例如，C/C++ 中的“long”）。 输入样例：55 2 3 3 0
输出样例：04457输出的第四行描述了 FJ 的头发长度减少到 3 时的逆序对数量。A=[3,2,3,3,0] 有五个逆序对：A1>A2,A1>A5,A2>A5,A3>A5, 和 A4>A5。 测试点性质：测试点 2 满足 N≤100。测试点 3-5 满足 N≤5000。测试点 6-13 没有额外限制。解析：题意概括：
有长为n的序列 a[1...n],∀a[i](0<i≤n),a[i]≤n。
请你按 j(j=0,1,2,...,n-1依次输出把大于 j 的 a[i]变为 j 后逆序对的个数。
思路：
这是一道很好的思考题，我们可以把 a[1..n] 按从小到大的顺序排序，对于每个 a[i]，在原序列中它前面比它大的数的个数即为其对 j=a[i]+1,a[i]+2,...,n时的答案的贡献。然后从 0 到 (n−1) 枚举 j。每次枚举先输出答案，再把答案加上等于 j 的 a[i]的贡献即可。
这个贡献可以利用树状数组维护区间和把复杂度降为 O(logn) 。具体实现方式为先往树状数组的每一位上放1。然后每遍历到一个 a[i]，将它在原序列中的位置对应的树状数组值改为 0，其贡献即为它在原序列中的位置前还有多少 1，即 query(num[i]-1),（num[i]为 a[i]在原序列中的位置）。

Task 2题目：Farmer John 的 N 头奶牛（1≤N≤2*105）每头都有一种最喜欢的颜色。奶牛们的编号为 1…N，每种颜色也可以用 1…N 中的一个整数表示。存在 M 对奶牛 (a,b)，奶牛 b 仰慕奶牛 a（1≤M≤2*105）。有可能 a=b，此时一头奶牛仰慕她自己。对于任意颜色 c，如果奶牛 x 和 y 都仰慕一头喜欢颜色 c 的奶牛，那么 x 和 y 喜欢的颜色相同。给定这些信息，求一种奶牛喜欢颜色的分配方案，使得每头奶牛最喜欢的颜色中不同颜色的数量最大。由于存在多种符合这一性质的分配方案，输出字典序最小的（这意味着你应当依次最小化分配给奶牛 1…N 的颜色）。 输入格式（文件名：fcolor.in）：输入的第一行包含 N 和 M。以下 M 行每行包含两个空格分隔的整数 a 和 b（1≤a,b≤N），表示奶牛 b 仰慕奶牛 a。同一对奶牛可能会在输入中多次出现。 输出格式（文件名：fcolor.out）：对于 1…N 中的每一个 i，用一行输出分配给奶牛 i 的颜色。
输入样例：9 121 24 25 84 66 92 98 78 37 19 43 53 4
输出样例：123112323在下图中，用粗边框圆表示的是最喜欢颜色 1 的奶牛。测试点性质：测试点 2-3 满足 N,M≤103。测试点 4-10 没有额外限制。解析：简单描述一下算法：从1~n遍历所有点，将这些点的后继节点合并;从1~n遍历所有点，将它和和它最终属于同一个点的染上同一个颜色cur，然后++cur;我们使用并查集维护节点合并，因为合并后每个点只会有一个后继节点（我们每步会把所有的后继节点合成一个点），想到在每个节点并查集的祖先处维护这个后继的编号，开一个数组存即可。合并两个节点其实就是对应合并由它和它的后继构成的两条链封装一个函数，大概像这样：
因为每个节点最多被合并一次，并查集同时加上按秩合并和路径压缩优化后，总复杂度会是O(n*α(n))也就是O(n)的。

Task 3题目：Farmer John（又）想到了一个新的奶牛晨练方案！如同之前，Farmer John 的 N 头奶牛（1≤N≤104）站成一排。对于 1≤i≤N 的每一个 i，从左往右第 i 头奶牛的编号为 i。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。给定长为 N 的一个排列 A，奶牛们改变她们的顺序，使得在改变之前从左往右第 i 头奶牛在改变之后为从左往右第 Ai 头。例如，如果 A=(1,2,3,4,5)，那么奶牛们总共进行一步。如果 A=(2,3,1,5,4)，那么奶牛们总共进行六步。每步之后奶牛们从左往右的顺序如下：0 步：(1,2,3,4,5)1 步：(3,1,2,5,4)2 步：(2,3,1,4,5)3 步：(1,2,3,5,4)4 步：(3,1,2,4,5)5 步：(2,3,1,5,4)6 步：(1,2,3,4,5)求所有正整数 K 的和，使得存在一个长为 N 的排列，奶牛们需要进行恰好 K 步。由于这个数字可能非常大，输出答案模 M 的余数（108≤M≤109+7，M 是质数）。
输入格式（文件名：exercise.in）：输入的第一行包含 N 和 M。
输出格式（文件名：exercise.out）：输出一个整数。
输入样例：5 1000000007
输出样例：21存在排列使得奶牛需要进行 1、2、3、4、5 以及 6 步。因此，答案为 1+2+3+4+5+6=21。
测试点性质：测试点 2-5 满足 N≤102。测试点 6-10 没有额外限制。解析：
发现如果循环了几次可以回到原地，当且仅当形成了一个环，假如设每个环的长度是 ai，那么可以发现 k=lcmai  ，又知道lcm 其实就是将那几个数分解质因数，然后取每个质数的最高次幂乘起来，所以我们可以想到枚举素数来做dp。我们设 f(i,j)f(i,j) 表示前 i 个素数总和为 j的所有 k 的总和，枚举第 个素数的幂进行转移，因为之前并没有用过第  个素数，所以应把上一个状态乘上 pki，所以直接有方程 f(i,j)=∑f(i−1,j− pki)× pki接着发现这个东西可以滚动数组压缩一下，于是可以省掉一维 f(j)=∑f(j− pki )× pki，倒序枚举即可，初始状态 f(0)=1，最后答案是∑f(i)。