题目描述

一共有$2^m$个所有长度为$m$的01字符串。
现在将$n$个01字符串删除，并将剩下的$k$个01字符串按字典序排序，其中$k=2^m-n$。
将这$k$个字符串标号为$0$到$k-1$，现在让你求出中位数的值。
输入包含多组数据。

输入格式

第一行包含一个整数$T$表示测试数据的组数。
每组测试数据的第一行包含两个正整数，n和m。
后面有n行，每行包含一个字符串，表示删除的字符串。

输出格式

共T行，每行包含一个字符串，表示答案。

数据范围：

$1<=T<=1000$
$1<=n<=min((2^m-1),100)$
$1<=m<=60$

样例

Input:
5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10

Output:
100
010
0
1
11

算法

(数学，指针扫描) $O(nlogn)$

考虑把字符串转化成二进制数，并转化成十进制数。
事先把中位数的位置算出来，把这n个数按照大小排序，依次扫描。
如果该数在中位数的范围内，把中位数对应的指针加1；
否则不用管中位数的增减。
时间复杂度为$O(nlogn)$，AC是绰绰有余的。
官方题解直接维护了中位数，CF上众多大佬也维护了中位数，但是比较麻烦，自己想了40分钟想到了这个算法。
代码略带大常数，勿喷

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 65
using namespace std;

int n, m;
char str[maxn];
long long bin[110];

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n >> m;
        long long k = ((1ll << m) - n - 1) / 2;
        for (int i = 1; i <= n; i ++ )
        {
            scanf("%s", str + 1);
            long long ans = 0;
            for (int j = 1; j <= m; j ++ )
                if (str[j] == '1')
                    ans += 1ll << (m - j);

            bin[i] = ans;
        }
        sort(bin + 1, bin + n + 1);

        for (int i = 1; i <= n; i ++ )
            if (bin[i] > k) break;
            else k ++ ;
        //cout << k << endl;

        vector<int> vec;
        while (k)
        {
            vec.push_back(k % 2);
            k /= 2;
        }
        reverse(vec.begin(), vec.end());

        for (int i = 1; i <= m - vec.size(); i ++ ) cout << '0';
        for (int i = 0; i < vec.size(); i ++ ) cout << vec[i];
        puts("");
    }

    return 0;
}