1 P7873 「SWTR-07」Scores
2 题目描述
时间限制 \(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\)
3 题解
考虑构造。
容易发现，对于任意 \(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\) 构造即可。
注意判断无解情况。
4 代码（空格警告）：
#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;
}