当前位置：首页 > news >正文

打卡信奥刷题（3212）用C++实现信奥题 P8210 [THUPC 2022 初赛] 造计算机

news 2026/5/5 8:09:55

P8210 [THUPC 2022 初赛] 造计算机

题目描述

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

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

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

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

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

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

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

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

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

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

输入格式

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

第二行：nnn个正整数aia_iai依次表示第iii个内存单元中的初始值，保证所有aia_iai构成一个1∼n1 \thicksim n1∼n的排列。

输出格式

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

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

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

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

输入输出样例 #1

输入 #1

2 2 1

输出 #1

2 5 3 4 1 3 2 4 1 4 2 3

说明/提示

【样例解释】

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

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

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

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

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

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

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

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+10;intgetint(){intx;scanf("%d",&x);returnx;}inta[N];boolvis[N];vector<int>r[N];intcnt=0;vector<pair<int,int>>ans;voidswp(intx,inty){ans.emplace_back(min(x,y),max(x,y));swap(a[x],a[y]);}intmain(){intn=getint();for(inti=1;i<=n;i++)a[i]=getint();a[n+1]=n+1;a[n+2]=n+2;for(inti=1;i<=n;i++){if(!vis[i]){intu=i;while(!vis[u]){vis[u]=1;r[cnt].push_back(u);u=a[u];}++cnt;}}vector<int>cy;for(inti=0;i<cnt;i++)if(r[i].size()>1)cy.push_back(i);if(cy.empty())returnputs("0 0"),0;for(inti=cy.size()-1;i;--i)swp(r[cy[i]].back(),n+2);swp(r[cy[0]].back(),n+1);for(inti:r[cy[0]])swp(i,n+2);swp(r[cy[0]].front(),n+1);for(inti=1;i<cy.size();i++)for(intj:r[cy[i]])swp(j,n+1);swp(n+1,n+2);printf("%d %d\n",2,(int)ans.size());for(autoi:ans)printf("%d %d\n",i.first,i.second);return0;}