CF632(EDU9) 题解
:::::warning[约定]
除特殊规定外，本文章下所有数均限定在整数域。
:::::
A. Grandma Laura and Apples：
:::::info[题目基本信息]
考察：数学。
题目简介：
小 B 在卖苹果，每个苹果
然后现在小 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})
数据范围：
-
1\le n\le 2500 -
\forall i,j\in[1,n],0\le a_{i,j}\le 10^9 ::::: 三个条件中的前两个非常好维护，第三个条件需要优化。
考虑建图（通过观察标签易得），在i 和j 之间连边权为a_{i,j} 的边，然后注意到a_{i,j}\le\max(a_{i,k},a_{k,j}) ，其实就指i 和j 之间不通过边权小于a_{i,j} 联通。
所以我们考虑到应用 Kruskal 进行求解，枚举每一坨a_{i,j} 相等的边，这一坨一起判断，一起加边即可。 时间复杂度为\Theta(n^2\log n) ，空间复杂度为\Theta(n^2) 。