GDKOI2021普及组Day2D矩阵
1959+
作者:crxis 发布:2021-02-03 分类:构造
题目大意:一个n*n的矩阵A,每一行每一列的和都是偶数,需要分解成两个n*n矩阵B和C,要求A=B+C,且B和C每一行的和、每一列的和都相当。
解题思路
不难想到,偶数直接分一半,奇数尽量分一半,如果这个位置分多了(向上取整),记下来,下一次对应行、列分少一点(向下取整)。
按照这种思路,从上往下依次确定每个位置的大小,有可能出问题,如:
1 0 1
0 1 1
1 1 0
遇到不确定填+(向上取整),多了的填-(向下取整):
+ 0 –
0 + –
此时已经无法再填,需要撤销操作(后悔:联想到二分图、网络流),复杂度就会增高。
因此,我们只能换一种填法:第一个不妨填+,然后在同一行找一个不确定的奇数填-,接着在该列找一个不确定的奇数填+……如此往复,必有一条欧拉回路,因为题目保证每一行每一列都是偶数。
① 0 ②
0 ④ ③
⑥ ⑤ 0
最后找不到就不需要再填,继续下一个即可(奇数是向上取整,偶数向下取整)。
如何实现?暴力模拟,参考Dinic算法的优化,用引用,保证只扫一遍——每一行只会循环查找n列、每一列只会循环查找n行。
(当然,如果考场上想不到,你也可以想一想怎么编数据,编数据的时候也会发现此规律。)