2023 年上海市大学生程序设计竞赛 - 六月赛 题解

George_Plover edited 1 年，9 月前

A.四角不同色

容易发现当 $n=2$ 或 $m=2$ 时一定有解，而且容易构造。

当 $n=3$ 时，若要有解，可以粗略判断出 $m\le 8$ 是必要的，否则将会出现两列完全相同，这时必然会有四角同色的子矩阵。

据此可以预估出当 $min(n,m)>2$ 时，若要有解，则 $max(n,m)$ 不会很大。据此可以进行搜索或者手推，构造出方案。

最终结论：$min(n,m)\le 4$ 且 $max(n,m)\le 6$ 时一定有解，可以打表或者搜索求解。

B.模后和

首先可以将 $A,B$ 两个数列各项对 $n$ 取模，不影响答案。

然后问题的本质在于在 $A,B$ 两个数列之间，构造一个完美匹配，使得匹配的 $n$ 组 $(i,j)$ 中，满足$a_i+b_j\ge n$ 的组的数目尽可能少，不妨称这样的组为劣组。反之不满足此条件的称为优组，我们希望优组尽可能多。

因此可以先对两数列排序。假设最优方案中，优组的数目是 $k$ ，那么我们一定可以调整方案使得 $A$ 序列中取最小的 $k$ 个元素来组成优组，即 $a_1,a_2,\cdots a_k$。 接下来假设所有在优组中的 $B$ 序列元素是 $b_{p_k}\le b_{p_{k-1}}\le \cdots b_{p_1}$ ，容易证明 $(a_1,b_{p_1}),(a_2,b_{p_2})\cdots (a_k,b_{p_k})$ 肯定是一种全为优组的分组方案。

因此我们不妨从小到大枚举 $k$ ，并且为当前 $a_k$ 贪心选取一个最大的 $b_{p_k}$ 使得 $a_k+b_{p_k}<n$ ，直到找不到为止，即可最大化优组的数目。

排序数列可以在取模后用计数排序进行，贪心算法可以用双指针实现，复杂度 $O(n)$

C.排头兵

容易发现，第 $n$ 个士兵作为端点时，形成的区间总是良好的。

如果第 $n$ 个士兵的位置确定了为 $i$，那么对于区间 $[l,r],l<i,i<r$ 肯定不是良好的，我们就可以把问题分解到 $[l,i-1],[i+1,r]$ 两个子区间了。

因此可以采用朴素的区间dp求解出良好区间最大的数目，并且记录分界点构造方案即可，复杂度 $O(n^3)$ ，对于已有的士兵需要特殊判断和处理。

注意到题目描述里强调了输出格式不允许有行末空格。

D.前缀分割

等价于枚举分割点 $i$ ，然后统计 $C[1,i]$ 有多少个后缀与 $A$ 的前缀相匹配，记统计结果数目为 $a_i$ ；然后统计 $C[i+1,|C|]$ 有多少个前缀和 $B$ 的前缀相匹配，记统计结果为 $b_i$ 。那么最后的答案就是 $\sum a_i\cdot b_i$ 。

求解 $a_i$ 可以对 $A$ 求KMP然后在 $C$ 上跑匹配完成。

求解 $b_i$ 可以把 $B$ 与 $C$ 拼接后求 Z函数 来完成。

复杂度 $O(n)$

E. 第K大

首先不妨将随机变量按照上界从小到大排序，于是可以视 $a_i$ 为递增序列。

根据Min-Max容斥的第K大拓展，可以得到：
$$E(\text{K-thMax}S)=\sum _{T\subset S}E(minT)\cdot (-1{)}^{|T|-k}\cdot (\genfrac{}{}{0ex}{}{|T|-1}{k-1})$$
其中 $S$ 表示集合，在此题中即为随机生成的 $n$ 个数。$T$ 为 $S$ 的非空子集。

对此我们考虑子集 $T$ 的 $E(minT)$ 如何求解。

假设$|T|=m$，并且 $T$ 中元素的随机上界分别为 $a_{p_1},a_{p_2},\cdots a_{p_m},(p_1<p_2\cdots <p_m)$

可以用积分求解该期望：
$$E(minT)={\int }_0^{a_{p_1}}\prod _{i=1}^m(1-\frac{x}{a_{p_i}})\text{d}x$$
积分项是关于 $x$ 的 $m$ 次函数，我们只需要知道每次项的系数，即可在 $O(m)$ 时间求解积分的值。

接下来，回到原问题，我们不可能枚举所有的 $T$ ，但是我们可以用 $dp$ 的方式把 $|T|$ 相同的子集归为同一类，并且在动态规划的过程中维护积分各项的系数。

用 $dp(i,j)$ 表示在下标区间 $[i,n]$ 的随机变量中选择 $j$ 个随机变量的集合 $T$ 的积分多项式之和，该状态记录的是多项式各项系数而非积分结果。

最后按照 $a_i$ 将值域分为若干个段，用分段积分的方式计算出每部分贡献即可。

复杂度 $O(n^3)$

Past Versions

• #28600 by George_Plover (2023-06-30 16:11:00).

Comments