自动搬运

查看原文

来自洛谷，原作者为

	hhoppitree 成功的秘诀只有一个：加训。故古语有云：日拱一卒，功不唐捐；玉汝于成，溪达四海。

搬运于2025-08-24 22:59:54，当前版本为作者最后更新于2024-08-28 10:32:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

记行和为 $R_i$，列和为 $C_i$，容易证明 $\sum R=\sum C$ 则必有对应解，记 $p$ 为输入元素不全相同的一行，$q$ 为输入元素不全相同的一列（若不存在则为 $0$，否则任意），若 $p=q=0$ 是平凡的（此时必有 $R_1=R_2=\cdots$ 或 $C_1=C_2=\cdots$），下文讨论 $p+q\ne0$ 的情况，在下文推导中，我们将多次用到如下事实：$\{x_1-y_1,x_1+y_1\}=\{x_2-y_2,x_2+y_2\}\Leftrightarrow x_1=x_2,y_1=y_2$，即若 $(x_1,y_1)\ne(x_2,y_2)$，则对应的集合交的大小 $\le1$。

若 $pq\ne0$，我们取出 $(p,q)$ 和 $(r,q)$，其中 $r$ 为第 $q$ 列任一与 $(p,q)$ 值不同的位置，先令 $C_q=0$，枚举 $4$ 种可能的 $R_p$ 与 $R_r$，则由 $R_p\ne R_r$，可推理出全部 $C_{*}$，进而得出所有 $R_{*}$，最终使用全局加上同样的数来调整 $\sum R-\sum C$。

考虑拓展这个做法，不妨设 $p=0,q\ne0$，发现此时可能出现 $C_{*}$ 全相同的情况导致无法推理出 $R_{*}$（由于第 $p$ 行有至少两种取值，故 $C_{*}$ 不会全相同），可以证明此时 $C_{*}$ 必然全相同，而每个 $R_{i}$ 都是在一个大小为 $2$ 的集合中选择，使用 $\texttt{bitset}$ 优化背包计算出所有可能的 $\sum R$ 后选出一种合理的进行调整即可，时间复杂度为 $\mathcal{O}\left(\dfrac{n^2V}{w}\right)$。