わたしの部屋

题目描述#

明白 你那份跳动的爱

别再 装作着无所谓的姿态

现在 就跟着节奏摇摆

将所有的伪装抛开

——阿良良木健《末日DISCO》

给定一个正整数 n，你需要构造 n 个集合 S₁, S₂, …, Sₙ，每个集合均含有 n 个元素，且满足：

1. 在每个集合中，每个数最多出现 1 次。

2. 任意两个集合 Sᵢ, Sⱼ 满足 i ≠ j，都有 |Sᵢ ∩ Sⱼ| = 1，即 Sᵢ 和 Sⱼ 的交集的大小均为 1。

3. 对于所有在 S₁, S₂, …, Sₙ 中出现过的元素 x，x 在所有集合的出现次数之和必须小于等于 2。

4. 集合中的元素 x 必须满足 1 ≤ x ≤ 10⁶。

输入描述#

一行一个正整数 n (1 ≤ n ≤ 500)。

示例#

输入

1
// 3

输出

1
// 1 2 3
2
// 3 4 5
3
// 1 5 6

接下来是题解。我们首先看示例，示例这里的正确输出其实不唯一，如下面这种矩阵

1
// 1 2 3
2
// 2 4 5
3
// 3 5 6

本人认为这种矩阵比示例的矩阵更有规律。n × n 的矩阵，对于每一行，从第 i 行的 i − 1 索引到该行的 n − 1 索引上的整数是连续的。对于每一列，从第 j 列的 j − 1 索引到该列的 n − 1 索引上的整数是连续的。行与列的规则相似，并且对于每一行/列，又有第 i 行/列 n−1 索引上的数(末尾上的数)，与第 i + 1 行/列 j 索引上的数连续。

注：i 或者 j 都满足 1 ≤ i, j ≤ n (该不会真的有人用第 0 行这种说法吧)，每行/列的索引是从 0 开始到 n − 1

题解代码-C语言版本

1
#define _CRT_SECURE_NO_WARNINGS //没错，我用的是VS2022
2
#include <stdio.h>
3

4
int main()
5
{
6
int n = 0;
7
int num = 1;
8
long arr[502][502] = { 0 };
9

10
scanf("%d", &n);
11

12
for (int i = 0, z = 0; i <= n - 1; i++, z++)
13
{
14
for (int j = z; j <= n - 1; j++)
15
{
16
arr[i][j] = num;
17
arr[j][i] = num++;
18
}
19
}
20

21
for (int i = 0; i <= n - 1; i++)
22
{
23
for (int j = 0; j <= n - 1; j++)
24
{
25
printf("%ld ", arr[i][j]);
26
}
27
printf("\n");
28
}
29

30
return 0;
31
}

核心代码

1
int num = 1;
2
.
3
.
4
.
5
for (int i = 0, z = 0; i <= n - 1; i++, z++)
6
{
7
for (int j = z; j <= n - 1; j++)
8
{
9
arr[i][j] = num;
10
arr[j][i] = num++;
11
}
12
}

这里使用行优先的双层 for 循环，i 是行对应索引，这里用一个变量 z 记录每一行递增序列的开始索引。这里看内层的循环，j 会初始化为 z 记录的值，也就是说我们仅从每一行递增序列的开始索引开始构造矩阵。因为这种矩阵的 (i, j) 位置上与 (j, i) 位置上的数是相同的，我们在对 (i, j) 位置上的元素赋值时同时对 (j, i) 位置赋值就行