BCJ! 并查集。

Table of Contents

  1. Description
  2. Solution

Description

$2n$个数站成两排（每个数在$2n$个数中最多出现两遍），一次操作可以交换任意一列中两个数，求使每行数不重复的最少操作数。

Solution

一道并查集好题， 似乎网路上用并查集过掉的人不很多， 不过思想是一致的。

考虑一个数字，假如她在不同列出现， 那么她们要么都反转，要么都不反转，这时候我们可以把她们放在一个集合里。

考虑在同一列出现了两次的数字，她们必然需要反转其中一个，那么这时反转的代价就是两者所在集合大小的较小值，这很显然。

但是直接用并查集维护不太好做，考虑带偏移量，对于情况一，她们间的距离必然为0，反之必然为1，这样在模2的剩余系下做就可以了。

当所有连接都做完后，每个联通块将互不影响，我们只需要统计每个联通块中两种状态的数量，取较小值就可以了。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;

const int maxn = 5e+4 + 5;
const int maxm = 1e+5 + 5;

int n, a[maxn], b[maxn], f[maxn], siz[maxn];
int dis[maxn], cnt[maxn], dt[maxn];
int bkta[maxm], bktb[maxm];
vector< pair<int, int> > vec;

int find(int x) {
  if (x == f[x]) return x;
  int rt = find(f[x]);
  dis[x] = (dis[x] + dis[f[x]]) % 2;
  return f[x] = rt;
}
int link(int x, int y, int d) {
  int fx = find(x), fy = find(y);
  if (fx == fy) {
    int del = (dis[x] + dis[y]) % 2;
    return (d + del) % 2;
  } else {
    int equ = (d - dis[x] + dis[y] + 2) % 2;
    f[fx] = fy; dis[fx] = equ; siz[fy] += siz[fx];
    return 0;
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    f[i] = i, siz[i] = 1;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    if (bkta[a[i]]) link(bkta[a[i]], i, 1);
    else bkta[a[i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &b[i]);  
    if (bktb[b[i]]) {
      link(bktb[b[i]], i, 1);
    } else {
      if (bkta[b[i]]) link(bkta[b[i]], i, 0);
      else bktb[b[i]] = i;
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    int fx = find(i);
    if (!dis[i]) ++cnt[fx];
  }
  for (int i = 1; i <= n; ++i) {
    int fx = find(i);
    if (!dt[fx]) {
      ans += min(cnt[fx], siz[fx] - cnt[fx]);
      dt[fx] = 1;
    }
  }
  printf("%d\n", ans);
  return 0;
}