THUPC D 造计算机 题解

时间限制： 1.0 秒

空间限制： 512 MiB

相关文件： 题目目录

题目描述

小 R 和小 C 听说贵系有一门造计算机的课之后吓得连夜提交了退学申请。

开玩笑的啦！正处于大一的他们对这门课不但不害怕，甚至有些想笑。他们超强的动手能力甚至驱使他们想造一个玩意玩玩。

当然由于他们毕竟才大一，计算机专业课基本上都没上过，经过长时间的艰苦奋战，他们终于造出了一个奇怪的玩意：

这台计算机只有 $n$ 个内存单元，反而有足够多个寄存器。内存单元的编号从 $1$ 到 $n$ ，寄存器从 $n+1$ 开始往上编号。每个内存单元和寄存器可以存储一个整数。

目前他们已经设计好了一类指令：swap i, j，表示交换编号为 $i$ 和 $j$ 的单元里的数，其中 $i$ 和 $j$ 均为正整数且 $i \neq j$ 。他们打算写一段程序来测试这条指令。

最开始， $n$ 个内存单元中乱序存放着 $1\sim n$ 这些数，且每个数恰好出现一次。而每个寄存器里存放的是它的编号。

两人打算设计一段指令序列，使得计算机依次执行完这些指令后，所有内存和寄存器中的数都归位，也就是恰好等于它自己的编号。

虽然没学过计算机专业课，小R和小C还是懂一点皮毛的，因此他们规定每条swap指令操作的两个位置至少有一个需要是寄存器，也就是 $i$ 和 $j$ 至少有一者应当大于 $n$。

然而，正当他们写完程序开始运行时，却发现系统崩溃了！在查找了半天原因后，他们发现了一个奇怪的bug：他们设计出来的计算机不能运行两条相同的指令！也就是说，他们不能在一段程序里出现两条相同的swap i, j指令。更进一步他们发现即使出现一条swap i, j一条swap j, i也不行，因为计算机会自动将这两条指令视为同一条。

然后可怜的小R和小C就斯巴达了。不过他们在弃疗之前还是打算利用现有的架构把程序写出来。不仅如此，他们还希望用到的寄存器数量尽可能少。你能帮帮他们吗？

输入格式

从标准输入读入数据。

第一行：一个正整数 $n\ (1 \leq n \leq 10^5)$ 表示内存单元的数量。

第二行： $n$ 个正整数$a_i$ 依次表示第 $i$ 个内存单元中的初始值，保证所有 $a_i$ 构成一个 $1 \sim n$ 的排列。

输出格式

输出到标准输出。

第一行：两个非负整数$m,k$，分别表示你用到的寄存器数量和指令的条数。

接下来$k$行，每行输出两个正整数$i, j$，依次表示你设计的每一条指令中交换的两个位置。你需要保证 $1 \leq i,j \leq n+m$ ，并且满足题目中对于指令的限制条件。

如果有多种设计指令的方案满足题目所需，输出任意一种即可。

你需要最小化 $m$ 而无需最小化 $k$ ，但需要保证$k \leq 10^6$。输入数据保证符合要求的解存在。

样例1输入

1
2

2
2 1

样例1输出

样例1解释

最初，前 $4$ 个单元的值依次为 $(2,1,3,4)$ 。

执行指令swap 3, 4，各单元的值变为 $(2,1,4,3)$ 。

执行指令swap 1, 3，各单元的值变为 $(4,1,2,3)$ 。

执行指令swap 2, 4，各单元的值变为 $(4,3,2,1)$ 。

执行指令swap 1, 4，各单元的值变为 $(1,3,2,4)$ 。

执行指令swap 2, 3，各单元的值变为 $(1,2,3,4)$ 。

可以证明 $m=1$ 是不行的。

首先肯定会考虑按照排序的方法进行移动，但是如果寄存器的数量是 $m$ 个我们就必须满足每个位置被使用的次数 $\le m$。

我们考虑对于一个排律本质就是一个置换，我们将置换中的所有环都拿出来看，对于一个环来说我们可以进行构造出 $m = 2$ 的解。

考虑对于置换环 $p[i_1] = i_2, p[i_2] = i_3 ,\cdots, p[i_k] = i_1 $，我们考虑让：

$$
\begin{aligned}
&\tt swap(i_1, n + 1) \\
&\tt swap(i_2, n + 1) \\
&\cdots \\
&\tt swap(i_{k - 1}, n + 1) \\
&\tt swap(i_k, n + 2) \\
&\tt swap(i_k, n + 1) \\
&\tt swap(i_1, n + 2)
\end{aligned}
$$

我们做完所有的操作之后再看 $n + 1, n + 2$ 的位置是否合法，不合法就进行一次交换。

这个解法本质是依据 $\tt swap(i, j)$ 在实现的时候需要引入一个变量，但是考虑环的情况我们最后一步是不能直接使用当前变量的，所以我们需要再引入一个变量。