本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$

$m\le 10$ 的数据范围提醒了我们，注意到两个元素相同的不同位置的数本质上是相同的，然后我们把数放到桶 $\{t_m\}$ 里，对元素枚举，得到两种元素 $i,j$，使最终答案 $ans\leftarrow ans+t_it_j$ 即可。
时间复杂度为 $\Theta(n+m^2)$，空间复杂度为 $\Theta(m)$。

C. Load Balancing：

考察：数学，贪心。
题目简述：
给定整数 $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\}$，满足：
  • $\forall i\in[1,m]\cap\mathbb Z,S_i\in[0,p]\cap\mathbb N$。
  • $\displaystyle\sum_{i=1}^m[S_i\ne 0]=k$。
  • $\displaystyle\sum_{i=1}^m[S_i\ne 0]\cdot a_ix_{S_i,op_i}\le s$。
• $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)$。