[CF1360H] Binary Median

Description

一共有 (2^m) 个长度为 (m) 的 01 字符串，求从中删去 (n) 个后，求剩下 (2^m-n) 个二进制数按照字典序排序后的中位数。若有偶数个数，则取中间靠左的数作为这 (2^m -n) 个二进制数的中位数。(T le 1000, n le 100, m le 60)

Solution

模拟一个 Kth 的过程，显然 (k=[frac {n+1} 2])，从高到低枚举依次确定各位，假设现在枚举到了第 (p) 位，检查第 (p) 位为 (0) 时数字的个数，如果个数 (le k) 则将第 (p) 位定为 (0)，否则定为 (1) 并减去这个已经统计出的个数

时间复杂度 (O(Tnm^2))，其实也可以用位运算压到 (O(Tnm log m))

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 105;

int n,m;
string s[N];
int a[N];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(auto &j:s[i])
        {
            j-='0';
        }
    }
    memset(a,0,sizeof a);
    int k=(1ll<<m)-n;
    k=(k+1)/2;
    for(int i=0;i<m;i++)
    {
        int res=1ll<<(m-i-1);
        for(int j=1;j<=n;j++)
        {
            int flag=1;
            for(int k=0;k<=i;k++)
            {
                if(s[j][k]!=a[k])
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                res--;
            }
        }
        if(k>res)
        {
            k-=res;
            a[i]=1;
        }
    }
    for(int i=0;i<m;i++)
    {
        cout<<a[i];
    }
    cout<<endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}