题解：AT_arc219_a [ARC219A] Similarity

C202301 · 2026-05-13 10:03:37 · 题解

前言

写了一个比较复杂的做法。我已急哭。

做法

看到 01 序列直接想到拆位。

首先我们先对 01 序列排序。由于是字符串，比较适合类似基数排序的方式，从第一行开始把 0 分左边 1 分右边，然后分治下去即可。复杂度 O(NM^2)。

然后我们注意到我们可以设计分治函数 solve(l,r,x) 表示考虑 [l,r]，仅考虑第 x 位以后的位（0 为最高位）是否存在字符串，然后找到 01 分界处，设为 mid，则如果 solve(l,mid,x+1)=1 那么我们就填 1，否则就填 0，如果都是 0 那么就返回 0 代表不合法。

由于最多 M 层这部分复杂度 O(NM)。幸好代码还挺好写。写到一半发现把输入所有字符串取反，找个不存在的即可。输麻。

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e4;
string d[N + 5], s[N + 5];
bool p[N + 5];
int n, m;
bool solve(int l, int r, int x) {
  if(l > r) return 0;
  int h = l - 1;
  for(int i = l; i <= r; ++i)
    if(d[i][x] == '0') h = i;
  if(x == m - 1) {
    if(h == r || h == l - 1) {
      if(h == r) p[x] = 0;
      else p[x] = 1;
      return 1;
    }
    return 0;
  }
  if(solve(l, h, x + 1)) {
    p[x] = 1;
    return 1;
  }
  if(solve(h + 1, r, x + 1)) {
    p[x] = 0;
    return 1;
  }
  return 0;
}
void qsort(int l, int r, int x) {
  if(l >= r || x == m) return;
  int h = l, t = r;
  for(int i = l; i <= r; ++i) if(d[i][x] == '0') s[h++] = d[i]; else s[t--] = d[i];
  for(int i = l; i <= r; ++i) d[i] = s[i];
  qsort(l, h - 1, x + 1);
  qsort(h, r, x + 1);
}
int main() {
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) cin >> d[i];
  qsort(1, n, 0);
  if(solve(1, n, 0) == 0) {
    cout << "No";
  } else {
    cout <<"Yes\n";
    for(int i = 0; i < m; ++i) cout << p[i];
  }
  return 0;
}