题解 P1461 【海明码 Hamming Codes】

```cpp ###//位运算+压行 #include<bits/stdc++.h> using namespace std; int ans[257],cnt,n,b,d; inline bool check(int x,int y){ int z=x^y,tot=0;//计算两个数的相同位上的情况 do if(z&1) tot++;//如果末位为0 while(z>>=1);//检查下一位 return tot>=d; } inline bool exe(int tar){ for(int i=1;i<=cnt;i++)//这个算法的正确性在于算法每次枚举并检查一个二进制码时保证了之前的加入答案的二进制码已经两两互查过 if(!check(ans[i],tar)) return false;//所以每次对新数据检查时，只要将其与已经加入答案的二进制码对比 return true; } int main(){ scanf("%d%d%d",&n,&b,&d); int maxn=1<<b;//加速循环（在不开-O的情况下） for(int i=0;i<=maxn&&cnt<=n;i++)//在2^B进制数下最小这句话其实是具有迷惑性的，实际上就是10进制下最小，也就不用进制转换了 if(exe(i)) ans[++cnt]=i; for(int i=1;i<=n;i++){//DFS和顺序枚举出来的结果应该是不用排序的 printf("%d ",ans[i]); if(!(i%10)) printf("\n");//注意换行 } return 0; } ```