题解 CF1491G 【Switch and Flip】
SSerxhs
2021-03-01 13:24:00
把 $c_i$ 看成图上存在一条 $i\to c_i$ 的边，则每个点恰有一条入边一条出边，可以证明图构成若干个环。
考虑如何同时处理两个环。
可以这样构造（下为 $c_i$）
231 564
234 561
134 562
124 563
123 564
123 465
123 456
这里通过一开始一次多余的操作，使每个数字恰好被操作两次。
于是我们通过 $|S_1|+|S_2|$ 次操作处理了两个环 $S_1,S_2$。
考虑对于剩下那个环怎么处理，一个简单而错误的想法是直接借一个已经归位的自环处理。
然而整张图可能就是一个大环，这时并不能用这种方法。
我们模仿上面的过程进行构造。
23451
32451
42351
52341
这里同样是借助多做一次操作，使 234 归位。
然而这里 5 不能再归位了，因为 1 和 2 的操作次数会不对。
这里我们继续使用一次操作使 1 操作次数正确。
51342
15342
12345
至此，通过 $|S|+1$ 次操作，成功解决了环 $S$。
总操作次数至多为 $n+1$。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
std::mt19937 rnd(time(0));
inline int sj(int n)
{
unsigned int x=rnd();
return x%n+1;
}
#define rand fst
template<typename typC> void read(register typC &x)
{
register int c=getchar(),fh=1;
while ((c<48)||(c>57))
{
if (c=='-') {c=getchar();fh=-1;break;}
c=getchar();
}
x=c^48;c=getchar();
while ((c>=48)&&(c<=57))
{
x=x*10+(c^48);
c=getchar();
}
x*=fh;
}
template<typename typC> void write(register typC x)
{
if (x<0) putchar('-'),x=-x;
static int st[100];
register int tp=1,y;st[1]=x%10;x/=10;
while (x) y=x/10,st[++tp]=x-y*10,x=y;++tp;
while (--tp) putchar(st[tp]|48);
}
template<typename typC> void write(register typC *a,register int num)
{
for (register int i=1;i<=num;i++) write(a[i]),putchar(i==num?10:32);
}
#define space(x) write(x),putchar(32)
#define enter(x) write(x),putchar(10)
const int N=1e6+2,M=1e6+2,p=998244353;
inline void inc(register int &x,const int y)
{
if ((x+=y)>=p) x-=p;
}
inline void dec(register int &x,const int y)
{
if ((x-=y)<0) x+=p;
}
inline int ksm(register int x,register int y)
{
register int r=1;
while (y)
{
if (y&1) r=(ll)r*x%p;
x=(ll)x*x%p;
y>>=1;
}
return r;
}
vector<int> bel[N];
char s[N];
int a[N],ed[N],st[N],ans[N][2];
int T,n,m,c,i,j,k,x,y,z,ass,la,tp;
int main()
{
read(n);
for (i=1;i<=n;i++) read(a[i]);
for (i=1;i<=n;i++) if (!ed[i])
{
ed[i]=i;bel[i].push_back(i);
for (j=a[i];j!=i;j=a[j]) ed[j]=i,bel[i].push_back(j);
}
for (i=1;i<=n;i++) if (ed[i]==i) st[++tp]=i;
for (i=1;i+1<=tp;i+=2)
{
x=st[i];y=st[i+1];
ans[++ass][0]=bel[x][0];ans[ass][1]=bel[y][0];
for (int i=1;i<bel[x].size();i++) ans[++ass][0]=bel[y][0],ans[ass][1]=bel[x][i];
for (int i=1;i<bel[y].size();i++) ans[++ass][0]=bel[x][0],ans[ass][1]=bel[y][i];
ans[++ass][0]=bel[x][0];ans[ass][1]=bel[y][0];
}
for (;tp&1;)
{
if (bel[st[tp]].size()==1) break;x=st[tp];
if (bel[x].size()==2)
{
for (i=1;i<=n;i++) if (i!=bel[x][0]&&i!=bel[x][1]) break;
ans[++ass][0]=bel[x][0],ans[ass][1]=i;
ans[++ass][0]=bel[x][1],ans[ass][1]=i;
ans[++ass][0]=bel[x][0],ans[ass][1]=i;break;
}
for (i=1;i+1<bel[x].size();i++) ans[++ass][0]=bel[x][0],ans[ass][1]=bel[x][i];
ans[++ass][0]=bel[x][1];ans[ass][1]=bel[x][bel[x].size()-1];
ans[++ass][0]=bel[x][0];ans[ass][1]=bel[x][bel[x].size()-1];
ans[++ass][0]=bel[x][1];ans[ass][1]=bel[x][0];
break;
}
printf("%d\n",ass);
for (i=1;i<=ass;i++) printf("%d %d\n",ans[i][0],ans[i][1]);
}
```