自动搬运

查看原文

来自洛谷，原作者为

	Katyusha_01 不拿金牌不改签!(AFOed 个签不改了致敬青春

搬运于2025-08-24 22:51:14，当前版本为作者最后更新于2025-02-08 14:21:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

不用欧拉回路的做法来了，轻松拿下最优解。

模拟赛考了，赛时想到一个巧妙的二染色做法，可惜没想到分治。

考虑 $S=2$ 怎么做，不同行的相同颜色（相同题目，下同）两两一组，要求一个出现在第一列，另一个出现在第二列，这样组内贡献抵消，就能保证两列出现次数之差不超过 $1$（最后最多剩下一个，随便怎么分组都行），实现就是组内两个点（也就是对应的两行）之间连一条有权边（$0/1$ 表示翻转情况相同或只翻转一个）。然后跑一遍染色就做完了。

是不是听起来很厉害，考虑证明($*,*$ 表示一行数，$a,b,x,y$ 互不相同)：

• $a,b$ 和 $x,y$ 肯定没有连边，一定没有问题。
• $x,y$ 和 $x,y$ 连一条边就消没了。
• $x,a$ 和 $x,b$ 连一条边，其实就相当于合并成了一个 $a,b$。

就分讨完了，不会出现奇环的。

然后分治一下，把每行两两一对拆开，跑前面的染色，使得同色在第一列和第二列出现的次数之差不超过 $1$，然后把第一列的都放到原来那一行的前面一半，第二列的放到后面一半，分治下去就行了。证明类似线段树同一层的节点长度只差不超过 $1$。

染色可以手写队列跑 BFS，目前还是最优解。