题解：P9731 [CEOI 2023] Balance

· · 题解

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

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

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

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

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

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

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