E.Checksum（东北四省联赛ccpc）

题意：有一个a的字符串，要构造一个b的字符串，使得b接到a后面，所有的1的个数（去掉二进制k位后的数）等于b字符串转十进制的数。

知识点：枚举构造

分析：因为k比较小，所以可以用枚举，构造每次的二进制数符不符合条件，如符合就输出，不符合就继续。先算出初始1有几个，在此基础上，b最小可以位1的个数。每次都要把b的二进制k位后的舍去，用取模就好啦。

#include<bits/stdc++.h>
using namespace std;
void sol(){
	int n,k;cin>>n>>k;
	string s;cin>>s;
	int cnt=0;
	for(auto x:s){//算出A中1的个数
		if(x=='1')cnt++;
	}
	for(int i=0;i<=k;i++){//枚举，尝试构造新的二进制串
		int b=cnt+i;
		b%=(1<<(k));//把k位后面的去掉
		int bc=0;
		for(int j=0;j<k;j++){
			if(b>>j&1)bc++;//计算b中1的个数
		}
		if(bc==i){//如果b的中1的个数等于期望增加的1的个数
			for(int j=k-1;j>=0;j--){
				if(b>>j&1){
					cout<<"1";
				}
				else cout<<"0";
			}
			cout<<endl;return;
		}
	}
	cout<<"None"<<endl;
}
int main(){
	int t;cin>>t;
	while(t--)sol();
	return 0;
}