P6965 [NEERC2016] Binary Code

· · 题解

*P6965 [NEERC2016] Binary Code

一个字符串至多含有一个问号，所以状态至多有两种，考虑 2-SAT，设 x_i 表示第 i 个字符串的问号填 0，\lnot x_i 表示第 i 个字符串的问号填 1。现在我们有 2n 个字符串和 2n 个文字，它们之间一一对应。

容易发现，若字符串 s 是 t 的前缀，则若 s 对应文字为真，则 t 对应文字为假；若 t 对应文字为真，则 s 对应文字为假。这说明若 s 则非 t，若 t 则非 s。

刻画前缀关系的结构是字典树。对于若 s 则非 t 的限制，我们需要从 s 向它的子树内所有字符串的 否定 连边。对于若 t 则非 s 的限制，我们需要从 t 向它的祖先对应的所有字符串的 否定 连边。因此，建出根向字典树和叶向字典树。在两棵字典树上，每个字符串对应的状态向它对应文字的否定连边。为防止出现 s 和 t 对应同一字符串的情况，在叶向字典树上，s 对应文字只能向它对应状态的两个儿子连边，否则 s 会向 s 的否定连边，导致必然无解。同理，在根向字典树上，s 对应文字向它对应节点的父亲（而非它本身）连边。

我们还要处理 s = t 但对应不同字符串的情况。容易发现，将相等的字符串排成一行，每个字符串会向所有除了它本身的其它字符串的 否定 连边，可以通过前缀后缀优化建图做到。

综上，点数和边数关于 n 和字典树大小 m 线性。点数不超过 4n + 2m，而 m \leq 2n，所以边数不超过 8n。

#include <bits/stdc++.h>
using namespace std;
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
bool Mbe;
constexpr int N = 3e6 + 5;
int n, node, trie, son[N][2], fa[N], ed[N], pos[N], qm[N];
vector<int> e[N], buc[N], pref[N], suff[N];
string s[N];
void insert(int id, string s) {
  int p = n * 2;
  for(char it : s) {
    if(!son[p][it - '0']) {
      e[p].push_back(trie), e[trie ^ 1].push_back(p ^ 1);
      fa[son[p][it - '0'] = trie] = p, trie += 2;
    }
    p = son[p][it - '0'];
  }
  ed[id] = p, pos[id] = buc[p].size();
  buc[p].push_back(id ^ 1);
  e[p].push_back(id ^ 1), e[p ^ 1].push_back(id ^ 1);
}
int dfn[N], dn, low[N], vis[N], col[N], cn, stc[N], top;
void tarjan(int id) {
  dfn[id] = low[id] = ++dn, stc[++top] = id, vis[id] = 1;
  for(int it : e[id]) {
    if(!dfn[it]) tarjan(it), low[id] = min(low[id], low[it]);
    else if(vis[it]) low[id] = min(low[id], dfn[it]);
  }
  if(low[id] == dfn[id]) {
    col[id] = ++cn;
    while(stc[top] != id) col[stc[top]] = cn, vis[stc[top--]] = 0;
    vis[stc[top--]] = 0;
  }
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n, trie = n * 2 + 2;
  for(int i = 0; i < n; i++) {
    cin >> s[i], qm[i] = s[i].find('?');
    if(qm[i] == -1) insert(i * 2, s[i]), insert(i * 2 + 1, s[i]);
    else s[i][qm[i]] = '0', insert(i * 2, s[i]), s[i][qm[i]] = '1', insert(i * 2 + 1, s[i]);
  }
  node = trie;
  for(int i = n * 2; i < trie; i += 2) {
    if(buc[i].empty()) continue;
    int sz = buc[i].size();
    pref[i].resize(sz), suff[i].resize(sz);
    for(int p = 0; p < sz; p++) {
      if(p) e[node].push_back(node - 1);
      e[node].push_back(buc[i][p]);
      pref[i][p] = node++;
    }
    for(int p = sz - 1; ~p; p--) {
      if(p + 1 < sz) e[node].push_back(node - 1);
      e[node].push_back(buc[i][p]);
      suff[i][p] = node++;
    }
  }
  for(int i = 0; i < n * 2; i++) {
    int p = ed[i];
    if(son[p][0]) e[i].push_back(son[p][0]);
    if(son[p][1]) e[i].push_back(son[p][1]);
    e[i].push_back(fa[p] ^ 1);
    int q = pos[i];
    if(q) e[i].push_back(pref[p][q - 1]);
    if(q + 1 < buc[p].size()) e[i].push_back(suff[p][q + 1]);
  }
  for(int i = 0; i < node; i++) if(!dfn[i]) tarjan(i);
  for(int i = 0; i < n; i++) {
    if(col[i * 2] == col[i * 2 + 1]) puts("NO"), exit(0);
    if(qm[i] != -1) s[i][qm[i]] = col[i * 2] < col[i * 2 + 1] ? '0' : '1';
  }
  cout << "YES\n";
  for(int i = 0; i < n; i++) cout << s[i] << "\n";
  cerr << TIME << " ms\n";
  return 0;
}