2133.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"

long a[140000],s[140000];

int main()
{
	long i,n,m,j;long result;
	long begin[200],st,k,ss;
	char c;
	while(1)
	{
	cin>>m>>n;
	if(cin.fail())break;
	
	long h;
	h=(1<<16);
	result=0;
	for(j=0;j<m;j++)
	{
		cin>>c;
		result*=2;
		result+=c-'0';
	}
			
			
	for(i=0;i<n;i++)
	{
		begin[i]=0;
		for(j=0;j<m;j++)
		{
			cin>>c;
			begin[i]*=2;
			begin[i]+=c-'0';
		}
		a[i]=begin[i];
	}
	for(i=0;i<h;i++)
	s[i]=-1;
	
	//for(i=0;i<n;i++)
	//s[begin[i]]=0;
	
	ss=0;k=0;
	for(st=n;st<h+n&&st!=k;)
	{
		k=st;
		for(i=ss;i<k;i++)
		for(j=0;j<n;j++)
		{	
			if(s[a[i]^begin[j]]<0)
			{
				s[a[i]^begin[j]]=(s[a[i]]>=0?s[a[i]]:0)+1;
				a[st++]=a[i]^begin[j];
			}
		}
		ss=k;
	}
	
	
	long best,bi,need;
	bi=-1;
	for(i=0;i<h;i++)
	if(s[i]>=0)
	{
		need=0;
		for(j=0;j<m;j++)
		if((result&(1<<j))!=(i&(1<<j)))need++;
		

		if(bi<0||(need<best||(need==best&&s[i]<s[bi])))
		{
			bi=i;
			best=need;
		}
	}
	if(bi<0)while(1)cout<<"sadfsdf";
	cout<<s[bi]<<endl;
	for(i=m-1;i>=0;i--)
	cout<<((bi>>i)&1);
	cout<<endl;
	}
	return 0;
}