题解：CF1385G Columns Swaps
fan_xiaoyi · · 题解
CF1385G Columns Swaps
思路
手玩一下样例，发现若按照数字类型连边，从上或下其中一个数字连入，另一个数字连出，会形成一个环状结构。
关于自环：换不换都一样，要使得交换次数最小显然不换。
先考虑单个环怎么做：若有一对数字都在上或者下，则选择其中一个上下交换，然后依次扩展到整个环。
显然会有两种方案，另一种就是把这一种中交换的位置不交换，不交换的位置交换。
所以先把每一个环单独找出来，然后计算出两种方案所需的交换次数，取其中较小的一种并加入输出标记，最后输出最小次数和以及交换位置即可。
环之间，由于没有相同数字，所以两种方案可以任意组合，不会相互影响。
这里给出一组由两个环组成的 hack 数据：
input:
3
7
1 1 4 5 2 7 3
2 3 6 6 4 5 7
4
2 1 3 2
1 3 4 4
11
1 1 4 5 2 7 3 9 8 10 9
2 3 6 6 4 5 7 8 10 11 11
output:
3
1 3 5
1
4
4
1 3 5 11第三组是把第二组按照相对顺序接在第一组后面。
代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pii pair<int,int>
#define double long double
#define tomin(a,b) a=min(a,b)
#define tomax(a,b) a=max(a,b)
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
template<typename T>inline void read(T &x){
x=0;int f=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
}
inline void read(char &c){
c=getchar();
while(isspace(c))c=getchar();
}
inline void read(std::string &s){
s.clear();char c=getchar();
for(;isspace(c);c=getchar());
for(;!isspace(c)&&c!=EOF;c=getchar())s+=c;
}
template<typename T,typename...Args>
void read(T &x,Args&...args){
read(x);read(args...);
}
template<typename T>void print(T x){
if(x<0)x=-x,putchar('-');
if(x>9)print(x/10);
putchar((x%10)^48);
}
inline void print(char c){
putchar(c);
}
inline void print(std::string s){
fep(i,0,s.size())putchar(s[i]);
}
inline void print(const char*s){
while(*s)putchar(*s++);
}
template<typename T,typename...Args>
void print(const T &x,const Args&...args){
print(x);print(args...);
}
}
using namespace std;
using namespace FastIO;
const int N=2e5+47;
int T,n,a[N],b[N],cnt[N];
int A[N],B[N],ans,bel[N];
pii l[N],r[N];
vector<int>res;
vector<vector<int>>grp;
void find(int x,int tim){
grp.push_back({});
queue<int>q;
q.push(x);
while(q.size()){
int u=q.front();q.pop();
if(bel[u])continue;bel[u]=tim;
int a1=l[a[u]].fir,a2=r[a[u]].fir;
int b1=l[b[u]].fir,b2=r[b[u]].fir;
if(!bel[a1])q.push(a1);
if(!bel[a2])q.push(a2);
if(!bel[b1])q.push(b1);
if(!bel[b2])q.push(b2);
}
}
void solve(int k){
int ans1=0,ans2=0;
rep(I,0,grp[k].size()-1){
int i=grp[k][I];
int L=l[a[i]].fir;
int R=r[a[i]].fir;
if(l[a[i]].sec!=r[a[i]].sec)continue;
int nxt=a[i],cur=a[i];
while(l[nxt].sec==r[nxt].sec){
L=l[nxt].fir;
R=r[nxt].fir;
swap(A[R],B[R]);cur=nxt;
nxt=A[R]+B[R]-cur;
if(R==r[nxt].fir)swap(l[nxt],r[nxt]);
swap(l[nxt].sec,r[cur].sec);
}
}
rep(I,0,grp[k].size()-1){
int i=grp[k][I];
if(A[i]!=a[i])ans1++;
if(B[i]!=a[i])ans2++;
}
ans+=min(ans1,ans2);
if(ans1<=ans2){
rep(I,0,grp[k].size()-1){
int i=grp[k][I];
if(A[i]!=a[i]){
res.push_back(i);
}
}
}
else{
rep(I,0,grp[k].size()-1){
int i=grp[k][I];
if(B[i]!=a[i]){
res.push_back(i);
}
}
}
}
signed main(){
read(T);
while(T--){
read(n);
rep(i,1,n)read(a[i]);
rep(i,1,n)read(b[i]);
ans=0;
grp.clear();
res.clear();
rep(i,1,n){
cnt[i]=bel[i]=0;
l[i]=r[i]={0,0};
A[i]=a[i],B[i]=b[i];
}
rep(i,1,n){
cnt[a[i]]++;
cnt[b[i]]++;
if(l[a[i]].fir==0)l[a[i]]={i,0};
else r[a[i]]={i,0};
if(l[b[i]].fir==0)l[b[i]]={i,1};
else r[b[i]]={i,1};
}
int flg=0;
rep(i,1,n)if(cnt[i]!=2){
flg=1;break;
}
if(flg){
puts("-1");
continue;
}
int tim=0;
grp.push_back({});
rep(i,1,n){
if(!bel[i]){
tim++;
find(i,tim);
}
}
rep(i,1,n){
grp[bel[i]].push_back(i);
}
fep(i,1,grp.size())solve(i);
print(ans,'\n');
fep(i,0,res.size()){
print(res[i],' ');
}
print('\n');
}
}