Home > Old Blog Posts > USACO 2.1.5 Hamming Codes

USACO 2.1.5 Hamming Codes


位运算题。

求两个数中不相同的数字的个数用异或,再取其中的1的个数。

注意读题,每两个数之间的海明距离都要满足条件,而不仅仅是相邻的两个。

输出格式问题……

代码:

/*
ID: dementr1
PROG: hamming
LANG: C++
*/
#include<fstream>
#include<iostream>
using namespace std;
ifstream fin(“hamming.in”);
ofstream fout(“hamming.out”);
int test(int a,int b)
{
int tmp=a^b;
tmp=(tmp&0x55555555)+((tmp>>1)&0x55555555);
tmp=(tmp&0x33333333)+((tmp>>2)&0x33333333);
tmp=(tmp&0x0F0F0F0F)+((tmp>>4)&0x0F0F0F0F);
tmp=(tmp&0x00FF00FF)+((tmp>>8)&0x00FF00FF);
tmp=(tmp&0x0000FFFF)+((tmp>>16)&0x0000FFFF);
return tmp;
}
int main()
{
int N,B,D,i,num,t,a[70],tmp,j;
fin>>N>>B>>D;
for(i=0;i<(1<<B);i++)
{
num=0;
t=i;
a[num++]=t;
while(num!=N&&t<(1<<B))
{
t++;
bool flag=true;
for(j=0;j<num;j++) if(test(t,a[j])<D){ flag=false; break;}
if(flag) a[num++]=t;
}
if(num==N) break;
}
int counter=0;
for(i=0;i<num;i++)
{
fout<<a[i];
if(counter%10!=9&&counter!=num-1) fout<<” “;
counter++;
if(counter%10==0)
fout<<endl;
}
if(counter%10!=0) fout<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: