2023 Abakoda Long Contest——C. Canonizing Cannonade（封圣炮响）

题目大意

题目描述

Bob 正在为学校的一场模拟战斗设计队形，参与者扮演潘普洛纳战役中的士兵。

一个队形是一个 $r \times c$ 的网格，其中恰好有 $m$ 个格子里站着士兵。敌方每消耗一发炮弹，可以进行如下操作：

• 选择某一行或某一列，消灭该行或该列中的所有士兵。

定义一个队形的韧性为消灭其中所有士兵所需的最少炮弹数。

给定 $r, c, m, k$，请构造出任意一个韧性恰好等于 $k$ 的队形，或者报告无解。你需要回答同一个文件中的 $T$ 组测试数据。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

接下来是每组测试数据的描述，每组数据占一行，包含四个用空格分隔的整数 $r, c, m, k$。

输出格式

对于每组测试数据，若无解，输出一行 NO；否则输出一行 YES。

若输出 YES，则接下来还需输出一个 $r \times c$ 的网格，即输出 $r$ 行，每行包含一个长度为 $c$ 的字符串。网格中只能包含字符 . 和 #，分别表示空地和站有士兵的格子；注意其中恰好应有 $m$ 个字符为 #。

若存在多组可行解，输出任意一组均可。

数据范围与评分

对所有子任务：

$$0 \leq T \leq 1500,\quad 1 \leq r, c \leq 25,\quad 1 \leq m \leq rc,\quad 1 \leq k \leq 10^9$$

子任务	分值	限制
1	$\mathbf{40}$	$m = k$
2	$\mathbf{30}$	$m = 2k$
3	$\mathbf{20}$	$m = 3$
4	$\mathbf{10}$	无额外限制

样例

2
7 8 11 4
9 6 2 10

YES
........
...#....
#..#...#
#....#.#
...##.#.
........
...#....
NO

对于第一组数据，可以验证所有士兵能够用 $4$ 次操作被清除：选择从上往下的第三、四、五行，以及从左往右的第四列。同时可以说明无法用 $3$ 次操作完成，因此该队形的韧性为 $4$。

对于第二组数据，无法构造出满足要求的队形。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）