本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-29 13:31:02

:::::info[闲话] 收回我在 EDU10 题解里的闲话。
:::::

A. Co-prime Array：

考察：数学（$1200$）。
题目简介：
给你一个序列 $\{a_n\}$，求插入一定数字使其满足下列条件的最小插入数量，并构造一种方案。

• $\forall i\in[1,|a|),\gcd(a_i,a_{i+1})=1$

数据范围：

• $1\le n\le 1000$
• $\forall i\in[1,n],1\le a_i\le 10^9$

注意到对于任何正整数 $x$，满足 $\gcd(x,1)=1$，所以我们加入 $1$ 一定不劣。
那么我们对于所有不符合条件的相邻数对，在它们之间插入一个 $1$ 即可。
时空复杂度均为 $\Theta(n)$。

B. Seating On Bus：

考察：模拟（$1000$）。
题目简介：
有一个有 $n$ 排 $4$ 列座位的公交车，有 $m$ 位乘客要上车，按照从靠窗到不靠窗（第一关键字），从前到后（第二关键字），从左两排到右两排（第三关键字）的顺序坐，下车时按从前到后（第一关键字），从左两排到右两排（第二关键字），从不靠窗到靠窗（第三关键字），求每一位下车的乘客是第几个上车的。
数据范围：

• $1\le n\le 100$
• $1\le m\le 4n$

模拟即可，懒得讲。
时空复杂度均为 $\Theta(n)$。

C. Hard Process：

考察：前缀和，双指针（$1600$）。
题目简介：
给你只含 $0$ 和 $1$ 的序列 $\{a_n\}$ 和整数 $k$，求满足下列条件的 $l,r$ 中可能的最大的 $r-l+1$ 并构造一种符合条件的操作后的序列。

• $1\le l\le r\le n$
• 能通过最多 $k$ 次操作使得 $\forall i\in[l,r],a_l=1$
  • 操作：选择一个 $pos\in[1,n],a_{pos}\leftarrow 1$

数据范围：

• $1\le n\le 3\times 10^5$
• $0\le k\le n$

操作等价于选择一个 $pos\in[1,n],a_{pos}=0,a_{pos}\leftarrow 1$，因为这样操作才有效。
那么条件就等价于 $\displaystyle\sum_{i=l}^r[a_i=0]\le k$，这个东西显然可以运用前缀和维护。
然后我们注意到最大的合法的 $r$ 是一定随 $l$ 的增大而不降的，所以我们可以双指针维护。
时空复杂度均为 $\Theta(n)$。

D. Number of Parallelograms：

考察：计算几何（$1900$）。
题目简介：
给定平面上的 $n$ 个点，求从中选取四个点使得这四个点构成平行四边形的方案数。
数据范围：

• $1\le n\le 2000$

我们先证明四边形 $ABCD$ 为平行四边形的一个充要条件为 $|x_A-x_C|=|x_B-x_D|$ 且 $|y_A-y_C|=|y_b-y_D|$。
:::::success[必要条件] 如图：

初中数学，$ASA$ 证明全等。
::::: :::::success[充分条件] 同上。
$SAS$ 证明全等。
::::: 那么根据证明，我们对每条线开一个 pair，然后排序统计即可。
时间复杂度为 $\Theta(n^2\log n)$，空间复杂度为 $\Theta(n^2)$。

E. Different Subsets For All Tuples：

考察：组合数学（$2300$）。
题目简述：
存在一个序列 $\{a_n\}$，且 $\forall i\in[1,n],a_i\in[1,m]$，求所有可能序列的不同子序列（包括空序列）个数之和，并对 $10^9+7$ 取模。
数据范围：

• $1\le n,m\le 10^6$

注意到本题需要对不同的子序列计数，所以我们只对第一次出现的子序列计数。也就是说，对于子序列的下标 $\{b_k\}$（钦定 $b_0=0$），$\forall i\in[1,k],j\in[b_{i-1}+1,b_i-1],a_j\ne a_{b_i}$。
那么我们就推出了最后答案的表达式：
$$(\sum_{i=1}^nm^i\sum_{j=i}^n\binom{j-1}{i-1}m^{n-j}(m-1)^{j-i})+m^n$$ （加 $m^n$ 是因为空序列是任何一个序列的子序列，$i$ 枚举的是子序列长度，$j$ 枚举的是子序列下标 $\{b_i\}$ 中 $b_i$ 的值，即子序列终止位置）
注意到计算这个式子时间复杂度至少为 $\Theta(n^2)$，所以我们要对这个式子的前面一大坨进行化简。
$$\begin{aligned}\sum_{i=1}^nm^i\sum_{j=i}^n\binom{j-1}{i-1}m^{n-j}(m-1)^{j-i}&=\sum_{i=1}^n\sum_{j=i}^n\binom{j-1}{i-1}m^{n-j+i}(m-1)^{j-i}\&=\sum_{j=1}^n\sum_{i=1}^j\binom{j-1}{i-1}m^{n-j+i}(m-1)^{j-i}\&=\sum_{j=1}^nm^{n-j+1}\sum_{i=1}^j\binom{j-1}{i-1}m^{i-1}(m-1)^{j-i}\end{aligned}$$ 注意到这玩意特像二项式定理，直接令 $i_1=i-1$。
$$\begin{aligned}\sum_{j=1}^nm^{n-j+1}\sum_{i=1}^j\binom{j-1}{i-1}m^{i-1}(m-1)^{j-i}&=\sum_{j=1}^nm^{n-j+1}\sum_{i_1=0}^{j-1}\binom{j-1}{i_1}m^{i_1}(m-1)^{j-i_1-1}\&=\sum_{j=1}^nm^{n-j+1}(2m-1)^{j-1}\end{aligned}$$
这个式子直接预处理 $m$ 和 $2m-1$ 的幂次即可线性计算，最后别忘了加上 $m^n$。
时空复杂度均为 $\Theta(n)$。

F. Bear and Bowling 4：

考察：斜率优化 dp（$2500$）。
题目简介：
给你序列 $\{a_n\}$，求：
$$\max_{l=1}^n\max_{r=l}^n\sum_{i=l}^r(i-l+1)a_i$$ 数据范围：

• $1\le n\le 2\times 10^5$
• $\forall i\in[1,n],|a_i|\le 10^7$

我们先考虑如何快速求 $\displaystyle\sum_{i=l}^r(i-l+1)a_i$，我们对其变形：
$$\begin{aligned}\sum_{i=l}^r(i-l+1)a_i&=\sum_{i=l}^ria_i-(l-1)a_i\&=\sum_{i=l}^ria_i-(l-1)\sum_{i=l}^ra_i\end{aligned}$$ 那么我们维护前缀和（下文中 $num$ 指 $ia_i$ 的前缀和，$sum$ 指 $a_i$ 的前缀和）即可快速求得。
注意到现在时间复杂度仍是 $\Theta(n^2)$，考虑继续优化。
考虑枚举 $r$，求 $l$。
设 $f_i$ 为以 $i$ 结尾的连续子序列的最大权值，那么就有：
$$\begin{aligned}f_i&=\max_{j=1}^i(num_i-num_{j-1}-(j-1)(sum_i-sum_{j-1}))\&=\max_{j=1}^i((j-1)sum_{j-1}-num_{j-1})+num_i-(j-1)sum_i\end{aligned}$$ 我们假设已经找到了最大值对应的 $j$，那么就有：
$$f_i=(j-1)sum_{j-1}-num_{j-1}+num_i-(j-1)sum_i$$ 移项：
$$f_i-num_i=-sum_i(j-1)+(j-1)sum_{j-1}-num_{j-1}$$ 这是一个斜率优化的形式，不妨令 $y=f_i-num_i,k=-sum_i,x=j-1,b=(j-1)sum_{j-1}-num_{j-1}$。
注意到这道题 $x$ 单调递增，而 $k$ 并不，所以我们要通过在单调队列里二分来维护一个凸包。
然后我们注意到这个题没必要定义 $f_i$……
时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。