第十六届东南大学大学生程序设计竞赛（春、夏季） - 题解 - 帖子

第十六届东南大学大学生程序设计竞赛（春、夏季）命题组

令 $b_{(i-1)*n+j} = a_i + a_j$ 那么问题转换为对于所有的 $i,j(1 \leq i,j \leq n^2)$ 求 $b_i+b_j$ 的中位数。

对于上述问题，我们可以对 $b_i$ 排序，再二分答案求解即可。

如果一个数 $i$ 未被填入且位置 $i$ 已经被占用，我们称其为种类一。

如果一个数 $i$ 未被填入且位置 $i$ 没有被占用，我们称其为种类二。

令 $f_{i,j}$ 表示填入 $i$ 个种类一， $j$ 个种类二的方法数。

类比错位排序有 $f_{i,j} = (j-1)*(f_{i,j-1}+f_{i,j-2}) + i*f_{i,j-1}$ 且 $f_{i,0} = i!$ 。

设序列 $a_n$ 中种类一的数有 $a$ 个，种类二的数有 $b$ 个，答案即为 $f_{a,b}$ 直接递推即可得到答案。

先按照开始时间排序然后模拟过程，能进行任务就进行任务，最后恢复原来的排序以得到结果。

事实上最多出现两个小于 $10^5$ 的数字相加不会爆 int 的所以正常不开 long long 应该都能过。

每一行每一列都是等差数列。

推导得出每一行的公差构成的数列也是等差数列。

每一列的公差构成的数列也是等差数列。

所以 $(x,y)$ 位置的元素可以表示为 $ax+by+cxy+d$ 的形式。

对于每一个给定的点列出方程。

对于一个给定的点 $a,b,c,d$ 的系数为已知量 $x,y,xy,1$ 。

列出一个 $4\times 4$ 的矩阵用矩阵消原如果得到上三角矩阵也可以做。

特别的，如果你不会写矩阵消原。

我们也可以根据矩阵消原来推导出三种不成立的情况：

1.存在三点同一行或者同一列。 2.存在四点同一条直线（可以是任意方向的斜线）。 3.存在其中两点同一行，另外两点同一列。

剩余的所有情况都可以唯一确定了。

用 $dp[i][j]$ 表示第 $i$ 个小节情绪为 $j$ 的时候前 $i$ 小节的最小负面评价大小。

状态转移方程为 $dp[i][j]=min(dp[i-1][k]+(|j-k|-3)^2+|j-a_i|)$ 。

将差的平方求和的式子拆分为三部分：

$a$ 的平方和：每次生长可以由上次的序列直接 $O(1)$ 推导出。
$b$ 的平方和：初始的时候需要 $O(n)$ 算出，之后不变了。
$c$ 的平方和：预处理前缀和，因为最多有 $\sqrt{n}$ 段，所以可以 $O(\sqrt n)$ 时间求出，因为生长 $n$ 次序列长度 $\frac{n(n+1)}2$ 所以生长次数也是 $O(\sqrt n)$ 次，总共需要 $O(n)$ 的时间。

将 $b_j$ 提取到后面最后在乘。

剩下的式子就是一个标准的卷积模板题。

其中一个多项式是 $a$ 。

另一个和 $a$ 一样长。

最后一项是 $\frac 11$ ,倒数第二项 $\frac 12$ ，以此类推。

对这两个式子做卷积，去掉前 $n$ 项后得到序列 $\{x_i\}$ 。( $x_ib_i=c_i$ )

考虑给每个点定义一个权值 $v$ ，代表这个点上一个硬币能给御坂美琴或者御坂妹妹带来多少步的收益。

初始所有出度为 $0$ 的点的 $v$ 都等于 $0$ 。

之后进行逆拓扑排序，然后倒着更新即可算出点的权值 $v$ ，之后选或者不选就是一个经典的背包 $01$ 背包统计方案的问题，简单动态规划即可，复杂度 $O(n^3)$ 。

Shift And/Or 模板题。复杂度 $O(\frac{n^2}{w})$ 。

或者可以用 FFT，对 $26$ 个字符分别进行 FFT，然后求和，FFT 解决模糊匹配也是一种经典题型，可自行百度相关例题。本题可能需要稍微优化一下常数。复杂度 $O(26nlogn)$ 。

考虑定义 $x_1,x_2,\ldots,x_n$ 代表某种情况下某位公主是否被选中，答案就等于 $\sum_{情况y} (x_1 + x_2 + \ldots + x_n)^3$ 。

把三次方项展开，转而变成枚举每一项，求有多少种情况包含它即可，后者可以简单动态规划完成，复杂度 $O(n^3m)$ 。