4285. [THUPC 2025 Final] 三元链

【题目描述】

给定正整数 $n,k$，请在一个 $n\times n$ 的网格中将 $kn$ 个方格染成黑色，其余方格染成白色，满足：

• 在水平或竖直方向上不存在连续的三个同色格。具体地：

  1. 不存在 $1\le i\le n,1\le j \le n-2$ 满足坐标为 $(i,j),(i,j+1),(i,j+2)$ 的格子均为黑色或均为白色。
  2. 不存在 $1\le i\le n-2,1\le j \le n$ 满足坐标为 $(i,j),(i+1,j),(i+2,j)$ 的格子均为黑色或均为白色。
• 每列中有恰好 $k$ 个黑色格。
• 对于任意 $i=1,2,\dots,k$，任意相邻的两列中从上至下第 $i$ 个黑色格的行坐标之差不超过 $1$。具体地，记第 $j$ 列的黑色格的坐标分别为 $(x_{1,j},j),(x_{2,j},j),\dots,(x_{k,j},j)$，其中 $x_{1,j} < x_{2,j} < \dots < x_{k,j}$，那么对于 $1\le i\le k,1\le j < m$ 有 $|x_{i,j}-x_{i,j+1}|\le 1$。

给出一种合法的方案，或判定无解。

【输入格式】

第一行包含一个正整数 $T$ $(1\le T\le 500)$，表示数据组数。

每组数据包含一行两个正整数 $n,k$ $(4\le n \le 1000,1\le k \le n)$，分别表示网格的大小与每列中黑色格的数量。

保证单个测试点中所有数据 $n^2$ 的和不超过 $10^6$。

【输出格式】

对于每组测试数据：

• 若不存在合法的染色方案，则仅输出一行一个字符串 No；
• 否则，先输出一行一个字符串 Yes，然后接下来 $n$ 行每行输出一个长度为 $n$，仅包含字符 # 与 . 的字符串，代表你染色方案中从上到下每一行的染色情况，其中字符 # 代表对应格染为黑色，字符 . 代表对应格染为白色。如果有多种合法的染色方案，输出任意一种即可。

【输入样例】

3
4 2
6 1
9 5

【输出样例】

Yes
#..#
.##.
.##.
#..#
No
Yes
.#.#..##.
#.#.##..#
#.##..##.
.#..##.##
#..##.#.#
.##..#.#.
##.##.#.#
#.##.##..
.##.##.##

【样例解释】

对于第一组数据，以下为若干不符合条件的示例：

示例 $1$ 中左下角有连续的三个白色格，示例 $2$ 中第一列与第四列黑色格数量不正确，示例 $3$ 中左上角有连续的三个黑色格，示例 $4$ 中第三、四列的第二个黑色格行坐标之差大于 $1$。

对于第二组数据，容易发现不存在合法的染色方案。

对于第三组数据，下图中不同方位的黑色格用不同颜色标注后易见答案的合法性：

【来源】

清华大学学生算法协会 GitLink 仓库