题意:给定\(n\),\(m\),及\(n\)个二进制数,在由0到\(2^m-1\)这\(2^m\)个二进制数中删掉这\(n\)个数,求剩余二进制数的中位数。
LL trans(char s[]) {
int len = strlen(s);
int j=0;
LL ans=0;
while (s[j] != '\0') {
ans += (s[j] - '0') * pow(2, len - j - 1);
j++;
}
return ans;
}
vector<LL> v;
void solve(){
v.clear();
int n, m;
cin >> n >> m;
LL BS = (1LL << (m - 1));//直接找未删元素时的中位数
for (int i = -128; i < 128; i++) v.push_back(BS + i);
//再找出中位数左右两边的各128个数字
LL x;
for (int i = 0; i < n; i++) {
char s[100];
cin >> s;
x = trans(s);
//cout << x << endl;
if (x < v[0]) v.erase(v.begin());
else if (x > v.back()) v.erase(v.end() - 1);
else v.erase(find(v.begin(), v.end(), x));
}
x = v[(v.size() - 1) / 2];
//容器内剩余元素的中位数就是答案
//转换为二进制输出
for (int i = m - 1; i >= 0; i--) {
if (x & (1LL << i)) cout << "1";
else cout << "0";
//x&(1<<i)的作用是取出x在二进制下的第i位
}
cout << endl;
}