USACO 2019-2020赛季题解（Jan）

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

1
Task1题目：

Bessie 和她的妹妹 Elsie 正在 Farmer John 的浆果园里采浆果。Farmer John 的浆果园里有 N 棵浆果树（1≤N≤1000）；树 i 上有 Bi个浆果（1≤ Bi≤1000）。Bessie 有 K 个篮子（1≤K≤1000，K 为偶数）。每个篮子里可以装同一棵树上采下的任意多个浆果，但是不能装来自于不同的树上的浆果，因为它们的口味可能不同。篮子里也可以不装浆果。Bessie 想要使得她得到的浆果数量最大。但是，Farmer John 希望 Bessie 与她的妹妹一同分享，所以 Bessie 必须将浆果数量较多的 K/2 个篮子给 Elsie。这表示 Elsie 很有可能最后比 Bessie 得到更多的浆果，这十分不公平，然而姐妹之间往往就是这样。 帮助 Bessie 求出她最多可以得到的浆果数量。

测试点性质：测试点 1-4 满足 K≤10。测试点 5-11 没有额外限制。

输入格式（文件名：berries.in）：输入的第一行包含空格分隔的整数 N 和 K。第二行包含 N 个空格分隔的整数  B1, B2,…, BN。 输出格式（文件名：berries.out）：输出一行，包含所求的答案。

输入样例：5 43 6 8 4 2

输出样例：8如果 Bessie 在l一个篮子里装树 2 的 6 个浆果l两个篮子里每个装树 3 的 4 个浆果l一个篮子里装树 4 的 4 个浆果那么她能够得到两个各装有 4 个浆果的篮子，总共 8 个浆果。

解析：假设 Elsie 拿的篮子里面果子数最小值为 m，那么最好情况是她拿的篮子里全都是 m 个果子。

Task 2题目：

Farmer John 欠了 Bessie N 加仑牛奶（1≤N≤1012）。他必须在 K 天内将牛奶给 Bessie。但是，他不想将牛奶太早拿出手。另一方面，他不得不在还债上有所进展，所以他必须每天给 Bessie 至少 M 加仑牛奶（1≤M≤1012）。以下是 Farmer John 决定偿还 Bessie 的方式。

首先他选择一个正整数 X。然后他每天都重复以下过程：假设 Farmer John 已经给了 Bessie G 加仑，计算 N−GX 向下取整。令这个数为 Y。如果 Y 小于 M，令 Y 等于 M。给 Bessie Y 加仑牛奶。求 X 的最大值，使得 Farmer John 按照上述过程能够在 K 天后给 Bessie 至少 N 加仑牛奶 （1≤K≤1012）。

测试点性质：测试点 2-4 满足 K≤105。测试点 5-11 没有额外限制。

输入格式（文件名：loan.in）：输入仅有一行，包含三个空格分隔的正整数 N、K 和 M，满足 K⋅M<N。

输出格式（文件名：loan.out）：输出最大的正整数 X，使得按照上述过程 Farmer John 会给 Bessie 至少 N 加仑牛奶。

输入样例：10 3 3

输出样例：2在这个测试用例中，当 X=2 时 Farmer John 第一天给 Bessie 5 加仑，后两天每天给 Bessie M=3 加仑。注意这个问题涉及到的整数规模需要使用 64 位整数类型（例如，C/C++ 中的“long long”）。

解析：很明显，可以通过二分xx的方式将极值问题转化为判定性问题。暴力的方法是直接模拟每一天还的牛奶量，复杂度O(k logn)，能过四个点。考虑优化二分的判定函数。我们将还的过程分为两部分。前一部分每次还的牛奶量都大于M，后一部分则等于M。容易发现，在前一部分的某些情况下，会有连续几天还同样的牛奶量。考虑从这个方向去优化复杂度。

Task 3题目：

Farmer John 的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。她们刚刚完成了量子物理学的博士学位，准备将这一过程搞快点。今天早上，如同往常一样，Farmer John 的 N 头编号为 1…N 的奶牛（1≤N≤105），分散在牛棚中 N 个编号为 1…N 的不同位置，奶牛 i 位于位置 pi。但是今天早上还出现了 M 个编号为 1…M 的虫洞（1≤M≤105），其中虫洞 i 双向连接了位置 ai 和 bi，宽度为 wi（1≤ai,bi≤N,ai≠bi,1≤wi≤109）。

在任何时刻，两头位于一个虫洞两端的奶牛可以选择通过虫洞交换位置。奶牛们需要反复进行这样的交换，直到对于 1≤i≤N，奶牛 i 位于位置 i。奶牛们不想被虫洞挤坏。帮助她们最大化被她们用来排序的虫洞宽度的最小值。保证奶牛们有可能排好序。

测试点性质：测试点 3-5 满足 N,M≤1000。测试点 6-10 没有额外限制。

输入格式（文件名：wormsort.in）：输入的第一行包含两个整数 N 和 M。第二行包含 N 个整数 p1,p2,…,pN。保证 p 是 1…N 的一个排列。 对于 1 到 M 之间的每一个 i，第 i+2 行包含整数 ai、bi 和 wi。

输出格式（文件名：wormsort.out）：输出一个整数，为在排序过程中奶牛必须挤进的虫洞的最小宽度的最大值。如果奶牛们不需要用任何虫洞来排序，输出 −1。

输入样例：4 43 2 1 41 2 91 3 72 3 102 4 3

输出样例：9以下是一个仅用宽度至少为 9 的虫洞给奶牛排序的可能方案：奶牛 1 和奶牛 2 使用第三个虫洞交换位置。奶牛 1 和奶牛 3 使用第一个虫洞交换位置。奶牛 2 和奶牛 3 使用第三个虫洞交换位置。

输入样例：4 11 2 3 44 2 13

输出样例：-1给奶牛们排序不需要使用任何虫洞。解析：

这题思路还是比较简单的。

注意到"最大化被她们用来排序的虫洞宽度的最小值"，很容易想到二分答案。

又因为要使"奶牛 i 位于位置 i"，所以考虑用并查集维护。

首先对所有虫洞按宽度从大到小排序，接着二分所用的虫洞宽度的最小值，
判断函数中将可使用的虫洞连接的两个位置编号合并，最后判断是否所有 错位的奶牛所在的编号 都与 她们自己的编号 在一个集合里就行了（可以用类似基础的冒泡排序的思想证明：对于一个覆盖了 一些错位的奶牛的编号及这些奶牛们所在地编号的集合（可将其转化为在一条链上），每次都可以通过若干次操作将一个编号为链首编号的奶牛传送到链首，再将其从集合中删去，多次这样操作就可以使这个集合里所有的奶牛回到原位）。

最后输出答案。

复杂度O(nlogn)

2
Task 1题目：

Bessie 正在安排前往牛尼亚的一次出差，那里有 N（2≤N≤1000）个编号为 1…N 的城市，由 M （1≤M≤2000）条单向的道路连接。Bessie 每次访问城市 i 都可以赚到 mi 哞尼（0≤mi≤1000）。从城市 1 出发，Bessie 想要赚到尽可能多的钱，最后回到城市 1。为了避免争议，m1=0。沿着两个城市之间的道路移动需要消耗一天。出差的准备工作十分费钱；旅行 T 天需要花费 C✖T2 钱（1≤C≤1000）。Bessie 在一次出差中最多可以赚到多少钱？注意有可能最优方案是 Bessie 不访问城市 1 之外的任何城市，在这种情况下结果应当为 0。

输入格式（文件名：time.in）：输入的第一行包含三个整数N、M 和 C。第二行包含 N 个整数 m1,m2,…mN。以下 M 行每行包含两个空格分隔的整数 a 和 b（a≠b），表示从城市 a 到城市 b 的一条单向道路。

输出格式（文件名：time.out）：输出一行，包含所求的答案。

输入样例：3 3 10 10 201 22 33 1

输出样例：24最优的旅行方案是 1→2→3→1→2→3→1。Bessie 总共赚到了 10+20+10+20−1✖62=24 。解析：题目意思就是给你一个有向图，你在上面走获得 mi ，没经过一个点可以获得sum2(走过的边数)*C

解决：考虑DP我们设f i,j表示第i天到达城市j的最大收益。转移很简单f i,j=max{fi-1,lasj}+mj,fi,j}}对于lasj 的处理我们只需要反向建有向边即可，答案就是max{fi,1-i2*C}但是这样i的枚举范围无法确定，但是我们发现i≤1000即可，因为max{mi}*day-day2*C≤1

Task 2题目：

Farmer John 相信他在算法设计上实现了一个重大突破：他声称他发现了一个 3SUM 问题的近似线性时间算法，这是一个有名的算法问题，尚未发现比运行速度比平方时间明显更优的解法。3SUM 问题的一个形式是：给定一个整数数组 s1,…,sm，计算不同索引组成的无序三元对 i,j,k 的数量，使得 si+sj+sk=0。为了测试 Farmer John 的断言，Bessie 提供了一个 N 个整数组成的数组 A（1≤N≤5000）。Bessie 还会进行 Q 次询问（1≤Q≤105），每个询问由两个索引 1≤ai≤bi≤N 组成。对于每个询问，Farmer John 必须在子数组 A[ai…bi] 上求解 3SUM 问题。不幸的是，Farmer John 刚刚发现了他的算法中的一个错误。他很自信他能修复这个算法，但同时，他请你帮他先通过 Bessie 的测试！

测试点性质：测试点 2-4 满足 N≤500。测试点 5-7 满足 N≤2000。测试点 8-15 没有额外限制。

输入格式（文件名：threesum.in）：输入的第一行包含两个空格分隔的整数 N 和 Q。第二行包含空格分隔的数组 A 的元素 A1,…,AN。以下 Q 行每行包含两个空格分隔的整数 ai 和 bi，表示一个询问。保证对于每个数组元素 Ai 有 −106≤Ai≤106。

输出格式（文件名：threesum.out）：输出包含 Q 行，第 i 行包含一个整数，为第 i 个询问的结果。注意你需要使用 64 位整数型来避免溢出。

输入样例：7 32 0 -1 1 -2 3 31 52 41 7

输出样例：214对于第一个询问，所有的三元对为 (A1,A2,A5) 和 (A2,A3,A4)。

解析：发现n≤5000，那么我们自然想到O(n2)O(1)回答询问。先考虑一个更简单的问题，如果f[i][j]表示在区间[l,r][l,r]中，满足k∈(l,r),a[k]+a[l]+a[r]=0的k的数量，那么我们是可以枚举左右端点，用一个桶做到O(n2)预处理f的。

那么f与最后的答案是什么关系呢？最后要求的是：在一段区间内，左右端点不强制选的方案数。这隐隐约约的有点像是f数组的一个前缀和。我们可以考虑先求出s[l][r表示左端点在[1,l]内，右端点在[1,r]内的总方案数。这就真的是f的二位前缀和了。

可以这么理解，把f[l][r]对应到平面上的一个点，那么s[l][r]就是从(1,1)到(l,r)的这个矩形中所有点的和。这样我们也就可以在O(n2)的时间内求出s。同样的，最后的答案实际上是区间左右端点都在[l,r]内总答案。对应到平面上也就是左上角为(l,l)，右下角为(r,r)的矩形中所有点的和。这样就可以通过s来O(1)求答案了。

Task 3题目：

Bessie 在一个仅允许沿平行于坐标轴方向移动的二维方阵中。她从点 (0,0) 出发，想要到达 (N,N)（1≤N≤109）。为了帮助她达到目的，在方阵中有 P（1≤P≤105）个跳板。每个跳板都有其固定的位置 (x1,y1)，如果 Bessie 使用它，会落到点 (x2,y2)。Bessie 是一个过程导向的奶牛，所以她仅允许她自己向上或向右行走，从不向左或向下。类似地，每个跳板也设置为不向左或向下。Bessie 需要行走的距离至少是多少？

测试点性质：测试点 2-5 满足 P≤1000。测试点 6-15 没有额外限制。

输入格式（文件名：boards.in）：输入的第一行包含两个空格分隔的整数 N 和 P。以下 P 行每行包含四个整数 x1、y1、x2、y2，其中 x1≤x2 且 y1≤y2。所有跳板的位置和目标位置均不相同。

输出格式（文件名：boards.out）：输出一个整数，为 Bessie 到达点 (N,N) 需要行走的最小距离。

输入样例：3 20 1 0 21 2 2 3

输出样例：3Bessie 的最佳路线为：Bessie 从 (0,0) 走到 (0,1)（1 单位距离）。Bessie 跳到 (0,2)。Bessie 从 (0,2) 走到 (1,2)（1 单位距离）。Bessie 跳到 (2,3)。Bessie 从 (2,3) 走到 (3,3)（1 单位距离）。Bessie 总共走过的路程为 3 单位距离。

解析：首先考虑 dpi。设为只使用前 i个跳板，且必须使用第 ii个，能够省下的最大距离。转移方程如下：

显然暴力转移是 O(p2) 的。考虑如何优化。

发现实际上如果把 dpi的值赋值到 (x2(i),y2(i))这个点上面，那么现在就是一个二维统计问题。

想要纯 BIT，显然需要降维。发现本质上是个可以离线的加点/矩形查询，所以考虑排序。

将所有的点的 y坐标离散化，把 (x1,y1)和 (x2,y2)分开离散化；然后我们就有了 2p个单点，然后按照 xx为第一关键字，y为第二关键字排序。然后就可以直接二维数点套路了：对于每一个(x1,y1)，可以查询区间 (1,y1)的最大值，并记录 dp值；否则就把 dp值打到 y2上面。

所以现在我们需要一个数据结构，支持单点修改、前缀查询最大值。显然可以树状数组。

最后求出 dp之后，答案就是2n−maxdp。

于是这道题就解决了~

总时间复杂度 O(plogp)，空间复杂度 O(p)。

3
Task 1题目：

Bessie 成为了一名艺术家，正在创作壁画！她现在正在创作的作品是一个高为 N 的方阵，方阵的每行都由 M 个方格组成（1≤N,M≤1000）。每个方格是空的，画了石头，或者画了水。Bessie 已经画上了包含石头的方格，包括整幅画作的边界。她现在想要将某些空的方格画上水，使得如果这幅画是真实的，其中应当不存在水的净移动。

定义从上到下第 i 行的方格的高度为 N+1−i。Bessie 想要她的画作满足以下限制：假设方格 a 画的是水。那么如果存在一条从 a 到方格 b 的路径，由高度不超过 a 的空的方格或是有水的方格组成，路径中每相邻两个方格都有一条公共边，那么 b 画的也是水。

求 Bessie 可以创作的不同作品的数量模 109+7 的余数。Bessie 可以将任意数量的空格画上水，包括不画以及全画。

测试点性质：测试点 1-5 满足 N,M≤10。测试点 6-15 没有额外限制。

输入格式（文件名：cave.in）：输入的第一行包含两个空格分隔的整数 N 和 M。以下 N 行每行包含 M 个字符。每个字符均为 '.' 或 '#'，分别表示一个空的方格和一个画有石头的方格。第一行和最后一行、第一列和最后一列仅包含 '#'。

输出格式（文件名：cave.out）：输出一个整数，为满足限制的作品的数量模 109+7 的余数。

输入样例：4 9##########...#...##.#...#.##########

输出样例：9如果第二行中的任意一个方格被画上水，那么所有空的方格必须都被画上水。否则，假设没有这样的方格画有水。那么 Bessie 可以选择画上第三行的空格组成的三个连续区域的任意子集。

所以，画作的总数等于 1+23=9。

解析：这道题如果想对了方向就很简单了。可如果一直在想如何把图给抠出一个森林就很难了。发现如果一个格子放了水，对于在这个格子及以下的高度只要有一条路径能到达另一个格子，那那个格子也会有水。不难联想到可以将各个点标上号，使用并查集来做此题。考虑对于所有水的高度（注：高度是指从下往上的高度）小于等于 h的方案数，答案应该是所有联通块的方案数的乘积。

可以发现，如果有两个联通块合并，更新的答案应该是这两个联通快的方案数的乘积。所以对于原先高度为 hh的各个联通块的方案数，可以遍历一遍第 h+1行，看有哪些联通块可以合并，然后将方案数更新，由于如果在第 h+1行放一格水，这一个联通快就都会充满水，所以还需将更新完的各个联通块的方案数加一。

那么就可以每次更新联通块，从高度为 hh 推到高度为 h+1了。为了方便可以将方案数存在祖先那里，然后从第 n 行一直推到第 1行了。总效率 O(nm) 。

Task 2题目：

Bessie 最近参加了一场 USACO 竞赛，遇到了以下问题。当然 Bessie 知道怎么做。那你呢？考虑一个仅由范围在 1…K（1≤K≤20）之间的整数组成的长为 N 的序列 A1,A2,…,AN（1≤N≤5*104）。给定 Q（1≤Q≤2*105）个形式为 [Li,Ri]（1≤Li≤Ri≤N）的询问。对于每个询问，计算 ALi,ALi+1…,ARi 中不下降子序列的数量模 109+7 的余数。AL,…,AR 的一个不下降子序列是一组索引 (j1,j2,…,jx)，满足 L≤j1<j2<⋯<jx≤R 以及 Aj1≤Aj2≤⋯≤Ajx。确保你考虑了空子序列！

测试点性质：测试点 2-3 满足 N≤1000。测试点 4-6 满足 K≤5。测试点 7-9 满足 Q≤105。测试点 10-12 没有额外限制。

输入格式（文件名：nondec.in）：输入的第一行包含两个空格分隔的整数 N 和 K。第二行包含 N 个空格分隔的整数 A1,A2,…,AN。第三行包含一个整数 Q。以下 Q 行每行包含两个空格分隔的整数 Li 和 Ri。

输出格式（文件名：nondec.out）：对于每个询问 [Li,Ri]，你应当在新的一行内输出 ALi,ALi+1…,ARi 的不下降子序列的数量模 109+7 的余数。

输入样例：5 21 2 1 1 232 34 51 5

输出样例：3420对于第一个询问，不下降子序列为 ()、(2) 和 (3)。(2,3) 不是一个不下降子序列，因为 A2≰A3。对于第二个询问，不下降子序列为 ()、(4)、(5) 和 (4,5)。解析：我们要快速求出多组询问一个区间内不下降序列的个数。（不过不同的数不超过20）设计dp方程，f[i][j]表示左端点为i，有段点值为j的方案数。g[i][j]表示右端点为i，左端点值为j的方案数。我们逆向思维，如何求出一个询问。

考虑拼接的思想，从这个询问中间的某一个点，只要知道从l[i]到mid的所有f[i][j]和mid+1到r[i]的所有g[i][j]，显然每一种要吗只在左边或只在右边（加一个空集即可），否则必定过mid，所有我们可以枚举拼接的地方，然后从l到mid左右f[l][i]之和乘上从r到mid+1所有g[r][j]（j>=i）之和就是答案。所以对于每一个询问，我们只需知道任意一个在其中的点的所有f和g数组就可以O（n）求出答案。

但是我们现在有m个询问，如何找出这些mid且保证复杂度。分治大法好。考虑二分切割。于是对于每一个l到r，我们预处理出mid的f，g数组，用数据结构总共n∗log n2。然后把过mid的所有询问处理掉。把在左侧和右侧的询问分开保证，分别分治即可。

Task 3题目：

有 N（2≤N≤2*105）个世界，每个世界有一个传送门。初始时，世界 i（对于 1≤i≤N）位于 x 坐标 i，y 坐标 Ai（1≤Ai≤109）。每个世界里还有一头奶牛。在时刻 0，所有的 y 坐标各不相同，然后这些世界开始坠落：世界 i 沿着 y 轴负方向以 i 单位每秒的速度移动。在任意时刻，如果两个世界在某一时刻 y 坐标相同（可能是非整数时刻），传送门之间就会“同步”，使得其中一个世界的奶牛可以选择瞬间传送到另一个世界。

对于每一个 i，在世界 i 的奶牛想要去往世界 Qi（Qi≠i）。帮助每头奶牛求出如果她以最优方案移动需要多少时间。每个询问的输出是一个分数 a/b，其中 a 和 b 为互质的正整数，或者 −1，如果不可能到达。

测试点性质：测试点 2-3 满足 N≤100。测试点 4-5 满足 N≤2000。测试点 6-14 没有额外限制。

输入格式（文件名：falling.in）：输入的第一行包含一个整数 N。下一行包含 N 个空格分隔的整数 A1,A2,…,AN。下一行包含 N 个空格分隔的整数 Q1,Q2,…,QN。

输出格式（文件名：falling.out）：输出 N 行，第 i 行包含奶牛 i 的旅程的时间。

输入样例：43 5 10 23 3 2 1

输出样例：7/2

7/2

5/1

-1

考虑原先在世界 2 的奶牛的答案。在时刻 2 世界 1 和世界 2 同步，所以奶牛可以前往世界 1。在时刻 7/2 世界 1 和世界 3 同步，所以奶牛可以前往世界 3。

解析：

我们考虑一下，当两个世界“同步”之时，哪种情况我们会选择传送，哪种情况则不。

显然，当这头牛的目的地比它现在的位置要高时，它应该尽量往下落速度慢的世界走，这样方便等待高处的目的地落下来，也因此只要与它同步的世界比它慢就应该传送；当这头牛的目的地比它现在的位置要低时，它应该尽量往下落速度快的世界走，以此来追赶它的目的地，也因此只要与它同步的世界比它快就应该传送。

我们可以证明，只要固定了目的地的高度关系（即高于出发点高度还是低于出发点高度），则无论时刻如何，每一个世界上的牛，都有着唯一的传送目标。

我们不妨假设我们的目的地在出发点下方，则我们应该尽量往下落速度大的世界走。我们把目的地在出发点上方的情况称作UP类，而目的地在出发点下方的情况称作DW类。则我们以下只考虑DW类。

我们考虑对于每个世界，画出它的高度h与时间t的关系。（注意下文中“斜率”一词指的是倾斜程度，即越陡峭的线斜率越大，换句话说，是正常的斜率取绝对值后的结果）

一张典型的图可能会长这样：

则在一处交点处，就意味着发生了一次“同步”，也就意味着斜率小的直线可以在DW时传送到斜率大的直线上，而斜率大的直线可以在UP时传送到斜率小的直线上。

考虑对于具体的两条直线ff和gg。它们长成这样：

因为我们考虑的是DW情况，因此我们只考虑从f到g的情况。显然，只有当g是f出发后第一条遇见的大斜率直线时，f才会转移到g；否则，即之前存在一条大斜率直线，f就一定已经在那条直线上转移过去了。

这样看来，对于同一个f，这样的g应该是唯一的，因为f出发后遇到的第一条大斜率直线是唯一的。我们把这条直线g记作dwf。这样子，如果我们已经找出了所有的dwf，则对于询问，只需要不断地跳到dwf，直到当前直线跑到了目的地的下面，即可。

但是，我们不能忽略的是，如果f不是从头开始的怎么办？换句话说，如果f不是出发点，它是从另一条直线，假设是d转移来的怎么办？这样子的话，dwf与f的交点可能在（f与d的交点）前面，也就是说不能简单地跳到dwf。

正常的情况是这样的图：

可以看到，dwf是h，但是在A处时f却跳不到h（因为f与h的交点C在A前面）。但是，细心的读者可能已经发现了，在这样的情况下，dwf 变成了h而不是原图的f！这就导致了实际上d早在D点处就已经转到了h，而不会像原来我们想象的那样到A点再转。

事实上，每个转移的目标，一定是dwf，因为如果出现了之前相交过的情况，此时的直线h一定与d的交点在A前面。也因此，直接暴力跳dwf的算法是正确的。这只是DW的情况。类似的，UP的情况也可以通过我们预处理一个upf数组出来进行转移。

此处不再赘述。我们可以写出这样的n2 做法（n2预处理，跳dw/up）。此处有代码（联系课程老师获取）期望得分35%。

我们考虑优化。如果我们画出每个位置的dw_fdwf的话，会发现实际上构成了一个（一堆）凸包：即这样：

凸包可以通过单调队列预处理出来。复杂度O(n)。但是初始化时需要进行排序，因此是O(nlogn)的。代码（实际上还是O(n2)的，只不过跳dwdw时的深度可能比较小致使能通过84%）：此处有代码（联系课程老师获取）发现所有的dw/up一定构成一棵树的结构。

因此我们只需要建出这棵树，然后在上面树上倍增就可以在 nlogn时间内找到在目的地直线上方的最后一条直线。总复杂度O(nlogn)。期望得分100%。