#P17685. [2026年保加利亚]Gardening
[2026年保加利亚]Gardening
题目描述
Azusa 想和她的朋友 Laika 一起通过园艺来娱乐。
她们想建造一座长为 米、宽为 米的矩形花园。花园被划分成 个大小为 米 米的小方格。
Laika 找到了 种不同的花。Azusa 和 Laika 会在每一个小方格中种植恰好一种花。
出于美观方面的考虑,整个花园必须同时满足下面三个条件。
条件 1
每一种花都必须在花园中至少出现一次。
条件 2
对于任意两个种植了同一种花的方格,它们之间必须存在一条路径,使得路径经过的所有方格都种植这种花。
这里,一条路径是由若干个相邻方格组成的序列。
换句话说,对于每一种花,所有种植这种花的方格在四联通意义下必须构成一个连通块。
条件 3
每一个方格都必须恰好有 两个 与它相邻、并且种植了同一种花的方格。
两个方格当且仅当它们拥有一条公共边时才称为相邻;仅仅共用一个顶点不算相邻。
给定 组不同的 。
对于每一组测试数据,请构造一个满足上述所有条件的花园;如果不存在这样的花园,则判断其无解。
输入格式
第一行包含一个整数:
T
表示测试用例数量。
接下来 行,每行包含三个整数:
N M K
描述一个测试用例。
输出格式
按照输入顺序依次输出每个测试用例的答案。
如果不存在合法花园,输出:
NO
如果存在合法花园,首先输出:
YES
然后输出一个 的整数矩阵。
矩阵第 行第 列的整数表示花园中对应方格种植的花的种类。
花的种类编号必须属于:
如果存在多个合法方案,可以输出任意一个。
数据范围
此外,定义 为所有存在合法答案的测试用例的 之和,则保证:
子任务
| 子任务 | 分值 | 依赖子任务 | 其他限制 | ||
|---|---|---|---|---|---|
| 0 | — | — | 样例 | ||
| 1 | 5 | — | |||
| 2 | 6 | 0–1 | — | ||
| 3 | 10 | 0–2 | |||
| 4 | 18 | — | — | ||
| 5 | 39 | , 在 中均匀随机选择 | |||
| 6 | 22 | 0–5 | — | 无额外限制 | |
只有通过某个子任务的全部测试,并且通过它所依赖的全部子任务,才能获得该子任务的分数。
样例
输入
5
2 2 2
2 2 1
4 4 4
4 4 2
4 6 3
一种合法输出
NO
YES
1 1
1 1
YES
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
YES
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
YES
1 1 1 1 1 1
1 2 2 3 3 1
1 2 2 3 3 1
1 1 1 1 1 1
样例说明
对于第一组测试数据,无法在 的花园中使用恰好 种花并同时满足全部条件,因此输出 NO。
其余测试数据均存在合法构造,样例输出给出了其中一种可能的方案。