CF632(EDU9) 题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-07 20:59:10

:::::warning[约定] 除特殊规定外，本文章下所有数均限定在整数域。
:::::

A. Grandma Laura and Apples：

:::::info[题目基本信息] 考察：数学。
题目简介：
小 B 在卖苹果，每个苹果 $p$ 元钱，现在她卖完了苹果，但是她年纪大了记性不好，忘了最开始有几个苹果，只知道有 $n$ 位顾客，每位顾客买走了当时所剩苹果的一半，如果当时苹果数为奇数那么她就会慈祥地送他们半个苹果（不花钱，同时她很清楚地记得有没有送每位顾客半个苹果）。
然后现在小 B 想要知道她应得多少钱，以便看看有没有顾客耍她。
数据范围：

$1\le n\le 40$
$2\le p\le 100,2|p$ ::::: 注意到 $2|p$，且根据题目，小 B 只可能卖出（送出除外）几个或者几个半苹果，所以最后结果能用整型变量储存。
然后倒着推，边求出当时还有几个苹果，边求出后面一共得了多少钱，按题意模拟即可。
时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n)$。

B. Alice, Bob, Two Teams：

:::::info[题目基本信息] 考察：前缀和。
题目简介：
小 X 和小 K 在玩一个游戏。
场上有 $n$ 名战士站成一排，第 $i$ 名战士的战力为 $p_i$。
最开始小 X 先将 $n$ 名战士分成两队（A 队和 B 队），然后小 K 将这一排的一个前缀或后缀的战士进行操作，使得 A 队的去 B 队，B 队的去 A 队，A 队归小 X，B 队归小 K。
现在小 X 分好了队，小 K 想要使自己战队总战力尽量大，问最大值是多少。
数据范围：

$1\le n\le 5\times 10^5$
$\forall i\in[1,n],1\le p_i\le 10^9$ ::::: 提到前缀和后缀，我们便想到前缀和和后缀和，维护它们，然后枚举前缀和后缀的端点，依题意翻转前后缀，用前后缀和维护即可。时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n)$。

C. The Smallest String Concatenation：

:::::info[题目基本信息] 考察：排序，数学。
题目简介：
小 I 收到了 $n$ 个字符串 $\{s_n\}$，他想知道若把这些字符串按一定顺序拼成一个字符串，使这个字符串字典序最小，求这个字符串。
数据范围：

$1\le n\le 5\times 10^4$
$\forall i\in[1,n],1\le|s_i|\le 50$
$\displaystyle\sum_{i=1}^n|s_i|\le5\times 10^4$ ::::: :::::info[闲话] 你说的对，这个题很简单，但是我忘了邻项交换法。
::::: 运用邻项交换法，若两个字符串 $a$ 和 $b$ 进行比较，则若 $a+b<b+a$（$+$ 在这里表示字符串拼接），则 $a$ 应在前面。根据这个方式排序即可。时间复杂度为 $\displaystyle\Theta(\sum|s|\log n)$（在这里 $\displaystyle\sum|s|=\sum_{i=1}^n|s_i|$，下同），空间复杂度为 $\displaystyle\Theta(\sum|s|)$。

D. Longest Subsequence：

:::::info[题目基本信息] 考察：桶，数学。
题目简介：
小 A 收到了一个数列 $\{a_n\}$ 和一个数字 $m$。他想知道这个数列的子序列的最小公倍数不大于 $m$ 的条件下，子序列最长是多少，并给出这个子序列和它的最小公倍数。

定义空序列的最小公倍数为 $1$。

数据范围：

$1\le n,m\le 10^6$
$\forall i\in[1,n],1\le a_i\le 10^9$ ::::: 注意到 $m\le 10^6$，所以我们可以给 $\{a_n\}$ 中的数开桶，然后统计通过调和级数统计能整除每个数的 $\{a_n\}$ 中的数的个数，然后统计答案即可。 :::::info[闲话] 写的时候一时忘了调和级数叫什么在 HL 群中问了下。
::::: 时间复杂度为 $\Theta(m\log m)$，空间复杂度为 $\Theta(n+m)$。 :::::warning[坑点] 注意到求的是最小公倍数，因此统计答案时应该取最小的满足条件的数。
同时我们要把初始最小值设成负数，以免出现空序列的情况。
同时注意到 $a_i\le 10^9$，所以需要特判 $a_i>m$。
:::::

E. Thief in a Shop：

:::::warning[咕咕咕] FFT 不会，咕了。
:::::

F. Magic Matrix：

:::::info[题目基本信息] 考察：最小生成树。
题目简介：
小 Z 收到一个 $n\times n$ 的矩阵 $a$，他想知道这个矩阵 $a$ 符不符合以下条件：

$\forall i\in[1,n],a_{i,i}=0$
$\forall i,j\in[1,n],a_{i,j}=a_{j,i}$
$\forall i,j,k\in[1,n],a_{i,j}\le\max(a_{i,k},a_{k,j})$