「CCPC Final 2020 D」Data Structure

2025 年 5 月 7 日

$1$ 到 $n$ 的正整数各出现两次，共 $2n$ 个数，分布在 $m\ (m\geq n)$ 个大小至多为 $2$ 的栈中。你可以进行至多 $\lceil \frac{3}{2}n \rceil$ 次如下操作：弹出一个栈的栈顶元素并压入另一个栈中，要求另一个栈是空的或该栈只有一个元素且该元素数值上等于要压入的元素。构造一个操作序列或报告无解，要求操作结束后的 $m$ 个栈满足栈要么为空要么恰包含两个相同的数。

$1 \leq n \leq m \leq 2 \times 10^{5}$ 。

题解

考虑构建依赖图 $G$ ：每个 $1$ 到 $n$ 的数字对应图 $G$ 中的一个节点；对于原始分布每个大小为 $2$ 的栈 $\{ b,t \}$ （其中 $b$ 为栈底元素， $t$ 为栈顶元素），建边 $\texttt{t} \to \texttt{b}$ ，表示 $t$ 被“删除”了之后才能使用 $b$ ，其中“删除”定义为：对于 $x\ (1\leq x\leq n)$ ，通过若干次操作将其移动到同一个栈中，之后可将这个数字和这个栈都删除。

再考察 $1$ 到 $n$ 中的每个数在原始分布中的位置：如果其位于栈底记为 $\texttt{0}$ ，如果不位于栈底记为 $\texttt{1}$ （即位于栈顶并且栈大小为 $2$ ），则一共有三种情况：

$\texttt{00}$ ：即两次出现都在栈底，这样的数在 $G$ 中没有出边。删除一个 $\texttt{00}$ 节点可以获得一个空栈。
$\texttt{01}$ ：即两次出现一次在栈底一次不在栈底。如果这两次出现就是在同一个栈中，可以直接“删除”这个数。否则，他在 $G$ 中应恰有一条出边和至多一条入边。不妨把他“压缩”到其出边节点中，在删除其出边节点时将其先删除——注意到删除 $\texttt{01}$ 节点没有其他影响，只需要一次操作，并且不依赖于空栈进行中转。“压缩”操作是支持多跳的，最后所有 $\texttt{01}$ 节点都会被压缩到 $\texttt{00}$ 节点上。
$\texttt{11}$ ：即两次出现都不在栈底，这样的数在 $G$ 中没有入边，并且一定有 $2$ 条出边（除了某种特殊情况，一组 $\texttt{00}$ 和 $\texttt{11}$ 直接依赖，这是容易特殊处理的）。删除一个 $\texttt{11}$ 节点需要消耗一个空栈。

可以证明，如果对所有 $\texttt{01}$ 节点都应用“压缩”操作，则依赖图 $G$ 将变为一个二分图（除了由 $\texttt{01}$ 节点构成的环），其中左侧节点全为 $\texttt{00}$ 节点，右侧节点全为 $\texttt{11}$ 节点。因为删除 $\texttt{00}$ 节点可以获得空栈而删除 $\texttt{11}$ 节点需要消耗空栈，我们希望尽可能先删除 $\texttt{00}$ 节点，故提出以下构造流程：

循环，每次按照以下方法删除一个节点，直到所有节点均被删除：
- 若存在入度为 $0$ 的 $\texttt{00}$ 节点，将其删除；可获得一个空栈。
- 若存在入度为 $1$ 的 $\texttt{00}$ 节点，删除指向其的 $\texttt{11}$ 节点；需消耗一个空栈，如不存在空栈则无解——删除后这一 $\texttt{00}$ 节点的度数变为 $0$ ，会在紧接着的下一次的循环中被删除——这样刚消耗的空栈又能重新获得，无后效性。
- 若存在入度为 $2$ 的 $\texttt{00}$ 节点，删除指向其的 $11$ 节点中的任一个；需消耗一个空栈，如不存在空栈则无解——但会将这个 $\texttt{00}$ 节点的度数变为 $1$ ，并且会通过后续循环将整个联通块删空——注意来到这一分支说明依赖图 $G$ 只剩下两侧节点的度数均为 $2$ 的联通块，要删除这样的联通块要求空栈个数至少为 $2$ ，删完整个联通块之后空栈个数仍不变，无后效性。

可以证明如果存在解一定能通过这种方法找到——因为我们总是尽可能优先地获取空栈，并且删完一组后空栈个数不变。对于上文提到的一些特殊情况和细节，这里详细说明：

一对 $\texttt{00}$ 和 $11$ 节点直接关联，即在原始分布中出现形如 $\{ s,t \}$ 、 $\{ s,t \}$ 的两个栈。这就是前文提到的特殊情况，这可以被刚刚提到的算法解决而无需特判（因为根据我们的算法自然会先删 $t$ 再删 $s$ ）。
若干 $\texttt{01}$ 节点相互连接在依赖图 $G$ 中形成环。这种结构的“删除”只能特殊处理，并且必须临时借用一个空栈，借不到则为无解。
虽然需要压缩的 $\texttt{01}$ 节点只有恰好一条出边，但是对于底层的 $\texttt{00}$ 节点可能有至多两条来自 $\texttt{01}$ 节点的入边；换句话说，删除 $\texttt{00}$ 节点之前要先删除的 $\texttt{01}$ 节点会构成两条链的形状，实现时应注意这一细节。

关于操作次数：

对于成环的 $\texttt{01}$ 节点，设环长为 $k$ ，则均摊次数为 $\frac{k+1}{k} \leq \frac{3}{2}$ 。
对于其他的删除， $\texttt{11}$ 节点需要 $2$ 次， $\texttt{00}$ 和 $\texttt{01}$ 节点只需要 $1$ 次，但每产生 $\texttt{11}$ 节点至少需要一个 $\texttt{00}$ 节点或两个 $\texttt{01}$ 节点，故均摊次数仍 $\leq \frac{3}{2}$ 。

代码

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define log(...) (void(0))
#define endl '\n'
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
using lll = __int128;

const int N = 2e5 + 9;
int n, m, k[N], a[N][2], l[N], trans10[N];
vector<int> trans01[N];
bool mark[N];
set<int> st[3];
vector<int> emp, lr[N], rl[N], sim[N];
vector<pair<int, int>> ans;

struct position {
  int s, p;
} p[N][2];

int sum_pos(int x) { return p[x][0].p + p[x][1].p; }

void delnum(int x) {
  log("! delnum x=%d\n", x);
  assert(mark[x] == false);
  mark[x] = true;
  for (int r : lr[x]) {
    rl[r].erase(find(all(rl[r]), x));
  }
  for (int l : rl[x]) {
    assert(sum_pos(l) == 0);
    log("l=%d sz(lr[l])=%d count=%d\n", l, sz(lr[l]), (int)st[sz(lr[l])].count(l));
    assert(st[sz(lr[l])].count(l) == 1);
    st[sz(lr[l])].erase(l);
    lr[l].erase(find(all(lr[l]), x));
    assert(st[sz(lr[l])].count(l) == 0);
    st[sz(lr[l])].insert(l);
  }

  // must delete which covers it first
  for (int y : trans01[x]) {
    delnum(y);
  }

  if (sum_pos(x) == 0) {
    assert(st[sz(lr[x])].count(x) == 1);
    st[sz(lr[x])].erase(x);

    ans.emplace_back(p[x][0].s, p[x][1].s);
    emp.emplace_back(p[x][0].s);
    return;
  }

  // ans then delete itself
  if (sum_pos(x) == 1) {
    ans.emplace_back(p[x][1].s, p[x][0].s);
  } else {
    assert(!emp.empty());
    int t = emp.back();
    emp.pop_back();
    ans.emplace_back(p[x][0].s, t);
    ans.emplace_back(p[x][1].s, t);
  }
}

bool solve() {
  for (int i = 1; i <= m; i++) {
    cin >> k[i];
    for (int j = 0; j < k[i]; j++) {
      cin >> a[i][j];
      p[a[i][j]][l[a[i][j]]] = {i, j};
      l[a[i][j]]++;
    }

    if (k[i] == 0) {
      emp.push_back(i);
    }
  }

  for (int i = 1; i <= n; i++)
    if (sum_pos(i) == 1) {
      if (p[i][0].p == 1) {
        swap(p[i][0], p[i][1]);
      }

      if (p[i][0].s == p[i][1].s) {
        mark[i] = true;
        continue;
      }

      int y = a[p[i][1].s][0];
      trans10[i] = y;
      trans01[y].push_back(i);
      log("trans %d <-> %d\n", y, i);
    }

  for (int i = 1; i <= n; i++) {
    log("i=%d sum_pos=%d [p=%d s=%d] [p=%d s=%d]\n", i, sum_pos(i), p[i][0].p, p[i][0].s, p[i][1].p, p[i][1].s);
  }

  for (int i = 1; i <= n; i++)
    if (sum_pos(i) == 2) {
      int x = a[p[i][0].s][0];
      int y = a[p[i][1].s][0];
      while (trans10[x]) x = trans10[x];
      while (trans10[y]) y = trans10[y];
      log("i=%d -> x=%d y=%d\n", i, x, y);
      assert(sum_pos(x) == 0);
      assert(sum_pos(y) == 0);
      rl[i].emplace_back(x);
      lr[x].emplace_back(i);
      if (x != y) {
        rl[i].emplace_back(y);
        lr[y].emplace_back(i);
      }
    }
  for (int i = 1; i <= n; i++)
    if (sum_pos(i) == 0) {
      log("! insert into set i=%d sz=%d\n", i, sz(lr[i]));
      st[sz(lr[i])].insert(i);
      log("! insert into set i=%d sz=%d count=%d\n", i, sz(lr[i]), (int)st[sz(lr[i])].count(i));
    }

  while (sz(st[0]) || sz(st[1]) || sz(st[2])) {
    log("! remaining %d %d %d\n", sz(st[0]), sz(st[1]), sz(st[2]));

    if (sz(st[0])) {
      int u = *st[0].begin();
      delnum(u);

    } else if (sz(st[1])) {
      if (emp.size() < 1) {
        return true; // fail
      }

      int u = *st[1].begin();
      assert(lr[u].size() == 1);
      int v = lr[u].back();
      delnum(v);

    } else if (sz(st[2])) {
      if (emp.size() < 2) {
        return true; // fail
      }

      auto u = *st[2].begin();
      assert(lr[u].size() == 2);
      int v = lr[u].back();
      delnum(v);
    }
  }

  log("!!!!\n");

  // 还有处理sum_pos=1的点构成一个环的情况
  for (int i = 1; i <= n; i++)
    if (!mark[i]) {
      assert(sum_pos(i) == 1);
      vector<int> cir = {i};
      for (int j = trans10[i]; j != i; j = trans10[j]) {
        assert(j != 0);
        log("%d -> %d\n", cir.back(), j);
        cir.emplace_back(j);
      }
      if (emp.size() < 1) {
        return true; // fail
      }
      int t = emp.back();
      emp.pop_back();
      ans.emplace_back(p[i][1].s, t);
      for (int k = 1; k < sz(cir); k++) {
        assert(p[cir[k - 1]][1].s == p[cir[k]][0].s);
        ans.emplace_back(p[cir[k]][1].s, p[cir[k - 1]][1].s);
      }
      ans.emplace_back(t, p[i][0].s);
      emp.push_back(t); // 相当于emp数组又变回去了
      for (int x : cir) mark[x] = true;
    }

  return false; // not fail
}

void simulate() {
  for (int i = 1; i <= m; i++) {
    for (int j = 0; j < k[i]; j++) {
      sim[i].emplace_back(a[i][j]);
    }
  }

  for (const auto &[u, v] : ans) {
    assert(sz(sim[u]) > 0);
    assert(sz(sim[v]) < 2);
    sim[v].push_back(sim[u].back());
    sim[u].pop_back();
  }

  for (int i = 1; i <= m; i++) {
    assert(sim[i].empty() || (sz(sim[i]) == 2 && sim[i].front() == sim[i].back()));
  }
}

int main() {
#ifdef memset0
  freopen("D.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  while (cin >> n >> m) {
    log("\n\n====== n=%d m=%d ======\n", n, m);
    emp.clear();
    fill(l + 1, l + max(n, m) + 1, 0);
    fill(mark + 1, mark + max(n, m) + 1, false);
    fill(trans10 + 1, trans10 + max(n, m) + 1, 0);
    for (int i = 1; i <= max(n, m); i++) {
      a[i][0] = a[i][1] = 0;
    }
    for (int i = 0; i < 3; i++) st[i].clear();

    bool failed = solve();
    auto &os = cout;
    // auto &os = cerr;
    if (failed) {
      os << -1 << endl;
    } else {
      os << sz(ans) << endl;
      for (const auto &[x, y] : ans) {
        os << x << " " << y << endl;
      }

      simulate();
    }

    ans.clear();
    for (int i = 1; i <= max(n, m); i++) {
      lr[i].clear();
      rl[i].clear();
      sim[i].clear();
      trans01[i].clear();
    }
  }
  // cout << "ok" << endl;
}

TABLE OF CONTENTS

题解

代码

题解

代码

评论