hamming.cpp

USACO Section 2.1的全部AC的代码 OIer专用.

/*
NAME:lemon_c1
LANG:C++
PROG:hamming
*/
#include<fstream>
#include<bitset>
using namespace std;
ifstream cin("hamming.in");
ofstream cout("hamming.out");
int n,b,d;
bool can[257][257];
int x[65];
bool dfs(int layer);
int main(void)
{
	cin>>n>>b>>d;
	for(int i=0;i<1<<b;i++)
		for(int j=0;j<1<<b;j++)
		{
			bitset<65> t1=i;
			bitset<65> t2=j;
			t1^=t2;
			if(t1.count()>=d)can[i][j]=true;
		}
	for(int i=0;i<1<<b;i++)
	{
		x[0]=i;
		if(dfs(1))break;
	}
	return 0;
}
bool dfs(int layer)
{
	if(layer==n)
	{
		for(int k=0;k<=(n-1)/10;k++)
		{
			cout<<x[10*k];
			for(int i=1+10*k;i<min(n,10*(k+1));i++)
				cout<<' '<<x[i];
			cout<<endl;
		}
		return true;
	}
	for(int i=x[layer-1]+1;i<1<<b;i++)
	{
		bool flag=true;
		for(int j=0;j<layer;j++)
			if(!can[x[j]][i])
			{
				flag=false;
				break;
			}
		if(flag)
		{
			x[layer]=i;
			if(dfs(layer+1))return true;
		}
	}
	return false;
}