H. Binary Median 解题思路 ​

核心问题分析 ​

题意其实特别清爽：长度为 $m$ 的二进制串一共有 $2^m$ 个，按字典序排列。注意到——长度固定为 $m$ 的二进制串，字典序大小完全等价于它当作整数的数值大小。比如 01011 就是数字 $11$，01100 就是 $12$，前者字典序小、数值也小，一一对应、丝毫不乱。

于是整道题瞬间脱掉二进制的外衣：我们有 $0, 1, 2, \dots, 2^m - 1$ 这一排连续整数，从里面抠掉 $n$ 个（那些被删除的串对应的数值），剩下 $k = 2^m - n$ 个数，从小到大编号 $0 \sim k-1$，要求输出第 $\lfloor \frac{k-1}{2} \rfloor$ 个，也就是中位数那一位，最后再把它转回长度 $m$ 的二进制串。

数据范围很关键：$m \le 60$，所以 $2^m$ 能塞进 long long（int long long 这个宏就是干这个的）；而 $n \le 100$，删掉的数少得可怜。这意味着我们根本不需要把 $2^m$ 个数真的列出来——那是天文数字。突破口在于：删掉的东西就那么一小撮，只要算清楚它们对"第几名"的影响就行。

1. 先把删除的串翻译成数字，排好队 ​

第一步是无脑的：把每个被删的二进制串读进来，逐位 val = val * 2 + (c - '0') 折算成整数，然后排序。

int val = 0;
for (char c : s) {
    val = val * 2 + (c - '0');
}
a[i] = val;

排完序之后，a[] 就是一排从小到大的"空洞"位置。后面所有推导，都建立在这排有序空洞之上。

2. 目标名次：剩下的牌里，中位数排第几？ ​

剩下 $k = 2^m - n$ 个数，要的是第 $\lfloor \frac{k-1}{2} \rfloor$ 个（下标从 $0$ 开始）。代码里这一行就是它：

int mid = ((1LL << m) - n - 1) / 2;

把它解读为：如果一个数都没删，那么"第 $\text{mid}$ 名"对应的数值恰好就是 $\text{mid}$ 本身（因为 $0,1,2,\dots$ 是连续的，第 $x$ 名就是数 $x$）。所以这个 mid 是我们在完整序列里的初始猜测下标。

但问题在于——我们删掉了一些数啊！这个下标会被"挤"得不准。怎么修正？看下一节，这是全题的灵魂。

3. 顿悟时刻：被删掉的"前方空洞"会把你往后顶 ​

想象你站在数轴上，目标是数到剩余序列的第 mid 个。你从 $0$ 开始往右走，每遇到一个还活着的数就计一名。可是如果你前方（也就是 $\le$ 当前位置）有一个数被删了，那它本来要占的那一格名次就没了——为了凑够 mid 这么多名，你必须再往后多走一格去补回来。

这正是这段循环干的事：

for (int i = 0; i < n; i++) {
    if (a[i] <= mid) {
        mid++;
    } else {
        break;
    }
}

我们顺着排好序的空洞 a[] 扫：只要某个空洞落在当前 mid 的位置或前方（a[i] <= mid），就说明这一格被"偷"走了，于是 mid++，把目标数值往后顶一格。一旦遇到第一个 a[i] > mid，后面的空洞都在我们右边、影响不到当前目标了，直接 break 收工。

这里有个微妙但正确的细节：因为 a[] 是升序的，所以 mid 在循环里只增不减，每次 mid++ 后下一个 a[i] 仍然只可能更大或被跳过——不会出现"补了一格又冒出一个更小空洞"的乱序情况。换句话说，扫一遍单调推进就够了，不需要反复迭代。最终的 mid 就是真正答案对应的数值。

一句话总结这个修正：最终数值 = 初始下标 + 落在它前方（含自身位置）的删除点个数。 而升序扫描让"前方"这个边界随着 mid 自然延伸，一气呵成。

整段逻辑的复杂度只有排序的 $O(n \log n)$ 加上一遍 $O(n)$ 扫描，$n \le 100$，快到飞起。

4. 把数字穿回二进制的衣服 ​

定位到数值 mid 之后，剩下的就是把它按 $m$ 位从高到低打印出来：

for (int i = m - 1; i >= 0; i--) {
    cout << (mid >> i & 1);
}

从第 $m-1$ 位（最高位）一路右移到第 $0$ 位，逐位 & 1 取出来。注意这里固定输出 $m$ 位，所以哪怕高位是 $0$ 也会乖乖补齐，长度永远正确。

拿样例验证一下：$n=3, m=3$，删掉 010,001,111，即数值 $\{1, 2, 7\}$，排序后 a = [1, 2, 7]。$k = 8 - 3 = 5$，初始 $\text{mid} = (8 - 3 - 1)/2 = 2$。扫描：$a_0 = 1 \le 2$，mid 变 $3$；$a_1 = 2 \le 3$，mid 变 $4$；$a_2 = 7 > 4$，break。最终 $\text{mid} = 4$，转成三位二进制就是 100——和样例输出完全一致，漂亮。

CPP 代码实现 ​

// H. Binary Median

#include <bits/stdc++.h>
#define lg(x) (63 - __builtin_clzll(x))
#define all(x) (x).begin(), (x).end()
#define low_bit(x) ((x) & (-x))
#define pb push_back
#define db long double
#define int long long
#define sz(x) (int)x.size()
#define endl "\n"

using namespace std;

void solve() {

    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int val = 0;
        for (char c : s) {
            val = val * 2 + (c - '0');
        }
        a[i] = val;
    }

    sort(all(a));

    int mid = ((1LL << m) - n - 1) / 2;

    for (int i = 0; i < n; i++) {
        if (a[i] <= mid) {
            mid++;
        } else {
            break;
        }
    }

    for (int i = m - 1; i >= 0; i--) {
        cout << (mid >> i & 1);
    }
    cout << endl;

}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }

}