洛谷CF1360H Binary Median

题目描述

Consider all binary strings of length mm ( 1 le m le 601≤m≤60 ). A binary string is a string that consists of the characters 0 and 1 only. For example, 0110 is a binary string, and 012aba is not. Obviously, there are exactly 2^m2m such strings in total.

The string ss is lexicographically smaller than the string tt (both have the same length mm ) if in the first position ii from the left in which they differ, we have s[i] < t[i]s[i]<t[i] . This is exactly the way strings are compared in dictionaries and in most modern programming languages when comparing them in a standard way. For example, the string 01011 is lexicographically smaller than the string 01100, because the first two characters are the same, and the third character in the first string is less than that in the second.

We remove from this set nn ( 1 le n le min(2^m-1, 100)1≤n≤min(2m−1,100) ) distinct binary strings a_1, a_2, ldots, a_na1,a2,…,a**n , each of length mm . Thus, the set will have k=2^m-nk=2m−n strings. Sort all strings of the resulting set in lexicographical ascending order (as in the dictionary).

We number all the strings after sorting from 00 to k-1k−1 . Print the string whose index is lfloor frac{k-1}{2} floor⌊2k−1⌋ (such an element is called median), where lfloor x floor⌊x⌋ is the rounding of the number down to the nearest integer.

For example, if n=3n=3 , m=3m=3 and a=[a=[ 010, 111, 001 ]] , then after removing the strings a_ia**i and sorting, the result will take the form: [[ 000, 011, 100, 101, 110 ]] . Thus, the desired median is 100.

输入格式

The first line contains an integer tt ( 1 le t le 10001≤t≤1000 ) — the number of test cases. Then, tt test cases follow.

The first line of each test case contains integers nn ( 1 le n le min(2^m-1, 100)1≤n≤min(2m−1,100) ) and mm ( 1 le m le 601≤m≤60 ), where nn is the number of strings to remove, and mm is the length of binary strings. The next nn lines contain a_1, a_2, ldots, a_na1,a2,…,a**n — distinct binary strings of length mm .

The total length of all given binary strings in all test cases in one test does not exceed 10^5105 .

输出格式

Print tt answers to the test cases. For each test case, print a string of length mm — the median of the sorted sequence of remaining strings in the corresponding test case.

输入输出样例

输入 #1

输出 #1

说明/提示

The first test case is explained in the statement.

In the second test case, the result after removing strings and sorting is [ 001, 010, 101, 110 ]. Therefore, the desired median is 010.

准英文题面，没有一点翻译，所以我也懒得去调整这个markdown格式了

这个题面的简洁描述：

一共有(2^m)个长度为(m)的01字符串,求从中删去(n)个后，求剩下(2^m-n)个二进制数按照字典序排序后的中位数

注：若有偶数个数,则取中间靠左的数作为这(2^m -n)个二进制数的中位数

1<=T<=1000

1<=n<=min(((2^m)−1),100)

1<=m<=60

我所坚持的原理便是用最简单的思路写最乱的代码

所以我们看到题目之后就可以直接利用数据的小的特性强行求解

通过对中位数的每一步操作去完成代码任务

我们发现一共会有三种情况

1.删掉的数小于中位数，直接模拟中位数的移动过程*1

2.删掉的数等于中位数，直接模拟中位数的移动过程*2

3.删掉的数大于中位数，直接模拟中位数的移动过程*3

进一步直接模拟(当然可以直接去通过其他的lower_bound操作改变)

思路还是十分简单的

代码如下

#include<bits/stdc++.h>
using namespace std;
int qaq[200];
inline bool swag(long long a,long long b) {
	if(a<b)
		return true;
	return false;
}
inline long long pow1(long long a,long long k) {
	long long ans=1;
	while(k) {
		if(k&1)
			ans=ans*a;
		a=a*a;
		k>>=1;
	}
	return ans;
}
int main() {
	int t;
	cin>>t;
	while(t--) {
		long long n,m;
		cin>>n>>m;
		long long ans=(pow1(2,m-1))-1;
		string s;
		long long sum=0;
		memset(qaq,-1,sizeof(qaq));
		long long qwq=0,cnt=0;
		for(int i=1; i<=n; i++) {
			qwq = 0;
			cin>>s;
			for(int j=0; j<m; j++) {
				if(s[j]=='1')
					qwq+=pow1(2,m-j-1);
			}
			qaq[++sum]=qwq;
			sort(qaq+1,qaq+sum+1,swag);
			if(qwq==ans) {
				cnt++;
				if(cnt%2==0) {
					ans--;
					for(int j=sum; j>=1; j--)
						if(ans==qaq[j])
							ans--;
				}
				if(cnt%2==1) {
					ans++;
					for(int j=1; j<=sum; j++)
						if(ans==qaq[j])
							ans++;
				}
			} else if(qwq<ans) {
				cnt++;
				if(cnt%2==1) {
					ans++;
					for(int j=1; j<=sum; j++)
						if(ans==qaq[j])
							ans++;
				}
			} else if(qwq>ans) {
				cnt++;
				if(cnt%2==0) {
					ans--;
					for(int j=sum; j>=1; j--)
						if(ans==qaq[j])
							ans--;
				}
			}
		}
		for(int i=m-1; i>=0; i--) {
			if(ans>=pow1(2,i)) {
				ans-=pow1(2,i);
				printf("1");
			} else
				printf("0");
		}
		puts("");
	}
	return 0;
}

当然数组还是十分凌乱的，这个就靠自己的理解能力吧/cy(电脑qq专用)