CF609(EDU3) 题解

zrl123456 · 2025-07-20 22:05:59 · 题解

本场比赛没有计算几何题目，请放心食用。
但是我最擅长形式化（抽象化）题意了。

A. USB Flash Drives:

考察：排序，贪心。
题目简述：
求一个 |S| 最小的满足下列条件的 S 的大小 |S|。

• S\subseteq[1,n]\cap\mathbb Z
• \displaystyle\sum_{i\in S}a_i\ge m

其中整数 n,m 及序列 \{a_n\} 均已给出。
数据范围：

• 1\le n\le 100
• 1\le m\le 10^5
• \forall i\in[1,n],1\le a_i\le 1000

  显然，当 i 对应的 a_i 越大，i 越要放进集合 S 中，所以先将 \{a_n\} 降序排序，然后边选取数边判断即可。
  时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

  B. The Best Gift：

  考察：桶，模拟。
  题目简述：
  给你序列整数 n,m 及序列 \{a_n\}，求：

  \sum_{i=1}^n\sum_{j=i+1}^n[a_i\ne a_j]

  数据范围：

• 2\le n\le 2\times 10^5
• 2\le m\le\color{red}10
• \forall i\in[1,n]\cap\mathbb Z,1\le a_i\le m 时间复杂度为 $\Theta(n+m^2)$，空间复杂度为 $\Theta(m)$。 ### [C. Load Balancing](https://www.luogu.com.cn/problem/CF609C)： 考察：数学，贪心。 题目简述： 给定整数 $n$ 和序列 $\{m_n\}$，通过如下操作使得该序列极差最小，输出最小操作数。 > 选择两个数 $i,j$，满足 $i\ne j$ 且 $\{i,j\}\subseteq[1,n]\cap\mathbb Z$，使得 $m_i\leftarrow m_i-1$ 且 $m_j\leftarrow m_j+1$。

数据范围：

• 1\le n\le 10^5
• \forall i\in[1,n]\cap\mathbb Z,0\le m_i\le 2\times10^4

  首先，极差最小时一定为 0 或 1。

  极差肯定非负，若极差大于等于 2 时不断将最大值减一最小值加一即可。

设 \displaystyle sum=\sum_{i=1}^na_i，则序列最后会有 sum\bmod n 个数等于 \displaystyle\lfloor\frac{sum}{n}\rfloor+1，剩下的数都等于 \displaystyle\lfloor\frac{sum}{n}\rfloor，显然大的数最后变为较大的数一定不劣，故将序列排序后前 sum\bmod n 个数变为 \displaystyle\lfloor\frac{sum}{n}\rfloor+1 后面的同上，最后累加需加或减的次数，别忘除以 2。
时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

D. Gadgets for dollars and pounds：

考察：二分，贪心。
题意简述：
给你整数 n,m,k,s 以及 n\times 2 的矩阵 x，序列 \{op_m\},\{a_m\}。求满足以下条件的最小正整数 p 并给出所有下文中 \forall i\in[1,m]\cap\mathbb Z,S_i\ne 0 的所有 i 和 S_i，若不存在，输出 -1。

• 存在序列 \{S_m\}，满足：
• 1\le p\le n

数据范围：

• 1\le n\le 2\times 10^5
• 1\le k\le m\le 2\times 10^5
• 1\le s\le 10^9
• \forall i\in[1,n]\cap\mathbb Z,j\in\{1,2\},1\le x_{i,j}\le 10^6
• \forall i\in[1,m]\cap\mathbb Z,op_i\in[1,2],1\le a_i\le 10^6

  首先 p 具有单调性，我们可以对其二分。
  然后 \forall j\in\{1,2\}，选择最小的 x_{i,j} 是最好的，这样我们就可以预处理一个前缀最小值维护它，然后就分选或不选两种情况了。
  我们可以先将 \forall i\in[1,m]\cap\mathbb Z 的花费记录下来，即定义 \displaystyle ans_i=a_i\min_{j=1}^px_{j,op_i}，然后升序排序，模拟判断是否可行并记录方案即可。
  时间复杂度为 \Theta(m\log m\log n+n)，空间复杂度为 \Theta(n+m)。

  E. Minimum spanning tree for each edge：

  考察：生成树，倍增。
  题目简述：
  对于一个有 n 个点 m 条边的图 G，对于它的每条边求出包含这条边的最小生成树权值。
  数据范围：

• 1\le n\le 2\times 10^5
• n-1\le m\le 2\times 10^5

  首先运用 Kruskal 算法求出该图的最小生成树，然后在最小生成树上运用类似倍增求 LCA 的方式，过程中再维护一个 mx 数组来求出两点间的最大边，最后加上询问的这条边的边权减去求出的边权即可。
  时间复杂度为 \Theta(m\log m+m\log n+n\log n)，空间复杂度为 \Theta(n\log n+m)。

  F. Frogs and mosquitoes：

  考察：multiset。
  题目简述：
  这个抽象化题意太难描述了。
  在一个数轴上，向右涂上了 n 种颜色，第 i 种颜色端点为 x_i，初始长度为 t_i，若一个点上有多种颜色，则以端点最靠左的颜色为准。
  后面第 i 次操作有一个【编不出来了】落在了 p_i 处，不管这个【编不出来了】是否刚刚落下，只要它在一种颜色上，那么这种颜色的 sum\leftarrow sum+1 且 ans\leftarrow ans+b_i。
  最后输出每种颜色的 sum 和 ans。
  数据范围：

• 1\le n,m\le 2\times 10^5
• \forall i\in[1,n]\cap\mathbb Z,0\le x_i,t_I\le 10^9
• \forall i\in[1,m]\cap\mathbb Z,0\le p_i,b_i\le 10^9

  首先，若 x_i\le x_j 且 x_i+t_i\ge x_j+t_j，那么颜色 j 就完全没有意义了，可以忽略，所以我们维护一个 update 函数来省去不必要的颜色。
  然后我们把颜色和【编不出来了】都丢进 multiset 中按照题意维护即可。
  时间复杂度为 \Theta(n\log n+m\log m)，空间复杂度为 \Theta(n+m)。