George_Plover edited 1 年，5 月前
This is a past version of blog 2023 年上海市大学生程序设计竞赛 - 六月赛 题解
容易发现当 $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$ 时一定有解，可以打表或者搜索求解。
首先可以将 $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)$
容易发现，第 $n$ 个士兵作为端点时，形成的区间总是良好的。
如果第 $n$ 个士兵的位置确定了为 $i$，那么对于区间 $[l,r],li$ 肯定不是良好的，我们就可以把问题分解到 $[l,i-1],[i+1,r]$ 两个子区间了。
因此可以采用朴素的区间dp求解出良好区间最大的数目，并且记录分界点构造方案即可，复杂度 $O(n^3)$ ，对于已有的士兵需要特殊判断和处理。
注意到题目描述里强调了输出格式不允许有行末空格。
等价于枚举分割点 $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)$
首先不妨将随机变量按照上界从小到大排序，于是可以视 ${a_i}$ 为递增序列。
根据Min-Max容斥的第K大拓展，可以得到：
$$
E\big (\text{K-thMax}{S}\big ) = \sum_{T\subset S} E\big(\min {T }\big)\cdot(-1)^{|T|-k}\cdot\binom {|T|-1}{k-1}
$$
其中 $S$ 表示集合，在此题中即为随机生成的 $n$ 个数。$T$ 为 $S$ 的非空子集。
对此我们考虑子集 $T$ 的 $E\big(\min{T}\big)$ 如何求解。
假设$|T| = m$，并且 $T$ 中元素的随机上界分别为 $a_{p_1},a_{p_2},\cdots a_{p_m},(p_1<p_2\cdots <p_m)$
可以用积分求解该期望：
$$
E\big(\min{T}\big) =\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)$