ATC ** 练习 | 程序员灯塔

要正视自己的 ** ，所以。。。

statement

给定一个 $n (n ge 6)$，构造一个 $ntimes n$ 的矩阵，由 `.` 和 `#` 组成，这个矩阵满足：

每行每列都有且仅有 (3) 个 # 。
定义两个 # 在上下左右四个方向相连则为连通，若 (a) 和 (b) 连通，(b) 和 (c) 连通，那么 (a) 和 (c) 也连通。满足这个矩阵中由 # 连通组成的连通块数量恰好为 (n) 。

solution

由于要满足行和列两个方向的信息，所以考虑按对角线对称构造，然后通过不停的奋斗，搞出了这种东西。

##.#......
###.......
.#.##.....
#.#..#....
..#..##...
...##..#..
....#..##.
.....##..#
......#.##
.......###

当然，这是偶数的，奇数的长这样：

##.#.......
###........
.#.##......
#.#..#.....
..#..##....
...##..#...
....#..##..
.....##.#..
......#..##
.......#.##
........###

然后正解是对于 (n % 3) 的结果分类。

对于 (n = 3k) 的时候，构造：

###......
...###...
......###
###......
...###...
......###
###......
...###...
......###

然后是 (n = 3k + 1) ，考虑在 (n = 3k) 的基础上构造：

          3
 ###.......
 ...###....
 ......###.
 ###.......
 ...###....
 ......###.
 ###.......
 ...###....
 ......###.
3..........

然后就是从上面扣下来三个，最后只能多一个连通块，然后就变成下面的样子：

###.......
...###....
......###.
##.......#
...##....#
.......###
###.......
...###....
......###.
..#..##...

但是对于 (n = 7) 要特判。

然后是 (n = 3k - 1) ，考虑从上面的 (n = 3k) 删去最后一行和一列。

       11
 ###.....
 ...###..
1......##
 ###.....
 ...###..
1......##
 ###.....
 ...###..

然后在这些 1 在行列方向相互对出的点上选两个 # 就好了，但是这上面已经有 # 了。

然后有一个非常迷惑的操作：

#.
.#

变成

.#
#.

每行每列的数量是不变的，然后构造：

###.....
...##.#.
.....###
###.....
...##.#.
.....###
###.....
...###..

程序员灯塔
转载请注明原文链接：ATC ** 练习