题解：P11912 [PA 2025] 集合 2 / Zbiory 2

· · 题解

前言

基本承袭 gcx12012 大佬的思路，但删除部分显然有更简洁的做法。另外代码并不会多一次操作。

Solution

我们考虑维护当前构造的集合 S，记目标集合为 T。初始时我们令 S=A_n，其实可以令其为任意的 A_i。

枚举 i=1,\dots,n，用 A_i 去更新 S：

  1. 若 i \in S 且 i \notin T，我们需要把 i 从 S 中删去，即 S \leftarrow S \backslash A_i，因为 A \backslash B = A \cap \overline{B}，所以我们，只要求一个 A_i 的补集，再与 S 求交集即可。
  2. 若 i \notin S 且 i \in T，直接 S \leftarrow S \cup A_i。

至多 2n 次操作。

可以任意你喜欢的数据结构（比如数组）维护 S，更新时暴力更新即可，时间复杂度是调和级数的（“本题非同寻常的时空限制”是何意味）。

Code

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define _rep(i, l, r) for (int i = (l); i >= (r); i--)

using namespace std;

constexpr int N = 5e4 + 10;

struct Operation {
  int op, x, y;
  Operation(int op, int x, int y) : op(op), x(x), y(y) {}
};
vector<Operation> ans;

bitset<N> s, t;

signed main() {
  int n, k;
  cin >> n >> k;
  rep(i, 1, k) {
    int b;
    cin >> b;
    t[b] = 1;
  }

  int idx = n;
  s[n] = 1;
  rep(i, 1, n) {
    if (s[i] && !t[i]) {
      ans.emplace_back(3, i, 0);
      ans.emplace_back(2, idx, idx + 1);
      idx += 2;
      for (int j = i; j <= n; j += i)
        s[j] = 0;
    } else if (!s[i] && t[i]) {
      ans.emplace_back(1, idx, i);
      idx++;
      for (int j = i; j <= n; j += i)
        s[j] = 1;
    }
  }

  cout << ans.size() << "\n";
  for (auto v : ans) {
    if (v.op == 3)
      cout << v.op << " " << v.x << "\n";
    else
      cout << v.op << " " << v.x << " " << v.y << "\n";
  }

  return 0;
}

后记

并不认为这道题很简单，感觉方向容易找错，比如本人刚开始一直考虑构造出单元素集合再求并，但那样顶多做到 2n+2k。