时间限制 \(200ms\) | 空间限制 \(16MB\)
试构造一个 \(n \times m\) 的矩阵 \(s\),满足所有元素为 \([0,100]\) 之间的整数,且对于任意 \(i,j\ (i\neq j)\) 存在一个 \(k\) 使得 \(s_{i,k}>s_{j,k}\) 。
数据范围:
对于 \(100\%\) 的数据,\(1\leq n,m\leq 100,T=20\)
考虑构造。
容易发现,对于任意 \(i \ne j\),一定 \(\exists \space k_1, s_{i, k_1} > s_{j, k_1}\) 且 \(\exists \space k_2, s_{i, k_2} < s_{j, k_2}\)。
为了尽可能满足条件,我们令 \(k_1 = 1, k_2 = 2\)。
此时将每行的第一列按照 \(1,2,..,n\) 构造,第二列按照 \(n, n-1, ..., 1\) 构造即可。
注意判断无解情况。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <map> #include <cstdlib> #include <cmath> using namespace std; const int N = 105; int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } int T; int n, m; int Map[N][N]; int main() { T = read(), T = read(); while (T--) { n = read(), m = read(); if (n != 1 && m == 1) { puts("NO"); continue; } puts("YES"); if (n == 1 && m == 1) { puts("0"); continue; } for (int i = 1; i <= n; i++) { Map[i][1] = i; Map[i][2] = n - i + 1; } for (int i = 1; i <= n; i++) for (int j = 3; j <= m; j++) Map[i][j] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) printf("%d ", Map[i][j]); puts(""); } } return 0; }