G. Columns Swaps
题意
给出一个2×n的矩阵 (n<2e5)
要求每列最多交换一次使得矩阵两行均为[1,n]的排列
[1,n]的排列指[1,n]中每个数有且只有出现一次
问最少要交换几列才能变成2层排列 或者无法变为两层排列输出-1
输出交换次数以及需要交换哪几列
题解
首先判断不可能构成两层排列的情况
比如
1 1 2
3 2 2
其中2出现了3次,3出现了1次 这种情况无论如何变化都不能构成两层排列
所以显然当且仅当所有数在矩阵中出现2次才可能构成符合题意的解
我们将每列建一条无向边
每两个相同的数建一条无向边
对于相同的两个数在同一列则忽略
然后我们就得到了多个环构成的图
对于样例
5 3 5 1 4
1 2 3 2 4
它画出的图如下：
将环上的每个点黑白染色后 发现同色的需要在同一行
于是可以用dfs 将环上每个点染色后判断哪种颜色在第一行需要的操作更少
注意存在多个独立环 每个环需要独立判断最优操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e5+5;
const double Pi=acos(-1);
const ll mod=1e9+7;
int data[2*Max];
vector<int>mp[2*Max];
vector<int>pos[Max],shiftA,shiftB;
int color[2*Max],n;
bool vis[2*Max];
void dfs(int now,int fa){
for(auto i:mp[now]){
if(i==fa||vis[i])continue;
vis[i]=1;
color[i]=3-color[now];
if(i<=n){
if(color[i]==1)shiftA.push_back(i);
else shiftB.push_back(i);
}
dfs(i,now);
}
}
int main() {
Turnoff;
int t;cin>>t;
while(t--){
cin>>n;
bool flag=0;
for(int i=1;i<=n;i++)pos[i].clear();
for(int i=1;i<=n;i++)cin>>data[i],pos[data[i]].push_back(i);
for(int i=n+1;i<=2*n;i++)cin>>data[i],pos[data[i]].push_back(i);
for(int i=1;i<=n;i++){
if(pos[i].size()!=2){
flag=1;
break;
}
}
if(flag)cout<<-1<<endl;
else{
int bios=n;
for(int i=1;i<=2*n;i++)mp[i].clear();
for(int i=1;i<=2*n;i++){
vis[i]=0;color[i]=0;
if(i<=n&&data[i]==data[i+bios])continue;
if(i>n&&data[i-bios]==data[i])continue;
if(i<=n)mp[i].push_back(i+bios);
else mp[i].push_back(i-bios);
int Samenumpos=pos[data[i]][0]!=i?pos[data[i]][0]:pos[data[i]][1];
mp[i].push_back(Samenumpos);
}
vector<int>ans;
for(int i=1;i<=2*n;i++){
if(i<=n&&data[i]==data[i+bios])continue;
if(i>n&&data[i-bios]==data[i])continue;
if(vis[i])continue;
color[i]=1;dfs(i,0);
if(shiftA.size()<shiftB.size())for(auto i:shiftA)ans.push_back(i);
else for(auto i:shiftB)ans.push_back(i);
shiftA.clear();shiftB.clear();
}
cout<<ans.size()<<endl;
for(auto i:ans)cout<<i<<" ";
cout<<endl;
}
}
}
|