P8210 [THUPC 2022 初赛] 造计算机题目描述小R和小C听说贵系有一门造计算机的课之后吓得连夜提交了退学申请。开玩笑的啦正处于大一的他们对这门课不但不害怕甚至有些想笑。他们超强的动手能力甚至驱使他们想造一个玩意玩玩。当然由于他们毕竟才大一计算机专业课基本上都没上过经过长时间的艰苦奋战他们终于造出了一个奇怪的玩意这台计算机只有nnn个内存单元反而有足够多个寄存器。内存单元的编号从111到nnn寄存器从n1n1n1开始往上编号。每个内存单元和寄存器可以存储一个整数。目前他们已经设计好了一类指令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≤nm1 \leq i,j \leq nm1≤i,j≤nm并且满足题目中对于指令的限制条件。如果有多种设计指令的方案满足题目所需输出任意一种即可。你需要最小化mmm而无需最小化kkk但需要保证k≤106k \leq 10^6k≤106。输入数据保证符合要求的解存在。输入输出样例 #1输入 #12 2 1输出 #12 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)。可以证明m1m1m1是不行的。C实现#includebits/stdc.husingnamespacestd;constintN3e510;intgetint(){intx;scanf(%d,x);returnx;}inta[N];boolvis[N];vectorintr[N];intcnt0;vectorpairint,intans;voidswp(intx,inty){ans.emplace_back(min(x,y),max(x,y));swap(a[x],a[y]);}intmain(){intngetint();for(inti1;in;i)a[i]getint();a[n1]n1;a[n2]n2;for(inti1;in;i){if(!vis[i]){intui;while(!vis[u]){vis[u]1;r[cnt].push_back(u);ua[u];}cnt;}}vectorintcy;for(inti0;icnt;i)if(r[i].size()1)cy.push_back(i);if(cy.empty())returnputs(0 0),0;for(inticy.size()-1;i;--i)swp(r[cy[i]].back(),n2);swp(r[cy[0]].back(),n1);for(inti:r[cy[0]])swp(i,n2);swp(r[cy[0]].front(),n1);for(inti1;icy.size();i)for(intj:r[cy[i]])swp(j,n1);swp(n1,n2);printf(%d %d\n,2,(int)ans.size());for(autoi:ans)printf(%d %d\n,i.first,i.second);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容