小羊杯 Round 2 题解

预期的难度设定（同档难度按照编号排序）—— IG 有所偏离

签到题：E
较易题：CJK
中等偏易题：AFM
中等偏难题：DHI
较难题：BGL

实际通过率情况：

完成提交的队伍共计 $787$ 支，至少通过一题的队伍共计 $752$ 支，占比 $95.55\%$ 。

通过题数	1	2	3	4	5	6	7	8	9	10	11	12	13
队伍数量	$89$	$290$	$145$	$121$	$43$	$36$	$11$	$6$	$8$	$1$	$2$	$0$	$0$

Fun fact： 所有 tester 在 $3\sim 4$ 小时都没有成功的过题（我愿称之为三四魔咒），而在 $4\sim 5$ 小时通过的题都是 D 。

编号	题目标题	总通过队伍数	提交通过率（正确提交 / 总有效提交）	队伍通过率（通过队伍 / 总尝试队伍）
A	加法和异或	$95$	43.18% (95 / 220)	10.92% (95 / 870)
B	见好就收	$2$	6.06% (2 / 33)	2.11% (2 / 95)
C	是毛毛虫吗？	$360$	80.72% (360 / 446)	31.69% (360 / 1136)
D	几只毛毛虫？	$14$	73.68% (14 / 19)	20.90% (14 / 67)
E	三角形	$723$	98.91% (723 / 731)	89.26% (723 / 810)
F	能有多乱？	$58$	70.73% (58 / 82)	22.14% (58 / 262)
G	神秘的竞赛	$5$	16.67% (5 / 30)	5.43% (5 / 92)
H	体测	$16$	42.11% (16 / 38)	9.88% (16 / 162)
I	春游	$1$	9.09% (1 / 11)	4.55% (1 / 22)
J	冷酷的数	$658$	94.40% (658 / 697)	46.97% (658 / 1401)
K	友善的数	$259$	41.91% (259 / 618)	5.36% (259 / 4828)
L	我的地盘	$0$	0.00% (0 / 7)	0.00% (0 / 57)
M	光纤	$57$	68.67% (57 / 83)	24.26% (57 / 235)

题解部分

签到题

E. 三角形

题意： 三种边长可以拼成多少种三角形？

既然我们有边长的列表 $[a,b,c]$ ，我们不妨用 $(x,y,z)\ (x\leq y\leq z)$ 表示一个三角形，我们只需三重循环枚举所有可能的 $(x,y,z)$ 再判断能否构成三角形即可。

判断条件只需用最短的两条边和第三条边比较即可，即 $x+y\gt z$ 。

简评： 最好的算法是遍历。

Tester info： 这题所有 tester 都在 12 分钟内无伤通关了。（虽然题序跟正赛不一样）

较易题

C. 是毛毛虫吗？

题意： 对于一棵树，如果存在一条路径，使得不在路径上的点到路径的距离都不超过 $1$ ，则是毛毛虫。判断一棵树是否是毛毛虫。

实际上这个定义是早就出现过的，也可以搜索 Catepillar Graph 获取相应的信息。

不得不承认的是，这题是一道经典的原题，如果你善用搜索应该能找到。但本题的出现只是为了引出后一题的计数问题。

接下来回到题的解法。既然定义的核心是一条路径，我们想想这条路径是什么。

容易发现，对于一条毛毛虫而言，这条路径一定可以选为这棵树的直径。具体说明：如果选的路径两端并非度数为 $1$ 的结点，则可以进一步往外增长这条路径；如果两端度数都为 $1$ ，则这条路径一定是整棵树内最长的一条路径，即直径。

对于每一棵毛毛虫树，任选一条直径也都是满足条件的路径。

于是找到树的直径，对直径上的点进行标记，再查看是否每个不在直径上的点是否都距直径距离为 $1$ 即可。

时间复杂度为 $\mathcal{O}(n)$ 。

另解： 事实上，只要有一个点连出了三条没有公共边的长度为 $2$ 的路径，就一定返回 'NO' 。所以只需查看每个点的邻接节点中度数大于等于 $2$ 的点的个数，一旦个数不小于 $3$ ，返回 'NO' 即可。Python 等语言用这种方法就完全无需担心时限了。

简评： 引子罢了。

J. 冷酷的数

题意： 给定两个数 $x,y$ ，构造一个非 $1$ 的数与 $x,y$ 都互质。（新增了条件：在 $[2,\max(x,y)]$ 范围内找，Tester 做的是原题）

本来是没有加后面这个条件的，但是发现跟牛客寒假第一场第一题有撞车嫌疑，于是改题了。我们先聊聊原题。原范围是输入 $[1,10^4]$ ，输出 $[2,10^9]$ 。

这题有很多种不同的方法。下面简单介绍其中的三种。

构造 1： 对于一个数而言，其 $k$ 倍加 $1$ 一定和它互质（可以考虑辗转相除法）。于是直接输出 $xy+1$ 。类似地，也可以输出 $\mathrm{lcm}(x,y)+1$ 。

由于正整数关于 $x,y$ 取模的结果是循环的， $xy$ 一定是整体的循环节，于是 $xy+1$ 这个构造也可以理解为在 $1$ 这个合法构造的基础上，过了一个循环节。

构造 2： 因为 $x,y$ 的数据范围较小，所以直接输出一个大素数就行，比如 $998244353$ 。

构造 3： 如果你上面两个方法都没想出来，也可以直接枚举从 $2$ 开始的每一个数，看它是否满足条件。因为两个数的总质因子数量不多，所以一定存在一个很小的质数与已知的两数互质，于是一定能在这个数前退出循环，复杂度仍然满足要求。如果循环结束了还找不到答案，就输出 $-1$ 。

任何一种都是比较容易完成代码的。

对于新的一题： 使用上述构造 3 的思路，直接暴力找到第一个满足条件的数即可，注意提前退出。事实上也可以只使用质数来进行构造。最多只需查到第 $11$ 个质数 $31$ ，时间复杂度满足要求。

简评： 冷酷的数还是太温柔了。

K. 友善的数

题意： 输入两个正整数 $x,y$ ，输出一个最小的正整数与它们都不互质。

首先，如果 $x,y$ 中存在 $1$ ，显然无法构造，应直接输出 $-1$ 。

否则一定可以构造，至少 $xy$ 是满足条件的。

一种直接的想法是直接对 $xy$ 进行质因数分解，从小到大遍历所有因子查看是否满足要求。这种做法不是预期解，不清楚是否能够通过，也没有尝试造卡这种解法的数据。

另一种想法是进一步思考问题：不互质意味着构造的数至少有 $x$ 的一个质因子，也至少有 $y$ 的一个质因子。

如果这两个质因子不同，我们应该选择 $x$ 的最小质因子和 $y$ 的最小质因子进行相乘。

否则，我们选择的数是 $\mathrm{gcd}(x,y)$ 的质因子，也必然选择最小质因子。当然 $x,y$ 互质时，无法用这种方式构造。

上述两种方式取最小值即可。取一个数的最小质因子可以使用筛法预处理得到。

值得注意的是，输入两个质数时，需要输出两个较大的质数的乘积，结果会突破 int 的限制，所以请记得开 long long 。

时间复杂度为 $\mathcal{O}(M\log\log M+T\log M)$ ，前半部分是筛法（当然你可以选择线性筛），后半部分来源于求最大公因数。

简评： 求同存异。

Tester info： 这题差点没有一发过的 tester —— $5$ 位朋友中， $3$ 位都没有在 $\mathrm{gcd}>1$ 时取最小值而只是找了 $\mathrm{gcd}$ 的最小质因子；第一次问 DeepSeek-R1 时，它犯了同样的错误，且在我告诉它 “存在反例” 时质疑我弄错了答案。另外错了两次以上的朋友一般都输出过 $\mathrm{lcm}$ 相关的变量，但这题似乎跟 $\mathrm{lcm}$ 并没有关系。

中等偏易题

A. 加法和异或

题意： 两个 $k$ 位以内的二进制整数，给定异或结果 $n$ ，两数和的二进制表示有 $m$ 个位是 $1$ ，求满足条件的二进制整数对数。两数交换认为是相同的数对。

在 $n\neq 0$ 时，两数一定不相等，因此考虑认为 $(a,b),(b,a)$ 不相同的问题，最后除以 $2$ 即可。否则， $a=b$ ，答案无需调整。接下来不考虑 “两数交换认为是相同的数对” 这一条件。

根据一个数以及异或的结果，可以直接推出另一个数，进而可以直接推出两者的和。因此这是一个只涉及一个整数的数位 DP 问题。

但求和后的二进制数有几个 $1$ 并不能直接得到刻画。对于每一位而言，求和后是否为 $1$ 受到两个因素影响：这一位本身的求和与下一位是否发生进位。

于是设计 DP ，从最高位考虑到和的第 $i$ 位，有 $j$ 个位是 $1$ ，且下一位发生进位的状态是 $msk$ （如果发生进位则 $msk=1$ ，否则 $msk=0$ ）。

如何考虑状态转移呢？枚举第一个数在第 $i$ 位的取值是 $0$ 还是 $1$ ，以及更下一位是否发生进位，则可以很方便地确定当前位是 $0$ 还是 $1$ 且当前位是否发生进位。此时再枚举两数之和到前一位为止的 $1$ 的数量即可。

注意，加法可能进位，使得两数之和从低到高的第 $k+1$ 位是 $1$ ，因此可以考虑从第 $k+1$ 位作为 DP 起点，满足 $dp[k+1][0][0]=1,dp[k+1][1][1]=1$ 。

同时，遍历到最低位时，不可能再从后面进位，因此所有从后面一位进位的方案都是不合法的。因此最终只需输出 $dp[1][m][0]$ 即可。

时间复杂度为 $\mathcal{O}(k^2)$ 。可以类似滚动数组的实现。

另外，这题从最低位开始 DP 更符合直觉且更容易完成代码，相当于模拟了加法计算中的进位过程。想过对数对中的数添加上界来增加这种做法的难度，但感觉从低位往高位数位 DP 也是有点意思的思路，就没有进行改动。

简评： 小学就觉得加法进位超难。

F. 能有多乱？

题意： 取一个数组的子数组，求打乱后的期望逆序对数量乘以数组长度的阶乘。多次查询。

先不考虑多次查询的事。我们只考虑求一个数组打乱后的逆序对数量的期望。

考虑数组中的任意两个元素对结果的贡献。假设两个元素是 $x,y$ ，则 $x$ 在 $y$ 前的概率等于 $y$ 在 $x$ 前的概率。于是，只要这两个元素数值不同，产生逆序对的概率就是 $\frac{1}{2}$ ，也就是期望产生 $\frac{1}{2}$ 个逆序对 。而如果这两个元素相同，那么无论如何无法产生逆序对。

所以一个数组打乱后的逆序对个数的期望，等于数组中不同元素对的个数除以 $2$ 。

而接下来就是区间查询这件事。我们考虑求反面，即相同元素对的个数。

$[l,r]$ 区间内，一定是一系列完整的相等数字段 + 两端。我们只需二分找到完整段的起点和终点，利用前缀和计算这些完整段的相等元素对个数，再加上开头和结尾两段的相等元素对个数即可。

时间复杂度为 $\mathcal{O}(n+q\log n)$ 。

需要注意的还有一件事：这题的 $r-l$ 的最大数值是 $10^5$ ，因此取的子数组的长度最大是 $10^5+1$ ，需要预处理到 $10^5+1$ 的阶乘的取模的结果。

简评： 确实，能有多乱？

M. 光纤

题意： 在一个圆柱体内粒子不断在侧面反射，且反射 $n$ 次后从对侧射出。其平行于底面的速度分量方向和大小确定，求垂直于底面的速度分量的大小的取值范围。

注意到，垂直于底面和平行于底面的运动是相互独立的，因此分开考虑即可。

而垂直于底面的速度一直保持不变，而总路程为 $h$ ，因此只需计算出运动的总时间即可。

关于粒子第一次碰撞所需的时间，只需使用 $(x_0+v_xt)^2+(y_0+v_yt)^2=r^2$ 求解二次方程即可。

之后每一次碰撞后的路径到圆心的距离都相等，因此之后，相邻两次碰撞所需的时间都是一样的。实际上用时也就是上面那个二次方程的两根之差（该方程的两个解就是相邻两次碰撞的时刻）。

设第一次碰撞的时间为 $t_1$ ，后面相邻两次的碰撞之间的时间间隔为 $t_2$ ，而碰撞次数是 $n$ 次，意味着总用时在 $t_1+(n-1)t_2$ 和 $t_1+nt_2$ 之间。于是用 $h$ 分别除以两者即可得到速度的范围。

时间复杂度为 $\mathcal{O}(1)$ 。

Fun fact： 这题一开始没加 $n>1$ ，但发现第一次碰撞时间可能过短，这种情况下会导致除以这个时间的精度误差过大，加上 $n>1$ 就应该没有太大的精度问题啦！一开始也不想出几何题了，但是主队说不想做几何，我就叛逆啦！

简评： 降维打击。

中等偏难题

D. 几条毛毛虫？

题意： 毛毛虫定义同 F 题，问一棵树有多少子图是毛毛虫。

还是跟 F 一样，我们主要关注的是中间那条路径，也就是毛毛虫的直径。

这里我们强行去掉直径的两个端点。即使得我们选择的直径长度减 $2$ 。

此时特判两种情况：大小为 $2$ 的毛毛虫和直径为 $2$ 的毛毛虫。

对于前者，每条边对应一条毛毛虫，结果为 $n-1$ 。

对于后者，我们枚举直径终点，我们最终的树一定由这个点引出若干条边（边数不小于 $2$ ）。设点的度数为 $x$ ，则计数结果为 $2^x-x-1$ ，即所有方案 $2^x$ 减去选 $0$ 或 $1$ 条边的方案。

否则，去掉直径的两个端点后，还有一条长度为正整数的路径。而对于路径上的每一点，有多少种扩充成毛毛虫的方法呢？

对于路径的端点，我们至少得往外多连一条边。设度数为 $x$ ，则非路径上的边的数量为 $x-1$ ，因此总方案数为 $2^{x-1}-1$ 。

对于路径上非端点的点，其可以任意往路径外连边。设度数为 $x$ ，则路径外的边有 $x-2$ 条，因此总方案数为 $2^{x-2}$ 。

对于每条路径，我们需要对上述结果乘积后求和，最后再对所有路径求和。

容易想到树上 DP 。既然我们前面已经提到了只考虑中间的一条 “关键路径” ，我们就在有根树上，计算从 $u$ 位置往下的所有 “关键路径” 能长成多少种不同的毛毛虫段——我们称为 “段” 。（即从 “关键路径” 从子树中的一个位置开始，到 $u$ 尚未结束的这部分的方案数）

这件事的维护可以使用树上 DP ，将子结点的结果乘以当前结点作为 “路径上非端点的点” 的方案数，再加上子结点作为 “路径的端点” 的方案数，即可完成转移。

接下来考虑毛毛虫的计数，考虑每一条毛毛虫对应的 “关键路径” 。

如果它的两个端点一个是另一个的祖先，则设两个端点为 $u,v$ ，且 $u$ 是 $v$ 的祖先，则此时考虑 $u$ 的也是 $v$ 祖先的结点 $u'$ ，我们可以根据 $u'$ 的毛毛虫 “段” 数，乘以 $u$ 点的可选方案数，进而得到这种路径的方案总数。

否则，两个端点 $u,v$ 的 LCA 不为 $u,v$ 中任何一个，设 LCA 为 $l$ ，则相当于 $l$ 出发选择了两个子结点，两个子结点对应的毛毛虫 “段” 数相乘（需要加上子结点作为 “关键路径” 端点的情况），再乘以 $l$ 本身作为 “路径上非端点的点” 的方案数。最后这部分可以一起乘，前面部分相当于对于任意两个子结点相乘后再相加。这件事可以这么算：

$\sum\limits_{1\leq i\lt j\leq k}a_ia_j=\sum\limits_{i=1}^k a_i\left(\sum\limits_{j=1}^{i-1}a_j\right)$

在遍历子结点时维护一个前缀和即可。

时间复杂度为 $\mathcal{O}(n)$ 。

抱歉这题没有提供较大的样例，主要是因为想在样例解释中提供每个子毛毛虫。如果想找到一棵树进行 debug ，可以使用前一问中的第二棵树，那棵树除了树本身都是毛毛虫，因此只需计算连通块种类数量再减去 $1$ 就行。

Fun fact： 本来毛毛虫系列还有一题，是计算不同形态的有 $n$ 个结点的毛毛虫数量，但计算完成后发现 OEIS 上直接就能搜到，于是放弃了。感兴趣的朋友可以自己推一推，大概需要根据对称性去重来计数。

简评： 表面上看着人畜无害的。

H. 体测

题意： 给定一个排好序的数组 $[0,a_1,\dots,a_{n-1},l]$ ，在数组中插入最少个数的 $(0,l)$ 范围内的整数，使得数组中两数之差可以覆盖 $a,b,c$ 中的每一个数。

应该是中等题里比较容易意识到可做的一题，也容易以为实现十分容易进而被识别为简单题，但本题相当容易得到 WA 。

题目中给了我们一个提示：我们有时候可能在添加一个数字后同时满足多个要求。

而我们总共需要满足三个需求。考虑需求是如何满足的。注意到 $3=1+2=1+1+1$ ，因此可以将 $3$ 个要求捆绑为一组；也可以将 $3$ 个需求分为两组，一组 $1$ 个需求，一组 $2$ 个需求，每一组的需求一起满足；也可以选择每一个需求都单独满足。

因此需要完成以下几个步骤：

满足 $1$ 个需求：直接检查是否有两个数差是满足需求的，如果有，返回 $0$ ，否则返回 $1$ 。
满足 $2$ 个需求：两个条件同时满足，只能是存在 $a+b$ 或 $|a-b|$ 的间隔。（或者拆为 $1+1$ ，这种情况已经判断过了，不作考虑。）注意两个数间隔 $|a-b|$ 时候不总能满足要求，需要构造的新点仍在 $(0,l)$ 范围内。
同时满足 $3$ 个需求。一定有一个已有的点作为某一段的起点 / 终点。从这个点出发进行 DFS ，可以确定剩余三个要找的点的所有可能，只需检查每一种可能下，与已有的数字重合的个数即可。

枚举所有分割方式，取最小答案即可。时间复杂度为 $\mathcal{O}(n) / \mathcal{O}(n\log n)$ ，看你判断过程的复杂度。上述状态搜索中，实际的不同状态不会超过 $(3!)^2\times 2^3=288$ 种，是较大的一个系数。

Fun fact： 本次小羊杯题序原来是随机的，这题被随机到了 A 的位置，为了防止大家起手就做这道容易写假的题，就和签到题互换了位置。希望有效提升了大家的做题体验并降低大家的罚时。

简评： 又一个表面上看着人畜无害的。这一切都是包容的代价。（你猜猜这题为啥给了 10 秒.jpg）

Tester info： $5$ 位测试者中 $4$ 位积极避开了这道题，另一位朋友因为这题卡了 $3$ 小时（使用了分类讨论的做法），最终纯分类讨论达到了约 $55$ 毫秒的优秀用时，让我们向其致以敬意！

#include <bits/stdc++.h>

using namespace std;

int t;
int n, a, b, c, m;
int p[100005];

bool check1(int x, int L = 0, int R = m) {
	if (x <= 0)
		return false;
	for (int l = 0, r = 0; r <= n; r++) {
		while (p[r] - p[l] > x)
			l++;
		if (p[r] - p[l] == x && (L <= p[r] || p[r] <= R))
			return true;
	}
	return false;
}

bool check2(int x, int y, int L = 0, int R = m) {
	for (int i = 0, l = 0, r = 0; i <= n; i++) {
		while (p[i] - p[l] > x)
			l++;
		while (r <= n && p[r] - p[i] < y)
			r++;
		if (p[i] - p[l] == x && r <= n && p[r] - p[i] == y && L <= p[i] && p[i] <= R)
			return true;
	}
	return false;
}

bool check3(int x, int L = 0, int R = m) {
	if (x <= 0)
		return false;
	for (int l = 0, r = 0; r <= n; r++) {
		while (p[r] - p[l] > x)
			l++;
		if (p[r] - p[l] == x && L <= p[r] && p[r] <= R)
			return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for (cin >> t; t--; ) {
		cin >> n >> c >> a >> b >> m;
		for (int i = 0; i <= n; i++)
			cin >> p[i];
		vector<int> v;
		if (!check1(a))
			v.push_back(a);
		if (!check1(b))
			v.push_back(b);
		if (!check1(c))
			v.push_back(c);
		if (v.size() < 2)
			cout << v.size() << '\n';
		else if (v.size() == 2)
			cout << (check1(v[0] + v[1]) || check1(v[1] - v[0], v[1], m - v[0]) ? 1 : 2) << '\n';
		else if (check2(v[1] - v[0], v[2] - v[1], v[1], m) || check2(v[2] - v[1], v[1] - v[0], 0, m - v[1]) ||
				 check2(v[0] + v[1], v[2] - v[1]) || check2(v[0] + v[1], v[2] - v[0]) || check2(v[0] + v[2], v[1] - v[0]) ||
				 check2(v[2] - v[1], v[0] + v[1]) || check2(v[2] - v[0], v[0] + v[1]) || check2(v[1] - v[0], v[0] + v[2]))
			cout << 1 << '\n';
		else if (check1(v[0] + v[1]) || check1(v[1] - v[0], v[1], m - v[0]) ||
				 check1(v[0] + v[2]) || check1(v[2] - v[0], v[2], m - v[0]) ||
				 check1(v[1] + v[2]) || check1(v[2] - v[1], v[2], m - v[1]) ||
				 check1(v[0] + v[2] - v[1], v[2], m - (v[1] - v[0])) || check1(v[1] + v[2] - v[0]) || v[0] + v[1] == v[2] ||
				 check3(v[0] + v[1] - v[2], v[0], m - (v[2] - v[0])) || check3(v[0] + v[1] - v[2], v[1], m - (v[2] - v[1])) ||
				 check1(v[2] - v[0] - v[1], v[2], m - v[0] - v[1]) || (v[0] + v[1] <= m - v[2] && check1(v[0] + v[1] + v[2])) ||
				 check3(v[2] - v[0] - v[1], v[2] - v[1], m - v[1]) || check3(v[2] - v[0] - v[1], v[2] - v[0], m - v[0]) ||
				 check1(v[0] + v[1] - v[2], v[0] + v[1], m - v[2]))
			cout << 2 << '\n';
		else
			cout << 3 << '\n';
		
	}
	return 0;
}

I. 春游

题意： 目前有一些人在无向连通图的某些结点上，每条边从 $t_i$ 时刻才能同行且单位时间通行一人，问所有人都到达 $1$ 结点的最早时间。

假设每条边没有通行时间的限制，此时是一个可以用网络流解决的经典问题。下面进行简单说明——

可以证明，最早到达时间不超过 $n+m-2$ 。

具体而言，我们可以去掉边，使得图仍然保持连通，直到图变成一棵树。在删边的过程中，到达 $1$ 的用时是单调不减的（因为可行的路径变少了）。
按照与结点 $1$ 的距离进行排序，越近的越先行动。我们让每一个人一旦出发就不停下，求最晚的出发时间。可以用数学归纳法证明第 $i$ 个人的出发时间不晚于 $i-1$ ，因此第 $n$ 个人出发时间不晚于 $n-1$ ，因此至多需要 $(n-1)+(m-1)$ 的时间就能所有人聚集到结点 $1$ 。

进一步地，考虑二分最早集合时间。对于每个集合时间 $T$ 可以使用网络流检查。

我们对图上的每个点 $u$ 在不同时刻 $t_i$ 设立一个网络流上的结点 $(u,t_i)$ 。

则因为点待在原地没有限制，因此 $(u,t_i)$ 可以以无限流量流到 $(u,t_i+1)$ ，而对于任意一条边 $(u,v)$ ，都可以让一个人在单位时间内从 $u$ 走到 $v$ ，因此连边 $(u,t_i)\to(v,t_i+1)$ ，容量为 $1$ 。

但一条边我们既让 $u$ 到 $v$ ，又让 $v$ 到 $u$ ，会产生矛盾，即一条边上同时有两人通行吗？答案是否定的，因为同一时刻如果两个方向都走了，就相当于都没走（有点废话了）。

只需在最后时刻汇流到 $(1,T)$ 即可，流量必须等于总人数。

于是我们解决了无通行时间限制的问题。

有通行时间限制的话，我们的集合时间就可能很晚了。

我们仍然考虑使用二分。但这样我们就不能建一个完全的 $0$ 时刻到 $T$ 时刻的网络流，怎么办呢？

直觉是，如果一条边相较于 $T$ 时刻很早就开放了，那么它其实早开放也没用，不如干脆等到 $T-value$ 再开放也来得及（ $value$ 是一个设定的值，表示这条边最长实际有效的使用时间）。

利用这一点，我们将网络流从 $(u_i, T-value)$ 到 $(u_i,T)$ 进行建图，即可完成，且点数不会过多。

这里， $value$ 大概是 $\mathcal{O}(n+m)$ 的量级，从直觉上解释，因为可以先花 $\mathcal{O}(n+m)$ 的时间通过那些有效时长较长的边走到各自的中转站，再用 $\mathcal{O}(n+m)$ 的时间走剩余有效时长较短的边。（事实上，由于出题人不太想得清楚极限情况，这里只要是 $\mathcal{O}(n+m)$ 量级的基本都可以过）于是网络流中结点个数为 $\mathcal{O}((n+m)m)$ ，边数为 $\mathcal{O}((n+m)(m+k))$ 。

值得注意的是这个图流量很小，是 $\mathcal{O}(n)$ 的，所以网络流复杂度只需考虑 $\mathcal{O}(n)$ 轮在残留网络中找源到汇的路径，因此可以控制在 $\mathcal{O}(n(n+m)(m+k))$ 。

再搭配二分，时间复杂度需多一个 $\log$ 。总复杂度为 $\mathcal{O}(n(n+m)(m+k)\log M)$ 。

这里的 $\log M$ 可以进一步优化。我们可以找到使得整个图的 “最小生成树”，则 “最小生成树” 中最大边权的边对应的时间 $+n+m-2$ 时间内，一定能完成任务（这里的 “最小生成树” 指将 $1$ 和目标点相连的最大边权最小的树）；而如果时间小于这个最大边权，一定不满足要求。因此我们将实际答案缩小到一个 $\mathcal{O}(n+m)$ 长度的区间，这样这个 $\log M$ 就被优化为 $\log(n+m)$ ，但这步优化不是必要的。

由于出题人没有什么网络流题目的出题经验，所以数据可能不够强，主要只卡了二分上下界出错的事情，请多包涵。

简评： 希望大家有空多出去走走！

Tester info： 有测试者用随机算法随机了 $60$ 次，但是被一个神秘 case 单防了；有测试者这题因为使用的网络流板子太慢所以 TLE 了，比较可惜（但同时回推时间没有达到 $n+m$ 所以也没有那么可惜），但因为这题 case 数量太多，所以就并没有办法开再大的时限啦！

较难题

B. 见好就收

题意： 已知一枚硬币正面朝上的概率为 $\frac{p}{q}$ ， $n$ 次查询在 $y$ 次反面前扔出 $x$ 次正面的概率。

单次查询如何计算结果呢？

事实上，我们可以强行让小羊扔 $x+y-1$ 次硬币，如果扔到了 $x$ 次及以上的正面，我们就拿第 $x$ 次正面前所有抛硬币结果作为真实结果。发现这跟原命题概率一致。

因此，要求的就是 $x+y-1$ 次抛硬币中，至少抛出 $x$ 次正面的概率。

用二项式定理计算对应结果，为 $\sum\limits_{i=x}^{x+y-1}C_{x+y-1}^i\left(\frac{p}{q}\right)^i\left(1-\frac{p}{q}\right)^{x+y-1-i}$

直接使用二项式定理计算这个概率是 $\mathcal{O}(M)$ 的，并不符合要求。因此需要考虑多次查询之间存在的联系。

不妨设 $a$ 次抛硬币中，至少抛出 $b$ 次正面的概率为 $P(a,b)$ 。

注意到 $P(a,b-1),P(a,b+1)$ 上面的求和式都只跟 $P(a,b)$ 的差了一项，因此都可以在知道 $P(a,b)$ 的情况下 $\mathcal{O}(1)$ 计算。

接下来考虑 $P(a+1,b)$ ，即 $a+1$ 次抛硬币有至少 $b$ 次正面朝上。

考虑前 $a$ 次，如果至少有 $b$ 次正面朝上，则概率为 $P(a,b)$ ；否则，要 $a+1$ 次抛硬币有 $b$ 次正面朝上，只能是前 $a$ 次有 $b-1$ 个正面朝上且又抛出了正面，因此有：

$P(a+1,b)=P(a,b)+C_a^{b-1}\left(\frac{p}{q}\right)^{b-1}\left(1-\frac{p}{q}\right)^{a-b+1}\times\frac{p}{q}$

类似地，也可以得到 $P(a-1,b)$ 和 $P(a,b)$ 的关系。（这个式子也可以通过组合数的计算得到，但相对麻烦且需要比较好的数学观察）

把 $(a,b)$ 视为一个二维平面上的点，则在这个平面上，上下左右移动一个单位的计算成本都是 $1$ ，我们要求这个平面中 $n$ 个位置的数值。这就是莫队的思想，因此直接使用莫队算法即可。注意我们输出的变量不是概率，还要乘以 $q^{x+y}$ 。（抱歉是我偷懒了，我不想解释分数的取模的含义）

当然，这题到这里还没有结束所有的坑点。

首先，这题涉及到组合数的计算，而组合数取模的数可能是一个不大的质数，因此分子分母可能都是这个质数的倍数。

此时，我们可以预处理每个数含该质因子的次数并求前缀和，这样我们就能得到一个数的阶乘中这个质因子的出现次数，进而得到分子、分母中该因子的出现次数以判断取模结果是否为 $0$ 。

对于剩余的组合数，如何计算取模结果呢？我们直接把 $n!$ 中所有 $mod$ 因子都去掉求出取模结果，得到最大的数 $M$ 的阶乘去掉质因子 $mod$ 后关于 $mod$ 的取模结果，再求逆元得到 $\frac{1}{M!去掉质因子mod}$ ，再往回推即可。后半部分的逻辑类似于常规阶乘的逆元的求法 $\frac{1}{n!}=(n+1)\times \frac{1}{(n+1)!}$ 。

最后，使用莫队时，容易出现 $C_a^b$ 不合法的情况（如 $b\lt0$ 或 $b\gt a$ ），保证答案正确的一种处理方式是，先尽可能让 $a$ 变大， $b$ 变小，再执行 $a$ 变小， $b$ 变大的操作。这样可以保证中间的每一步都是合法的。

时间复杂度为 $\mathcal{O}(n\log n+M\sqrt{n})$ 。

上面涉及到的一个经典问题是求 $C_a^b\bmod x$ ，这个问题也可以简单想下咋写比较好。

简评： 小羊想见好就收，但为了做出题我们偏不让他见好就收。

G. 神秘的竞赛

题意： 有 $n$ 道题，做完一题得 $10^6$ 分，每一题要 $a_i$ 单位时间。总共 $T$ 单位时间。在 $[l,r]$ 时间内，每一次成功提交有奖励分 $1$ 分，而每做一道题就立即交，问最后最高的总得分。

我们需要关注到几件事情：

我们题数为王。不然我们基础分少了一题的话，附加分也救不回来。
在题数相同的情况下，我们总选择最简单的题来做，因为这更有利于我们分配时间。
我们没必要在某一个非整数的时刻开始做题——往前往后都不影响答案。
我们可以从一个时刻开始，连续地做题——奖励时间我们不应该浪费，如果没用满可以平移前面的做题动作 / 后面的做题动作。而非奖励时间可以任意平移不影响答案，因此干脆平移成一段连续的时间做题。

于是我们先将题目按照用时升序排序，选取最长的和不超过 $T$ 的前缀。这就是我们真正要选择去做的题。接下来我们认为 $n$ 是我们实际要做的题数， $a_i$ 是这些题分别需要的用时。

而我们多余的时间总共有 $T-\sum\limits_{i=1}^n a_i$ ，因此我们可以选择开头就休息 $\left[0,T-\sum\limits_{i=1}^n a_i\right]$ 中的一个整数时间，再连续做题。

那么，怎么分配题目和做题顺序呢？

考虑最后一次得到附加分的时刻。在这个时刻之前，为了得到最多的附加分，我们应该先做用时长的题，再做用时短的题，这样可以把前面没有奖励分的时间尽快用完。

于是，可以将题目按照所需时间逆序排序，根据逆序序列的一个子序列，安排完所有拿附加分的事项，最后再任意排列剩余的所有题目。

后半部分不影响答案，因此，只考虑附加分前的部分，这部分可以使用背包 DP 。下面的讨论已经将题目按照用时降序排列。

假设考虑到第 $i$ 题时，用时 $t$ 的最大附加分为 $dp[i][t]$ 。考虑第 $i+1$ 道题，如果做了的话，总用时为 $t+a_{i+1}$ ，因此 $dp[i+1][t+a_{i+1}]$ 可以更新为 $dp[i][t]+[l\leq t+a_{i+1}\leq r]$ 。

但这样做的复杂度仍然有 $\mathcal{O}(nT)$ ，无法通过本题。

但注意到 $\sum\limits_{i=1}^n a_i\leq T$ ，因此不同的 $a_i$ 不超过 $\mathcal{O}(\sqrt{T})$ 个，我们将这些 $a_i$ 进行合并。

我们同时考虑一批相同用时的题目进行状态转移，就可以用单调队列优化这个类背包 DP 的转移过程。假设是从 $i$ 位置转移到 $j$ 位置，则新增的数量就是 $i+1$ 到 $j$ 之间完成题目得到附加分的时刻数量，这可以拆解为 $j$ 之前完成题目得到附加分的时刻数量减去 $i$ 之前完成题目得到附加分的时刻数量。

因此单调队列只需维护此前 $i$ 位置的 DP 数值减去 $i$ 之前完成题目得到附加分的时刻数量的最大值即可。

时间复杂度为 $\mathcal{O}(T\sqrt{T}+n)$ 。

简评： 要是小羊能有点策略，水题做完一起交就好了。

Tester info： 有测试人员就差最后发现 $\sum\limits_{i=1}^n a_i\leq T$ 意味着不同的 $a_i$ 数量不多了，非常可惜啊！本题本来还加了限制 $\sum a_i\leq T$ ，一旦这个条件直接给出了就很容易被提示到发现端倪了！

L. 我的地盘

题意： 一个 $n\times m$ 的矩阵，按照一个规则，将部分格子进行染色，染的颜色单调不减，求每一时刻的最大连通分量的大小。

本题实际上是按照不同的颜色分别考虑。

对于某一种颜色，实际上经历了以下过程：先可能被更小的数字染色，再有一些新格子变成当前颜色，最后又有一些格子被染为更大的颜色。

整体只有三次单调的变化。先减后增再减。

而求连通块大小的常见做法是使用并查集，并查集在增的时候更好用，于是考虑以前两轮变换的中间时刻为起点，往前往后推断前两轮变换的每一个时刻该颜色连通块的最大大小；同时从最终时刻开始，往前递推，得到第三轮变换的每一个时刻该颜色连通块的最大大小。

这样，格子在三段中，按照对应的方向进行遍历，就是不断新增的了，维护最大连通块就手到擒来了。

注意到，涉及到第 $i$ 种颜色的格子数量等于原矩阵中 $i$ 颜色的格子数量加上涉及到第 $i$ 种颜色的操作数量。而这个变量关于 $i$ 求和是 $\mathcal{O}(nm+q)$ 的，因此，总共需要考虑的格子的数量是不会超标的。

但这也意味着我们需要对于每个颜色进行维护时细致操作，保证维护的并查集大小等于涉及到该颜色的格子数量。

同时，对于某种颜色而言，时间不是完整的 $1,2,\dots,q$ 而是离散的，因此我们实际上算的是其中一段区间上，该颜色的最大连通块。于是我们要对结果数组的 $[l,r]$ 关于某个数值 $x$ 取最大值。

由于这里 $x$ 的数据范围是不超过 $10^6$ 的，因此可以从大到小遍历 $x$ ，找到某一个 $x$ 对应的所有赋值操作，对区间内尚未被赋值的位置进行赋值。

上述过程相当于经典问题区间染色，可以使用并查集解决。

时间复杂度为 $\mathcal{O}((nm+q)\alpha(nm))$ 。

简评： 这题疑似容易想到线段树分治？

致歉： 由于线段树分治并未用到染色递增的关键性质，且理论复杂度相对高一些（有一个可撤销并查集的 $\log$ 与线段树分治的 $\log$ ），同时编码难度相对低一些，因此本题时间限制对于线段树分治而言相对较紧，但标程实际用时在 1200 ms 以内。

不过，本题对于这点也在题面中给出了一定提示：本题题目描述中明确加粗了染色的递增性质，数据范围中也明确指出了 $c_i$ 递增并加粗了，都是为了提醒尝试写线段树分治的朋友——是否有什么没用到的东西？

这题如果实现得当，Pypy 也是可以通过的，虽然跑的并不快，大概用时 $4\sim 5$ 秒。

至此，所有题都可以用 Pypy 通过！你 Py 又赢！