CF660(EDU11) 题解

zrl123456 · 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[充分条件] 同上。

  ::::: 那么根据证明，我们对每条线开一个 `pair`，然后排序统计即可。 时间复杂度为 $\Theta(n^2\log n)$，空间复杂度为 $\Theta(n^2)$。 #### [E. Different Subsets For All Tuples](https://www.luogu.com.cn/problem/CF660E)： 考察：组合数学（$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)。