USACO竞赛2020-2021新赛季第一场即将开始，为方便同学了解题目思路，准备了四期《USACO题解》专题，本期进入第三期解题思路提供 2019-2020赛季各级别晋级题目题解参考，希望能为同学们提供有用的帮助。
1
Task1
题目：
Farmer John 的 N 头奶牛（1≤N≤105）站成一排。对于每一个 1≤i≤N，从左往右数第 i 头奶牛的编号为 i。Farmer John 想到了一个新的奶牛晨练方案。他给奶牛们 M 对整数 (L1,R1)…(LM,RM)，其中 1≤M≤100。他让她们重复以下包含 M 个步骤的过程 K（1≤K≤109）次：对于从 11到 M 的每一个 i：当前从左往右数在位置 Li…Ri的奶牛序列反转她们的顺序。当奶牛们重复这一过程 K次后，请对每一个 1≤i≤N 输出从左往右数第 i 头奶牛的编号。测试点性质：测试点 2 满足 N=K=100。测试点 3-5 满足 K≤103。测试点 6-10 没有额外限制。
输入格式（文件名：swap.in）：输入的第一行包含 N, M 和 K。对于每一个 1≤i≤M，第 i+1 行包含 Li和 Ri，均为范围在 1…N内的整数，其中 Li<Ri。
输出格式（文件名：swap.out）：在第 i 行输出指令序列执行了 K 次后奶牛序列中从左往右数第 i 个元素的编号。
输入样例：7 2 22 53 7
输出样例：1243576初始时，奶牛们的顺序从左往右为 [1,2,3,4,5,6,7]。在这一过程的第一步过后，顺序变为 [1,5,4,3,2,6,7]。在这一过程的第二步过后，顺序变为 [1,5,7,6,2,3,4]。再重复这两个步骤各一次可以得到样例的输出。
解析：用快速幂去维护置换根据题意，每次操作时都会将区间 (L1,R1)…(LM,RM)内的奶牛翻转一次。由于这个翻转是固定的，所以每次操作奶牛编号的置换也是固定的。我们可以预处理出一个映射 f(x)表示 x经过置换后变成什么。预处理的时间复杂度为：O(nm)此时我们只需要求 fk(x)f 即可得到答案。通过观察我们发现该置换符合结合律。举个例子：令 h 表示“先 f 后 g ”的置换。设 f={2,1,4,3} , g={3,1,2,4}。那么“先 f 后 g ”的映射就是{1,3,4,2} 。则 h 可以表示为 h(x)=g(f(x)) 。这样我们就可以使用快速幂去求 fk(x)f 。总的时间复杂度为：O(nm+nlog k)。
Task 2
题目：Farmer John 想要给他的奶牛们建造一个三角形牧场。有 N（3≤N≤105）个栅栏柱子分别位于农场的二维平面上不同的点 (X1,Y1)…(XN,YN)。他可以选择其中三个点组成三角形牧场，只要三角形有一条边与 x 轴平行，且有另一条边与 y 轴平行。FJ 可以组成的所有可能的牧场的面积之和等于多少？
测试点性质：
测试点 2 满足 N=200。
测试点 3-4 满足 N≤5000。
测试点 5-10 没有额外限制。
输入格式（文件名：triangles.in）：第一行包含 N。以下 N 行每行包含两个整数 Xi 和 Yi，均在范围 −104…104 之内，描述一个栅栏柱子的位置。
输出格式（文件名：triangles.out）：由于面积之和不一定为整数且可能非常大，输出面积之和的两倍模 109+7 的余数。
输入样例：40 00 11 01 2
输出样例：3栅栏木桩 (0,0)、(1,0) 和 (1,2) 组成了一个面积为 1 的三角形，(0,0)、(1,0) 和 (0,1) 组成了一个面积为 0.5 的三角形。所以答案为 2*(1+0.5)=3。
解析：数据量105，如果依次取枚举三角形的三个顶点，复杂度O(n3)，必然超时。题目中说只关心一条边和x轴重合，另一条边和y轴重合的三角形，那么这两条边组成了一个直角，我们先尝试枚举这个直角，看看以一个点作为直角顶点，能组成的所有三角形面积能否快速求出。
考虑如下图的样子:
X点是我们所求的点，在X的左边还有A，B，C三个点，他们纵坐标相等。在X的下方还有F，E，D三个点，他们横坐标相等。那么此时以X为直角顶点，能组成多少个三角形，他们的面积的二倍的和是多少呢。我们设两点之间的线段长度已经用小写字符标在图上，可以算出，现在的总面积是：
(a+b+c)*d+(b+c)*d+c*d+(a+b+c)*(d+e)+(b+c)*(d+e)+c*(d+e)+(a+b+c)*(d+e+f)+(b+c)*(d+e+f)+c*(d+e+f)(a+b+c)∗d+(b+c)∗d+c∗d+(a+b+c)∗(d+e)+(b+c)∗(d+e)+c∗(d+e)+(a+b+c)∗(d+e+f)+(b+c)∗(d+e+f)+c∗(d+e+f)=(a+2*b+3*c)*(f+2*e+3*d)=(a+2∗b+3∗c)∗(f+2∗e+3∗d)
这个点的值，只和与自己横坐标相同的点，和与自己纵坐标相同的点有关。而且有点类似于前缀和，可以开一个数组，去记录每个横纵坐标各自积累的和是多少。当又来了一个新点，则把这个点对应的横坐标位置的和，加上4倍与上一个点之间的距离。纵坐标位置的和同理处理，所以我们发现还需要记录每行每列出现了几个数字了。再来一个新点，就加5倍距离，以此类推。
那么，我们按照x坐标从小到大，y坐标从小到大的顺序，依次去枚举每个点i，去做一下上述处理，然后计算结果出来。但是这个计算方式只对目前我们这种方向的三角形有效，事实上三角形的直角有四个方向，分别是冲着一二三四四个象限的方向。现在我们处理的，是直角在第三象限的情况。不过并不难处理，只要改一下点的排序方式，把同样的事情做4遍就行了。
Task 3题目：Farmer John 的新牛棚的设计十分奇怪：它由编号为 1…N 的 N 间房间（2≤N≤2500），以及 N−1 条走廊组成。每条走廊连接两间房间，使得每间房间都可以沿着一些走廊到达任意其他房间。牛棚里的每间房间都装有一个在表盘上印有标准的整数 1…12 的圆形时钟。然而，这些时钟只有一根指针，并且总是直接指向表盘上的某个数字（它从不指向两个数字之间）。奶牛 Bessie 想要同步牛棚中的所有时钟，使它们都指向整数 12。然而，她头脑稍有些简单，当她在牛棚里行走的时候，每次她进入一间房间，她将房间里的时钟的指针向后拨动一个位置。例如，如果原来时钟指向 5，现在它会指向 6，如果原来时钟指向 12，现在它会指向 1。如果 Bessie 进入同一间房间多次，她每次进入都会拨动这间房间的时钟。请求出 Bessie 可能的出发房间数量，使得她可以在牛棚中走动并使所有时钟指向 12。注意 Bessie 并不拨动她出发房间的时钟，但任意时刻她再次进入的时候会拨动它。时钟不会自己走动；时钟只会在 Bessie 进入时被拨动。此外，Bessie 一旦进入了一条走廊，她必须到达走廊的另一端（不允许走到一半折回原来的房间）。测试点性质：
测试点 2-7 满足 N≤100。测试点 8-15 没有额外限制。
输入格式（文件名：triangles.in）：输入的第一行包含 N。下一行包含 N 个整数，均在范围 1…12 之内，表示每间房间初始时的时钟设置。以下 N−1 行每行用两个整数 a 和 b 描述了一条走廊，两数均在范围 1…N 之内，为该走廊连接的两间房间的编号。
输出格式（文件名：triangles.out）：输出出发房间的数量，使得 Bessie 有可能使所有时钟指向 12。
输入样例：411 10 11 111 22 32 4
输出样例：1在这个例子中，当且仅当 Bessie 从房间 2 出发时她可以使所有房间的时钟指向 12（比如，移动到房间 1，2，3，2，最后到 4）。
解析：因为题目求起点有多少个，那么我们依次枚举每个点作为起点，把它当做树根，从它出发往孩子走，看看能不能做到。每当Farmer John沿着一条线在树上走的时候，遇到的每个点时间都往前加1。考虑从树上某个结点u走到它的孩子v，那么u和v上的时间都往前加1了。也就是说要改就父子一起改，父子之间的差是不变的。既然题目中是验证是否能完成，我们不妨贪心地看，每次不停地从父子之间来回走，直到把孩子改成12，这时候根据父子差固定，我们就能知道u现在是多少。然后再去搞下一个孩子，再确定u的值。直到把所有孩子都改好，此时u固定到了某个数。回到上一层，再由父亲把u改成12。那么这么一轮下来，最后除了根，其他点都是12了。那么根如果正好是12，说明是可以的。如果根不是12呢？其实根是1也行，因为这样就最后的时候从根的最后一个孩子停下，不走回来。这时候根和最后一个孩子的时间会差一个。除了这两种情况，其他都不行。这样枚举每个点做根，每次根确定以后，一遍dfs，总的时间复杂度是O(n2)，不超时。实际写的时候，用一个c数组表示每个点现在的时间，然后用0表示12，这样每次对12取模就行了，写起来比较方便。最终目标也是把所有点调成0。
2
Task 1题目：Bessie 在过去的 M 天（2≤M≤109）内参加了 N 次（1≤N≤105）挤奶。然而，她不太记得她是什么时候参加每次挤奶了。对于每次挤奶 i=1…N，她知道这次挤奶的时间不早于第 Si 天（1≤Si≤M）。此外，Bessie 记得 C 件事，每一件可以用一个三元组 (a,b,x) 表示，表示她记得第 b 次挤奶在第 a 次挤奶之后至少 x 天。请帮助 Bessie 计算每次挤奶最早可能的日期。保证 Bessie 没有记错；换而言之，存在一种在范围 1…M 内的挤奶时间的安排能够满足她的所有记忆。
测试点性质：测试点 2-4 满足 N,C≤103。测试点 5-10 没有额外限制。
输入格式（文件名：timeline.in）：输入的第一行包含 N、M 和 C。下一行包含 N 个空格分隔的整数 S1,S2,…,SN。每个数均在范围 1…M 之内。以下 C 行每行包含三个整数 a、b 和 x，表示第 b 次挤奶在第 a 次挤奶之后至少 x 天。对于每一行，a≠b，a 和 b 在范围 1…N 内，且 x 在范围 1…M 内。
输出格式（文件名：timeline.out）：输出 N 行，为每次挤奶最早可能的日期。
输入样例：4 10 31 2 3 41 2 52 4 23 4 4
输出样例：1638第二次挤奶发生在第一次挤奶之后至少五天，所以它不可能发生在第 1+5=6 天前。第四次挤奶发生在第二次挤奶之后至少两天，所以它不可能发生在第 6+2=8 天前。
解析：给定一些如下的不等式，求任意一组不等式的解。ti -tj ≥bSolution：差分约束裸题。首先我们分析差分约束的本来的式子：ti -tj ≤b左边的这个ti -tj 就是差分。我们首先把这个不等式化简一下，成 ti ≤ tj+bt假设tj已知，我们可以推出ti的最大值只可能是tj+b，最小不限。那我们再次假设如果ti跟 tj'，tj''，tj'''都有关，我们就可以得到三个不等式，即一个不等式组：
那么ti满足所有不等式下的最大值应该是 min{tj'+b，tj''+b，tj''+b}。因为要满足所有不等式，所以必须要取最小值来满足所有的不等式。注意，我们上面提到的 j 都可以模拟成 i的前继。那么我们可以再次简化模型。假设有多个tj 是ti的前继，那么我们就可以得到一个递推式。ti=min{tj +b}那么我们看一下 SPFA 的递推式。disti=min{distj +<i，j>}那么我们只需要找一个超级原点super，然后使得他连到 i 的长度是ti即可。最后我们求一个最短路即可，输出每个 disti 。最后无解的情况只需要判断一下负环即可。那么我们看过了tj - ti ≤ b那么我们怎么转化成这一题呢？还是用上面的思路，就可以得到tj ≥ ti+b然后就可以转化成上面推导的模型就可以了 …… 注意 ≥ 和≤ 的性质不同，注意最大值和最小值。这题貌似没有判负环的地方，注意在执行差分约束造超级原点的时候长度要造为 Si。
Task 2题目：
Bessie 得到了一条一维数轴上的 N 条线段（1≤N≤105）。第 i 条线段包含满足 li≤x≤ri 的所有实数 x。定义一组线段的并为所有被至少一条线段所包含的实数 x 的集合。定义一组线段的复杂度为这组线段的并的连通区域数量。Bessie 想要求出给定的 N 条线段组成的集合的所有 2N 个子集的复杂度之和模 109+7 的值。通常你的任务是帮助 Bessie。然而这次，你就是 Bessie，没人来帮你。请吧！ 测试点性质：测试点 2-3 满足 N≤16。测试点 4-7 满足 N≤1000。测试点 8-12 没有额外限制。
输入格式（文件名：help.in）：第一行包含 N。以下 N 行每行包含两个整数 li 和 ri。保证 li<ri，且所有 li,ri 均为 1…2N 中的不同整数。
输出格式（文件名：help.out）：输出答案模 109+7 的值。
输入样例：31 62 34 5
输出样例：8所有非空子集的复杂度如下。{[1,6]}⟹ 1,{[2,3]}⟹ 1,{[4,5]}⟹ 1{[1,6],[2,3]}⟹ 1,{[1,6],[4,5]}⟹ 1,{[2,3],[4,5]}⟹ 2{[1,6],[2,3],[4,5]}⟹ 1答案为 1+1+1+1+1+2+1=8。
解析：先将所有线段按左端点升序排序。fi表示前 i 条线段的所有子集的复杂度之和。如果我们新添加了一条线段，复杂度会怎样变化呢？不选这条线段。这种情况下，复杂度没有变化，不包含这条线段的子集的复杂度仍然为fi。选这条线段。复杂度分两部分：原来的复杂度（这部分不会因为新选一条线段而减少，因为线段已经按左端点排好顺序了）和新增加的复杂度（这条线段可能不与已有线段形成连通块）。原来的复杂度仍然为 fi，而选这条线段可能会让部分子集的复杂度 +1。如果之前的线段中有 x 条线段不与当前线段相交，则选这 x 条线段的一个子集加上当前线段可以让复杂度在原来子集的复杂度基础上 +1。根据集合的知识，新增加的复杂度就是 2x 。从而得到递推式：fi=fi-1+(fi-1+2x)=2fi-1+2x 。现在的问题就是计算 x。容易看出，设第 i条线段的左端点为 li，右端点为 ri ，则 x 等于右端点小于 ri的线段数量。我们可以利用前缀和技巧来预处理所有 x 的值。
3
Task 1题目：Farmer John 的农场由 N 块草地（1≤N≤105）和 N−1 条道路组成，满足每块草地都能从任意其他草地到达。也就是说，这个农场组成一棵树。但在与不可避免地由树而生的麻烦的算法问题打了 28 年交道之后，FJ 终于认为树形的农场太复杂了。他相信在链上的算法问题更简单。所以，他的计划是将这些道路划分成若干条链，并将每条链交给他值得信任的农场工人之一负责。他不关心链的数量。然而，他希望确保这些链都尽可能长，从而不会有农场工人能够用一个渐近效率低下的算法蒙混过关！
帮助 Farmer John 求出最大正整数 K，使得道路可以被划分为一些长度至少为 K 的链。
测试点性质：在测试点 2-4 中树组成了一个 “星形”；至多一个结点的度大于二。测试点 5-8 满足 N≤103。测试点 9-15 没有额外限制。
输入格式（文件名：deleg.in）：第一行包含一个整数 N。以下 N−1 行每行包含两个空格分隔的整数 a 和 b，表示结点 a 与 b 之间有一条边。a 和 b 均在范围 1…N 内。
输出格式（文件名：deleg.out）：输出 K。
输入样例：
8
1 21 31 44 51 66 77 8
输出样例：3一种可能的划分方式如下：2−1−6−7−8,3−1−4−5。解析：给定一棵含有n个结点的树，把它分成若干条链（边只能选一次，点可以选多次），使得最短的那条链的长度最长是多少。n≤105我们首先肯定会去二分答案L那个最长链长，关键是如何判定。我们这边利用multiset这个东东来维护，它是什么讷？就是一个容器，然后加入元素会帮你从小到大排序，且允许加入重复的元素，且删增操作是log的。然后我们就有考虑如何去判定：对于一个节点u有若干条从v连过来的边，我们尽量找道两条链l1,l2连接使得l1+l2l尽量接近且大于等于L。这个还是简单易懂的。于是我们是两两配对所以u要从儿子节点v连过来并且要有一条边给自己的父亲节点fu，那么如果从儿子那儿有奇数条边那么就不管了，如果偶数条边，我们强制构造出奇数条边（即加入一条0边）。于是我们O(nlog2n)做完了这道题目，似乎还可以双指针优化到O(nlogn)。
Task 2题目：
Farmer John 的牧场可以被表示为一个 N×N 的正方形方阵（1≤N≤300），包含 1≤i,j≤N 内的所有位置 (i,j)。对于方阵内的每个方格，如果在这个位置上有一头奶牛，输入中对应的字符为 '*'，如果这个位置没有奶牛则为 '.'。FJ 相信他的牧场的美丽程度正比于两两距离相等的奶牛三元组的数量。也就是说，她们组成一个等边三角形。不幸的是，直到最近 FJ 才发现，由于他的奶牛都处在整数坐标位置，如果使用欧几里得距离进行计算，不可能存在美丽的奶牛三元组！于是，FJ 决定改用“曼哈顿”距离。形式化地说，两点 (x0,y0) 和 (x1,y1) 之间的曼哈顿距离等于 |x0−x1|+|y0−y1|。给定表示奶牛位置的方阵，计算等边三角形的数量。
测试点性质：除了样例之外有十四个测试点，依次满足 N∈{50,75,100,125,150,175,200,225,250,275,300,300,300,300}。
输入格式（文件名：triangles.in）：第一行包含一个整数 N。对于每个 1≤i≤N，第 i+1 行包含一个长为 N 的仅由字符 '*' 和 '.' 组成的字符串。第 j 个字符描述了是否在位置 (i,j) 存在一头奶牛。 输出格式（文件名：triangles.out）：输出一个整数，为所求的答案。可以证明答案可以用 32 位有符号整数型存储。
输入样例：3*...*.*..
输出样例：1有三头奶牛，并且她们组成了一个等边三角形，因为每对奶牛之间的曼哈顿距离都等于二。解析：本题解所涉及知识点仅有前缀和。
如上图，对于斜向下45°45°的直线上任意两个点（图中J,K 两点向下做等腰直角t△JHK 并延长JH和KH 做的等腰直角三角形△OHL使△OHL≅△JHK那么线段OL上任意一个整点(如图O,N,M,L)与J,K两点一定形成一个曼哈顿等边三角形证明：首先△OJK 一定是曼哈顿等边三角形（易证）O每次延OL向下移动一个点，它与J,K的曼哈顿距离不变（横+1，纵-1）所以线段OL上任意一个整点与J,K两点都可形成曼哈顿等边三角形上面的结论非常显然，我们可以根据上面的结论解决此题我们先对每一条斜向下的直线做一个前缀和，这样我们可以快速计算出一条斜线段上有多少个*点然后我们枚举一个*点（图中J）和一个距离（如图中线段JH的长）我们就可以知道其他3个点的坐标了（如图上：K,O,L）如果判断点（图中的K）也是*点就用前缀和算出线段（图中OL）上*点的数量累加答案。但是，明显我们要统计的不止斜向下45°这一条直线的一边上的曼哈顿等边三角形。所以我们把整张图翻转90°，再做一遍。同理180°和270°也要再做一遍。为了避免重复计算，我们前缀和统计答案时要减去左端点（即f(R)-f(L-1)变为f(R)-f(L)其实核心思想很简单，但我好像解释得太复杂了……时间复杂度O(4∗n 3)
Task 3题目：Bessie 得到了一条一维数轴上的 N 条线段（1≤N≤105）。第 i 条线段包含满足 li≤x≤ri 的所有实数 x。定义一组线段的并为所有被至少一条线段所包含的实数 x 的集合。定义一组线段的复杂度为这组线段的并的连通区域数量的 K 次方（2≤K≤10）。 Bessie 想要求出给定的 N 条线段组成的集合的所有 2N 个子集的复杂度之和模 109+7 的值。通常你的任务是帮助 Bessie。然而这次，你就是 Bessie，没人来帮你。请吧！有 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）。帮助每头奶牛求出如果她以最优方案移动需要多少时间。
测试点性质：
测试点 2 满足 N≤16。
测试点 3-5 满足 N≤1000, K=2。
测试点 6-8 满足 N≤1000。
对于 T∈[9,16]，测试点 T 满足 K=3+(T−9)。
输入格式（文件名：help.in）：
第一行包含 N 和 K。
以下 N 行每行包含两个整数 li 和 ri。保证 li<ri，且所有 li,ri 均为 1…2N 中的不同整数。
输出格式（文件名：help.out）：
输出答案模 109+7 的值。
输入样例：
3 2
1 6
2 3
4 5
输出样例：
10
所有非空子集的复杂度如下。
{[1,6]}⟹ 1,{[2,3]}⟹ 1,{[4,5]}⟹ 1
{[1,6],[2,3]}⟹ 1,{[1,6],[4,5]}⟹ 1,{[2,3],[4,5]}⟹ 4
{[1,6],[2,3],[4,5]}⟹ 1
答案为 1+1+1+1+1+4+1=10。
解析：
先考虑 k = 1。考虑DP。首先将所有的线段按照左端点排序，考虑 f[r]表示最右以r结尾的线段集合的连通块的数量插入一个线段[l,r]。对于右端点在[1,l-1]的每种情况，都可以使它们的连通块加1,再加到f[r]里面。对于右端点在[l,r]的每种情况，可以直接加到f[r]里面，对于右端点在[r+1,n]的f[i],要全部*2 (选当前线段或不选)。也就是要一个数据结构，支持区间*2,区间求和，显然线段树。对于k != 1, 可以考虑把它的 [0，k]次的结果分别维护，计算的时候用二项式定理合并就好了。就是对于[1,l-1]的 要把 xk -> (x+1)k再加到f[r]里，这里可以用二项式定理把[0,k]次方的结果乘上二项式系数再加起来就好。就是线段树每个点要维护各个次方的结果。
【竞赛报名/项目咨询请加微信：mollywei007】
