CF1371D Grid-00100

疯狂科学家 Dr.Jubal 制作了一道竞赛编程题。请你来解决它！ 给定整数 $n, k$。请你构造一个 $n \times n$ 的网格 $A$，其中每个元素都是 $0$ 或 $1$。必须满足一个非常重要的条件：网格中所有元素的和恰好等于 $k$。换句话说，网格中 $1$ 的数量恰好为 $k$。 我们定义： - $A_{i,j}$ 表示第 $i$ 行第 $j$ 列的整数。 - $R_i = A_{i,1} + A_{i,2} + \cdots + A_{i,n}$（对于所有 $1 \le i \le n$）。 - $C_j = A_{1,j} + A_{2,j} + \cdots + A_{n,j}$（对于所有 $1 \le j \le n$）。 - 换句话说，$R_i$ 是第 $i$ 行的元素和，$C_j$ 是第 $j$ 列的元素和。 - 对于网格 $A$，我们定义 $f(A) = (\max(R) - \min(R))^2 + (\max(C) - \min(C))^2$（其中对于整数序列 $X$，$\max(X)$ 表示 $X$ 中的最大值，$\min(X)$ 表示 $X$ 中的最小值）。 请你找到任意一个满足上述条件的网格 $A$，并且使 $f(A)$ 的值尽可能小。在所有满足条件的网格中，任选一个输出即可。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来的 $t$ 行，每行包含两个整数 $n, k$（$1 \le n \le 300, 0 \le k \le n^2$）。 保证所有测试用例的 $n^2$ 之和不超过 $10^5$。

对于每个测试用例，首先输出一个整数，表示在所有满足条件的网格中，$f(A)$ 的最小可能值。 接下来输出 $n$ 行，每行包含 $n$ 个字符，第 $i$ 行第 $j$ 个字符为 $A_{i,j}$。 如果有多种答案，输出任意一种均可。

在第一个测试用例中，网格中所有元素的和等于 $2$，条件满足。$R_1 = 1, R_2 = 1$，$C_1 = 1, C_2 = 1$。因此，$f(A) = (1-1)^2 + (1-1)^2 = 0$，这是 $f(A)$ 的最小可能值。 在第二个测试用例中，网格中所有元素的和等于 $8$，条件满足。$R_1 = 3, R_2 = 3, R_3 = 2$，$C_1 = 3, C_2 = 2, C_3 = 3$。因此，$f(A) = (3-2)^2 + (3-2)^2 = 2$。可以证明，这就是 $f(A)$ 的最小可能值。 由 ChatGPT 4.1 翻译