#P6941. 作业题

    ID: 6772 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-矩阵构造贡献法局部修复补集转化全子集枚举广度优先搜索矩阵转置

作业题

题目描述

给定一个 nn 行 mm 列的网格。三个不同格子组成的无序集合称为一组有魔法的格子,当且仅当它们都在同一个 2×22\times2 区域内。

请选择一个非空的四连通块,使所选格子中恰好有 kk 组有魔法的格子。四连通指在所选格子内,仅通过上下左右相邻移动,就能从任一格到达任一格。

输入格式

第一行一个整数 TT,表示数据组数。接下来 TT 行,每行三个整数 n,m,kn,m,k。

输出格式

对于每组数据,若无解,输出一行 −1-1。

否则输出 nn 行,每行一个长为 mm 的字符串。若选择第 ii 行第 jj 列的格子,则第 ii 个字符串的第 jj 个字符为 1,否则为 0。若有多解,输出任意一组。

相邻两组输出之间留一个空行。

样例

3
3 3 1
3 3 3
3 3 4
110
100
000

010
111
100

010
111
010

数据范围

3≤n,m≤1000003\le n,m\le100000,0≤k≤1090\le k\le10^9。同一个输入文件内,所有数据的 ∑nm≤5000000\sum nm\le5000000。

下表为原赛子任务设置。

子任务 特殊限制 原赛分值 原赛依赖
1 nm≤16nm\le16 10 无
2 n=3n=3
3 n≤7n\le7,∑m≤100\sum m\le100
4 n≤7n\le7 1、2、3
5 k≤4(n−2)(m−1)k\le4(n-2)(m-1),n≤mn\le m 无
6 无 50 4、5

原 PDF 题面