USACO/hamming

分析

我们只要按递增顺序搜索要求的n个数，然后跟前面的数判断距离是否大于d，在找到一组解后它肯定是最小的，输出。 数据不大，暴力搜索即可。注意：

0是必须出现的。

几个优化：

1. b给出了搜索的最大值：2^b-1(这条好像不是优化)
2. 计算两个数a,b的距离，只要计算a xor b的数的二进制形式中1的个数。

// 利用位运算加速统计1的个数，参考matrix67的代码。
Function check(a , b : integer):boolean;
 var
  x : integer;
 begin
  x:= a xor b;
  x:= (x and $55555555) + ((x shr 1) and $55555555);
  x:= (x and $33333333) + ((x shr 2) and $33333333);
  x:= (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
  x:= (x and $00FF00FF) + ((x shr 8) and $00FF00FF);
  x:= (x and $0000FFFF) + ((x shr 16) and $0000FFFF);
  if x >= d then check:= true
            else check:= false;
 
 end;

这样可以做一个预处理，把所有二进制中1的个数≥d的数算出来（用can[i]记录i是否是满足要求的数）。 或者不优化，直接从小到大（1--255）直接与已经生成的比较，若满足，则加入结果中。

参考代码

C
C++
pascal
Java

引用

[1]

[2]