https://codeforces.ml/contest/1360/problem/H
题目应该挺好理解，先讲我自己想的，很直观：
最小值为0，假设最大值（就是二进制为m个1）为maxx，如果一个值都不去，那么答案就是mid = maxx/2，但是现在我们要去掉一些数，我们在去掉数的过程中，这个mid可能会变化，究竟mid怎么变化呢？我们在草稿纸上画一画就很容易知道（mid表示数组的中位数）
（1）如果此时数组的长度为奇数：那么去掉mid前面的数，mid不变，去掉mid本身或者mid后面的数，mid会减1
（2）如果此时数组的长度为偶数：那么去掉mid前面的数或者mid本身，mid会加1，去掉mid后面的数，mid不变
接下来看代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#define LL long long
using namespace std;
int T,n,m;
vector<LL> nums;
map<LL,bool> count;
LL er[100];
void solve(){
cin>>n>>m;
count.clear();
nums.clear();
for(int i = 1; i <= n; i++){
string cnt;
cin>>cnt;
LL p = 0,mul = 1;
for(int i = cnt.size()-1; i >= 0; i--){
p += mul*(cnt[i]-‘0‘);
mul *= 2;
} //把二进制字符串转化为十进制
nums.push_back(p);
}
LL maxx = er[m]-1,mid;
mid = maxx/2;// 最初始时的mid
int even = 1;//判断数组（0~m个1）长度为奇数还是偶数，刚开始肯定为偶数
for(int i = 0; i < nums.size(); i++){
count[nums[i]] = true;// 把这个数标记，表示已经去掉了
if(even){//如果是奇数
if(nums[i] <= mid) mid++; //如果比mid小或者等于就++，否则不变
while(count[mid]) mid++; // 如果这个位置被标记，说明这个数已经被去掉了，需要在++
}
else{//同理
if(nums[i] >= mid) mid--;
while(count[mid]) mid--;
}
even ^= 1;
}
//输出答案
vector<int> ans;
for(int i = 0; i <= m-1; i++){
ans.push_back(mid % 2);
mid /= 2;
}
for(int i = m-1; i >= 0; i--){
cout<<ans[i];
}
cout<<endl;
}
int main()
{
//freopen("in.txt","r",stdin);
er[0] = 1;
for(int i = 1; i <= 60; i++) er[i] = er[i-1]*2;
cin>>T;
for(int i = 1; i <= T; i++) solve();
return 0;
}
还有一个方法感觉比较巧妙，具体方法看这篇：https://blog.csdn.net/Joker_He/article/details/106339268
总结：在输出的时候不要出现特例输出，要把所有情况的输出放在同一个输出语句中，这次就是输出语句写错了写了个特例输出导致一直WA ??
Codeforces Round #644 (Div. 3) H. Binary Median
原文：https://www.cnblogs.com/Beic233/p/12969640.html