题解

思路

设出现次数最大值为 $A=\max a_i$。本题的关键是先判断一个给定边长是否足够，再给出能同时达到两个上界的构造。

子任务 1：回溯枚举

当 $m,k\le5$ 时，从 $n=1$ 开始逐一尝试。按行优先顺序枚举每个格子填 $0$ 或某个仍有剩余的数字；每填完一个 $2\times2$ 子矩阵的右下角，就立即检查占用数与两条对角线。第一个存在解的 $n$ 即为最优边长。

状态规模只适用于极小数据，但它直接按照定义求解，可作为独立小规模正确性基准。

最小边长的两个必要条件

对边长为 $n$ 的矩阵：

1. 把行两两分组。任意相邻两行中，同一种数字至多出现 $n$ 次，否则必有一对处于某个 $2\times2$ 子矩阵的对角线上。若有一行未配对，再贡献至多 $n$ 次。因此$$A\le n\left\lceil\frac n2\right\rceil.$$
2. 取 $\lfloor n/2\rfloor^2$ 个两两不交的 $2\times2$ 子矩阵，每个至少需要一个空格。因此非空格总数至多$$n^2-\left\lfloor\frac n2\right\rfloor^2,$$ 从而 $m$ 不能超过这个值。

这两个条件也是充分的。

三类位置

使用从 $0$ 开始的行列下标，把会使用的位置分成：

• $X$：行号为偶数，且行列下标之和为奇数；
• $Y$：行号为奇数，且行列下标之和为奇数；
• $Z$：行号、列号均为偶数。

其余恰好 $\lfloor n/2\rfloor^2$ 个“奇行奇列”位置始终留空，所以每个 $2\times2$ 子矩阵都有空格。每个集合在任意 $2\times2$ 内至多出现一次；并且 $X$ 与 $Z$ 的格子只可能同行，$Y$ 与 $Z$ 的格子只可能同列。因此，同一种数字只要不同时使用 $X$ 和 $Y$，就不会占据一条对角线的两个端点。

将数字按出现次数从大到小处理。只要 $X$ 还有位置，就先填 $X$，不足部分填 $Z$；当 $X$ 用尽后，后续数字改为先填 $Y$，不足部分仍填 $Z$。上面的两个容量条件保证整个过程不会缺少位置。

子任务 2：线性寻找边长

从 $n=1$ 开始，依次检查

$$m\le n^2-\left\lfloor\frac n2\right\rfloor^2,\qquad A\le n\left\lceil\frac n2\right\rceil.$$

找到第一个满足条件的 $n$ 后执行三类位置构造。该做法寻找边长需要 $O(m)$，适合 $m\le200$。

子任务 3：二分答案

两个容量上界均随 $n$ 单调不减，所以可在 $[1,m]$ 上二分第一个满足条件的边长，再执行同一构造。

设本组数据的答案边长为 $n$。排序耗时 $O(k\log k)$，二分耗时 $O(\log m)$，建表与输出耗时 $O(n^2)$；空间复杂度为 $O(k+n^2)$。所有测试用例满足总输入规模限制，输出本身也是该复杂度所必需的。

正确性证明

容量推导证明了任何合法答案都必须满足两个不等式，所以二分得到的边长不可能大于真正最优值。构造中，奇行奇列位置全为空，故每个 $2\times2$ 至多三个非空格；同一种数字只会落在 $X\cup Z$ 或 $Y\cup Z$，不会出现在同一条对角线两端；每种数字又恰好放置 $a_i$ 次。因此该边长一定存在合法矩阵，它就是最小边长。

做法

1. 读入每组频率，求 $m$ 与最大频率 $A$。
2. 小规模直接枚举边长并回溯；中等规模线性枚举边长；满分做法二分最小边长。
3. 按出现次数降序处理每种数字，依次使用 $X$、$Y$ 与公共的 $Z$ 位置。
4. 输出边长和构造矩阵。

复杂度

满分算法对每组测试排序需要 $O(k\log k)$，二分需要 $O(\log m)$，构造与输出需要 $O(n^2)$；空间复杂度为 $O(k+n^2)$。中等规模算法额外使用 $O(m)$ 次边长检查。极小规模回溯为指数复杂度，仅用于 $m,k\le5$。