【NOIP】1999真题解析 luogu-P1014 Cantor 表 | GESP三、四级以上可练习
NOIP 1999 普及组真题，主要考察简单的二维矩阵模拟与通过寻找数学规律进行时间复杂度优化。可以用模拟法暴力求解，也能通过总结对角线的排列规律实现高效求解。GESP三、四级以上可练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。
luogu-P1014 [NOIP 1999 普及组] Cantor 表
题目要求
题目描述
现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：
我们以 Z 字形给上表的每一项编号。第一项是 $1/1$，然后是 $1/2$，$2/1$，$3/1$，$2/2$，…
输入格式
整数 $N$（$1 \leq N \leq 10^7$）。
输出格式
表中的第 $N$ 项。
输入输出样例 #1
输入 #1
1
7
输出 #1
1
1/4
说明/提示
- 2024-11-18 0:30 数据中加入了样例，放在不计分的子任务 2 中。
题目分析
这道题考察了一定程度上的模拟能力和寻找数学规律的能力。问题要求找出 Z 字形遍历下第 $N$ 个分数的值（用 行号/列号 来表示）。我们可以有两种思路来求解。
1. 朴素模拟法（游走法）
我们已知起点为第 $1$ 行第 $1$ 列（$1/1$），通过观察可以发现从当前项走到下一项的规律。当走到网格边界时，会发生平移并改变方向：
- 如果碰到上边界（第一行）：向右平移一格，接着沿对角线向左下方移动。
- 如果碰到左边界（第一列）：向下平移一格，接着沿对角线向右上方移动。
- 如果处于内部区域，则按照原定方向继续在对角线上移动。
这种算法基于纯粹的位置模拟，每次循环走一步。对于本题 $N \le 10^7$ 的测试数据范围，执行一千万次循环在这个时间级别的评测中是可以勉强通过的（时间复杂度为 $O(N)$）。代码中通过控制变量和布尔值方向实现了路径的精准模拟。
2. 数学规律优化法
朴素法因为要一步一步模拟，时间开销会随着 $N$ 的变大而线性增长。如果我们分析一下对角线的规律，就可以大大优化运算过程。
我们可以把按 Z 字形走过的一条条斜线看作是“对角线”，观察如下特征：
- 第 $1$ 条对角线有 1 个元素：$1/1$
- 第 $2$ 条对角线有 2 个元素：$1/2$, $2/1$
- 第 $3$ 条对角线有 3 个元素：$3/1$, $2/2$, $1/3$
- 第 $k$ 条对角线就有 $k$ 个元素，并且这上面所有的分数，其 分子（行号）和分母（列号）之和恒等于 $k + 1$。
如何确定第 $N$ 项属于第几条对角线？ 我们可以通过不断从被减数 $N$ 中减去当前对角线的容量 $k$（$1, 2, 3…$），直到不够减时，剩余的 $N$ 即为这一项在第 $k$ 条对角线中的排位编号。此时寻找所在对角线的时间复杂度骤降至 $O(\sqrt{N})$ 级别，效率极高。
如何确定该对角线上的每一项具体的走向？ 注意对角线的奇偶性决定了走向：
- 偶数对角线（如第 2、4 条）的规律是：从右上端点指向左下端点生成。以第 2 条中的顺序 $1/2 \rightarrow 2/1$ 为例，可以看到行号增加、列号减少。在这种情况下，其第 $n$ 个元素的分子（行号）就是直接与其顺序 $n$ 相同，分母（列号）即为 $k + 1 - n$。
- 奇数对角线（如第 1、3 条）的顺序则是：从左下端点指向右上端点，方向为行号减小、列号增加。此时第 $n$ 个元素的 列号 会等于顺序 $n$，而 分子 为 $k + 1 - n$。
利用这两个结论，便可以直接通过运算一次求得对应的分母与分子，不再需要循环模拟每一项的演变。
示例代码
解法一：朴素模拟法（时间复杂度 $O(N)$）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
int main() {
int n;
std::cin >> n; // 读取输入的项数 N
// 初始化位置为表的第一项，即第 1 行第 1 列 (值为 1/1)
int row = 1, col = 1;
// 记录当前的移动状态
bool row_down = true; // 是否准备或正在向左下方（行增列减）移动
bool col_right = true; // 是否准备改变方向标志位
// 模拟从第 2 项走到第 N 项的移动过程
for (int i = 2; i <= n; i++) {
if (row == 1) { // 如果当前到达了第一行（上边界）
if (col_right) { // 碰到上边界后，需要向右平移一步进入下一条对角线
col++; // 向右移动一格
col_right = false; // 标记平移结束
row_down = true; // 接下来准备沿着对角线向左下方移动
} else { // 正在向左下方移动的过程中
row++; // 行号增加
col--; // 列号减少
col_right = true; // 恢复标记，以便之后碰到边界时判定
}
} else if (col == 1) { // 如果当前到达了第一列（左边界）
if (row_down) { // 碰到左边界后，需要向下平移一步进入下一条对角线
row++; // 向下移动一格
row_down = false; // 标记平移结束
col_right = true; // 接下来准备沿着对角线向右上方移动
} else { // 正在向右上方移动的过程中
row--; // 行号减少
col++; // 列号增加
}
} else { // 如果当前在中间区域（没有碰到第一行或第一列的边界）
if (row_down) { // 正在向左下方移动
row++; // 行号增加
col--; // 列号减少
} else { // 正在向右上方移动
row--; // 行号减少
col++; // 列号增加
}
}
}
// 输出第 N 项的结果，格式为：行号/列号（第一行是 1/1, 1/2...
// 行号即分子，列号即分母）
std::cout << row << "/" << col << std::endl;
return 0;
}
解法二：数学规律优化法（时间复杂度 $O(\sqrt{N})$）推荐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
int main() {
int n;
std::cin >> n;
int k = 1; // k 表示当前所在的第几条对角线
// 利用减法定位 n 属于哪一条对角线
// 每次减去当前对角线上的元素数量 k
while (n > k) {
n -= k;
k++;
}
// 循环结束后，变量 k 就是第 N 项所在的对角线编号
// 而此时的剩余值 n，即为元素在这条对角线上的顺序编号
if (k % 2 == 0) {
// 如果是偶数对角线，顺序是从右上到左下移动
// 行号从小到大（等于此时的排位 n），列号从大到小
// 根据 行+列 = k+1 的规律：
std::cout << n << "/" << k + 1 - n << std::endl;
} else {
// 如果是奇数对角线，顺序是从左下到右上移动
// 列号从小到大（等于此时的排位 n），行号从大到小
std::cout << k + 1 - n << "/" << n << std::endl;
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
