A5822. 「CTSC2016」单调上升序列
编程题
省选/NOI-
知识点
题目描述
对于一个带权无向图，我们可以考察它的单调上升路径。
一条路径被称为单调上升的，如果沿着它走时权值是单调递增的。
注意，路径由多条首尾相连的边组成，且可经过同一顶点多次。路径的长度为它包含的边数。
举例来说： 下图中 $v_2 \to v_4 \to v_1 \to v_2$ 是一条单调上升路径，因为每条边的权值依次为 $1,2,4$。这条路径的长度为 $3$。更进一步的，你可以验证下图中所有的单调上升路径的长度都不超过 $3$。
下面的结论指出在某些图中总会存在一个比较长的单调上升路径：
**结论**：假设带权无向图 $G$ 有 $100$ 个节点 $1000$ 条边，且所有权值各不相同。那么，$G$ 中一定存在一个单调上升路径，它的长度大于等于 $20$。
**证明**： 假设每个节点上有一个探险家。我们按权值从小到大枚举所有的边，每次将该边连接的节点中的探险家的位置进行对调。可以知道，每个探险家都走的是一条单调上升路径。另外，由于共有 $100$ 个探险家，而探险家一共走了 $2000$ 步，所以有人走了 $20$ 步。证毕。
现在，我们的问题是：
给定一个**完全图** $G$，它的顶点个数为一个**偶数** $N$。
你的任务是给每条边选一个不同的权值，要使得**最长的单调上升路径最短**。
一条路径被称为单调上升的，如果沿着它走时权值是单调递增的。
注意，路径由多条首尾相连的边组成，且可经过同一顶点多次。路径的长度为它包含的边数。
举例来说： 下图中 $v_2 \to v_4 \to v_1 \to v_2$ 是一条单调上升路径，因为每条边的权值依次为 $1,2,4$。这条路径的长度为 $3$。更进一步的，你可以验证下图中所有的单调上升路径的长度都不超过 $3$。
下面的结论指出在某些图中总会存在一个比较长的单调上升路径：
**结论**：假设带权无向图 $G$ 有 $100$ 个节点 $1000$ 条边，且所有权值各不相同。那么，$G$ 中一定存在一个单调上升路径，它的长度大于等于 $20$。
**证明**： 假设每个节点上有一个探险家。我们按权值从小到大枚举所有的边，每次将该边连接的节点中的探险家的位置进行对调。可以知道，每个探险家都走的是一条单调上升路径。另外，由于共有 $100$ 个探险家，而探险家一共走了 $2000$ 步，所以有人走了 $20$ 步。证毕。
现在，我们的问题是：
给定一个**完全图** $G$，它的顶点个数为一个**偶数** $N$。
你的任务是给每条边选一个不同的权值，要使得**最长的单调上升路径最短**。
输入格式
输入文件为
输入仅一行一个正偶数 $N$。
daydayup.in。输入仅一行一个正偶数 $N$。
输出格式
输出文件为
输出整数 $1$ 到 $\frac{N(N-1)}{2}$ 的一个排列，相邻的数之间用一个空格或换行隔开。
第一个数代表你给边 $(1,2)$ 选的权值；第二个数是给 $(1,3)$ 的权值，……，第 $N$ 个数是 $(1, N)$ 的权值；然后是 $(2,3)$ 的权值，$(2,4)$ 的权值，……，$(2, N)$ 的权值；然后是 $(3,4)$ 到 $(3, N)$ 的权值；以此类推；最后是 $(N − 1, N)$ 的权值。
daydayup.out。输出整数 $1$ 到 $\frac{N(N-1)}{2}$ 的一个排列，相邻的数之间用一个空格或换行隔开。
第一个数代表你给边 $(1,2)$ 选的权值；第二个数是给 $(1,3)$ 的权值，……，第 $N$ 个数是 $(1, N)$ 的权值；然后是 $(2,3)$ 的权值，$(2,4)$ 的权值，……，$(2, N)$ 的权值；然后是 $(3,4)$ 到 $(3, N)$ 的权值；以此类推；最后是 $(N − 1, N)$ 的权值。
输入输出样例
输入 #1
4
输出 #1
4 6 2 3 1 5
输入 #2
6
输出 #2
12 8 15 3 5 6 7 1 13 10 14 11 4 2 9
说明/提示
对于 $20\%$ 的数据，满足 $2 \le N \le 20$；
对于 $50\%$ 的数据，满足 $2 \le N \le 100$；
对于 $100\%$ 的数据，满足 $2 \le N \le 500$。
除不同的测试点有不同特点外，每个测试点你也可能获得部分分。如果你的程序能正确结束并按输出格式输出，我们将用下列方式评分：
假设你的图中最长单调上升路径的长度为 $A$，正确答案为 $B$。
- 如果 $A = B$，你的得分为 $10$ 分；
- 如果 $B < A < 2B$，你的得分为 $3$ 分；
- 如果 $A \ge 2B$，你的得分为 $0$ 分。
#### 提示
本题提供了一个额外的文件
该文件中有 $50$ 个表格。每一张这样的表格都满足一个很特别的性质。
你可以去观察一下这些表格。如果它们对你有帮助的话，你可以在你的程序中读取这个文件。
当然，你有另一种选择，那就是完全不理会这个文件。即便如此，你照样也可以解决本问题。
在评测时，该文件会与输入文件一样，与你的程序在同一个目录下，且文件名不会更改。
请注意：**不要在代码中直接粘贴该文件或是保存过大的常数表格，否则你的代码长度将可能超过比赛的代码长度限制而直接不予评测。**
对于 $50\%$ 的数据，满足 $2 \le N \le 100$；
对于 $100\%$ 的数据，满足 $2 \le N \le 500$。
除不同的测试点有不同特点外，每个测试点你也可能获得部分分。如果你的程序能正确结束并按输出格式输出，我们将用下列方式评分：
假设你的图中最长单调上升路径的长度为 $A$，正确答案为 $B$。
- 如果 $A = B$，你的得分为 $10$ 分；
- 如果 $B < A < 2B$，你的得分为 $3$ 分；
- 如果 $A \ge 2B$，你的得分为 $0$ 分。
#### 提示
本题提供了一个额外的文件
daydayup.tab。该文件中有 $50$ 个表格。每一张这样的表格都满足一个很特别的性质。
你可以去观察一下这些表格。如果它们对你有帮助的话，你可以在你的程序中读取这个文件。
当然，你有另一种选择，那就是完全不理会这个文件。即便如此，你照样也可以解决本问题。
在评测时，该文件会与输入文件一样，与你的程序在同一个目录下，且文件名不会更改。
请注意：**不要在代码中直接粘贴该文件或是保存过大的常数表格，否则你的代码长度将可能超过比赛的代码长度限制而直接不予评测。**