当前位置:首页 > 构造 > 正文
GDKOI2021普及组Day2D矩阵
1237+

题目大意:一个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行。

(当然,如果考场上想不到,你也可以想一想怎么编数据,编数据的时候也会发现此规律。)

程序实现

GDKOI2021普及组Day2D矩阵:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!