[usaco] 海明码
Rob Kolstad
Given N, B, and D: Find a set of N codewords (1 = N = 64), each of length B bits (1 = B = 8), such that each of the codewords is at least Hamming distance of D (1 = D = 7) away from each of the other codewords. The Hamming distance between a pair of codewords is the number of binary bits that differ in their binary notation. Consider the two codewords 0x554 and 0x234 and their differences (0x554 means the hexadecimal number with hex digits 5, 5, and 4):
0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
Bit differences: xxx xx
Since five bits were different, the Hamming distance is 5.
PROGRAM NAME: hamming
INPUT FORMAT
N, B, D on a single line
SAMPLE INPUT (file hamming.in)
16 7 3
OUTPUT FORMAT
N codewords, sorted, in decimal, ten per line. In the case of multiple solutions, your program should output the solution which, if interpreted as a base 2^B integer, would have the least value.
SAMPLE OUTPUT (file hamming.out)
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127
-----------------------------------------------------------------------------
关键之处在于：
求两个数字键的海明距离。
x=a xor b ,其中为1的位即表示a和b不同的地方。
只需要计算x中1的个数即可。
对于8位二进制数，计算1的个数的方法是：
x=(x 0x55555555)+((x 1) 0x55555555);
x=(x 0x33333333)+((x 2) 0x33333333);
x=(x 0x0F0F0F0F)+((x 4) 0x0F0F0F0F);
x=(x 0x00FF00FF)+((x 8) 0x00FF00FF);
x=(x 0x0000FFFF)+((x 16) 0x0000FFFF);
经过以上步骤之后，x就是1的个数。
我的程序：
----------------------------------- ----------------------------------------------------------------------
/*
ID: yunleis2
PROG: hamming
LANG: C++
*/
#include iostream
#include fstream
#include cmath
using namespace std;
int N, B, D;
typedef unsigned int uint;
int distance1(uint a,uint b);
int main()
{
fstream fin("hamming.in",ios::in);
fin N B D;
uint src;
uint end=(1 B)-1;
uint *result= new uint[N];
result[0]=0;
int ptr=1;
for(uint i=1;i =end;i++)
{
bool flag=true;
for(int j=0;j j++)
{
if(distance1(i,result[j]) D)
{
flag=false;
break;
}
}
if(flag)
{
result[ptr++]=i;
}
if(ptr==N)
break;
}
fstream fout("hamming.out",ios::out);
for(int i=0;i i++)
{
fout result[i];
if(((i+1)%10)==0||i==(ptr-1))
fout endl;
else fout " ";
}
}
int distance1(uint a,uint b)
{
uint x=a^b;
x=(x 0x55555555)+((x 1) 0x55555555);
x=(x 0x33333333)+((x 2) 0x33333333);
x=(x 0x0F0F0F0F)+((x 4) 0x0F0F0F0F);
x=(x 0x00FF00FF)+((x 8) 0x00FF00FF);
x=(x 0x0000FFFF)+((x 16) 0x0000FFFF);
return x;
}
LeetCode每日一题——417. 太平洋大西洋水流问题 有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
LeetCode每日一题——799. 香槟塔 我们把玻璃杯摆成金字塔的形状，其中 第一层 有 1 个玻璃杯， 第二层 有 2 个，依次类推到第 100 层，每个玻璃杯 (250ml) 将盛有香槟。
P3613 【深基15.例2】寄包柜 题目描述 超市里有 n(1\le n\le10^5)n(1≤n≤105) 个寄包柜。每个寄包柜格子数量不一，第 ii 个寄包柜有 a_i(1\le a_i\le10^5)ai(1≤ai≤105) 个格子，不过我们并不知道各个 a_iai 的值。对于每个寄包柜，格子编号从 1 开始，一直到 a_iai。现在有 q(1 \le q\le10^5)q(1≤q≤105) 次操作： 1 i j k：在第 ii 个柜子的第 jj 个格子存入物品 k(0\le k\le 10^9)k(0≤k≤109)。当 k=0k=0 时说明清空该格子。 2 i j：查询第 ii 个柜子的第 jj 个格子中的物品
[USACO 2012 Feb B]Moo - 规律 某字符串由m o 两个字符构成 而且构成的字符串为前一个字符串 + m + o * (i+2) + 前一个字符串 *(i+2)指的是数量 问字符串第n个字符是什么 在从一个字符串构成下一个字符串的时候，是有一定的规律的，所以我们可以很轻松地找到规律 然后就可以递归地找，满足规律的时候直接输出
洛谷 P1200 [USACO1.1]你的飞碟在这儿Your Ride Is He…【字符串+模拟】 P1200 [USACO1.1]你的飞碟在这儿Your Ride Is He… 众所周知，在每一个彗星后都有一只UFO。这些UFO时常来收集地球上的忠诚支持者。不幸的是，他们的飞碟每次出行都只能带上一组支持者。