問題描述

有 \(n(n \le 20)\) 個數 \(0 \sim n - 1\)，現在要選出若干個數。

給定 \(m \le 2 \times 10^5\) 條限制，每條限制給定集合 \(S \subseteq \{0, 1, 2, \dots n - 1\}\)，要求選出的數中至少有一個 \(x \in S\)。問至少需要選出幾個數。

解決方式

令全集 \(U = \{0, 1, 2, \dots, n - 1 \}\)。

考慮每種選取方式。對于每條限制，直接做比較復雜，考慮反面：令 \(P = \complement_U S\)，那么所有 \(P\) 的子集都不滿足要求。在 \(P\) 位置打個標記，最后做高維前綴和即可。

時間復雜度：\(O(nm + n2^n)\)。

#include <bits/stdc++.h>

using namespace std;

const int MAXU = (1 << 20);

int n, m, f[MAXU];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  int U = (1 << n) - 1; //全集
  for (int i = 1, k; i <= m; i++) {
    cin >> k;
    int u = 0;
    for (int x; k--; ) {
      cin >> x, u ^= (1 << x);
    }
    f[U ^ u]++; // 打標記
  }
  for (int i = 0; i < n; i++) { // 高維前綴和
    for (int j = U; j >= 0; j--) {
      if (((j >> i) & 1) ^ 1) {
        f[j] += f[j ^ (1 << i)];
      }
    }
  }
  int ans = n;
  for (int i = 0; i <= U; i++) {
    if (f[i]) continue;
    int c = 0;
    for (int x = 0; x < n; x++) {
      c += ((i >> x) & 1);
    }
    ans = min(ans, c);
  }
  cout << ans;
  return 0;
}

現在你應該已經會了吧，來試試 CF1995D。