Codeforces Round 773

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘

D

https://codeforces.com/contest/1641/problem/D

n(1e5)个数组

每个数组长度为m(<=5), 包含值(<1e9), 每个数组有总代价w(<=1e9)

找出两个数组，让它们的值没有重复，且代价和最小，求最小代价

题解

  1. 随机映射到0-15,注意同一个数一定映射到相同数，不同数可能映射到相同数, 多次运行提高概率期望到2, orz(见YB Lin 的链接)

  2. 集合数学性质

一个集合属于A,又属于B，

如果该集合个数为奇数，则+1

如果该集合个数为偶数(包含空集合)，则-1

那么，如果A,B有公共元素，则结果为0，否则为1

然后维护一个Trie树，上面是所有子集

把原数组按照w排序

利用Trie树找到首个合法的组合i,j

因为要答案最小，所以 i < i’, 则有 j’< j

代码

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define pb push_back
#define all(a) a.begin(), a.end()

// trie 树， 用index取代指针
// 集合按照从小到大 展开存成树节点
struct node {  // 只会新增不会移除， cnt为0 和 移除等价
  unordered_map<int, int> next;  // [值] => 树节点index
  int cnt;
};

vector<node> g;

int new_node() {
  g.push_back(node{{}, 0});
  return g.size() - 1;
}

// 新把数组变化 放入trie树
void add(const vector<int>& x,
         int c /* 1(加入) or -1(移除) */,
         int v = 0 /* trie 树 节点 index*/,
         int i = 0 /* 遍历数组下标 */) {
  if (i == x.size()) {
    g[v].cnt += c;  // 在trie树 的所有集合表示的位置都+1
    return;
  }
  // 不存在创建新节点
  if (!g[v].next.count(x[i]))
    g[v].next[x[i]] = new_node();
  add(x, c, v, i + 1);                // 不选择当前的情况
  add(x, c, g[v].next[x[i]], i + 1);  // 选择当前的情况
}

// 初始全是0
// 如果和 已经加入的 某个数组重合，那么与这个数组贡献的cnt 的结果为 0
// 如果和 已经加入的 某个数组不重合，那么与这个数组贡献的cnt 的结果为 1
// 而trie上的贡献是满足**累加**性质，所以与 trie树直接计算cnt
// 如果为0，则和所有数组现有的都冲突，否则存在一个数组和它没有重合
int get_cnt(const vector<int>& x, int v = 0, int i = 0) {
  if (i == x.size()) {
    return g[v].cnt;
  }
  int res = get_cnt(x, v, i + 1);  // 第i位 不选
  if (g[v].next.count(x[i]))       // 第i位 存在（集合存在） 并选择
    res -= get_cnt(x, g[v].next[x[i]] /* trie 树的下一个节点 */,
                   i + 1);  // 奇偶加减交替
  return res;
}

int main() {
  int n, k;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  vector<pair<int, vector<int>>> a = vector(n, make_pair(0, vector<int>(k, 0)));
  rep(i, 0, n) {
    rep(j, 0, k) {
      cin >> a[i].second[j];  // 读入每个数组
    }
    cin >> a[i].first;  // 数组权重
  }
  rep(i, 0, n) {  // 数组内按照值排序
    sort(all(a[i].second));
  }
  sort(all(a));  // 按权重排序
  new_node();    // trie 根节点 空集合
  int res = -1;
  int i = 0;
  // 和 trie 树中 任何一个重复 都会 让 get_cnt > 0
  while (i < n && !get_cnt(a[i].second)) {
    // 首个一定加入, 如果和现有所有数组都冲突，那么加入trie树
    // 如果存在一个不是和所有都冲突的 , 会触发 get_cnt 不为0
    add(a[i].second, 1);
    i += 1;
  }
  if (i >= n) {
    cout << -1 << "\n";
    return 0;
  }
  // i 是首个 与 [0...i-1]中某个不会冲突的
  int j = i;
  // 从i倒向查找
  while (get_cnt(a[i].second)) {  // 直到所有都冲突，找到一个最小的j
    j -= 1;
    add(a[j].second, -1);  // 每次从trie树中移除一个
  }
  // j < i 互相不冲突, 最小的i对应的最小的j
  res = a[i].first + a[j].first;
  // j' < j < i < i'
  for (i += 1; i < n && j > 0; ++i) {
    while (get_cnt(a[i].second)) {  // 循环直到 和 前面都冲突
      j -= 1;                       // 找一个 最小的j 让 i和j不冲突
      add(a[j].second, -1);         // 移除
    }
    // 不一定是有效值（可能i,j是冲突的），但是因为代价排序关系，保证不会影响最小值
    res = min(res, a[i].first + a[j].first);
  }
  cout << res << "\n";
  return 0;
}

总结

  1. 先按照价值排序，
  2. 再从小到大找到首个和前面某个不冲突的
  3. 找到前面最小的与当前不冲突的，确定一个合法j < i
  4. i增加，每次找更小的j与新的i不冲突的，或者找不到跳过这个i, 每次更新最小值

关键的核心就是,trie树保存的是两两冲突的数组的所有集合，而与trie树 做子集重合get_cnt运算，如果与已加入的所有都有重合则总结果为0，否则大于0, 相当于trie能帮助完成批量判断

ref

官方题解

YB Lin 概率映射 sosdp 乱搞

neweryyy