NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 26 题

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int SIZE=10000;
const int LENGTH=10;
int n,m,a[SIZE][LENGTH];
int h(int u,int v)
{
    int ans,i;
    ans=0;
    for(i=1;i<=n;i++)
       if( a[u][i]!=a[v][i])
           ans++;
    return ans;
}
int main()
{
    int sum,i,j;
    cin>>n;
    memset(a,0,sizeof(a));
    m=1;
    while(1)
    {
        i=1;
        while( (i<=n) && (a[m][i]==1) )
            i++;
        if(i>n)
           break;
        m++;
        a[m][i]=1;
        for(j=i+1;j<=n;j++)
           a[m][j]=a[m-1][j];
    }
    sum=0;
    for(i=1;i<=m;i++)
       for(j=1;j<=m;j++)
          sum+=h(i,j);
    cout<<sum<<endl;
    return 0;
}

输入：7 输出：_________

这题表面是模拟，实则藏着格雷码（Gray code）的生成规律。拿到题先别急着按位计算，要看出 while 循环里 a[m][i]=1 且后面复制前一行是典型的‘只变最后一位’构造法，这就是格雷码。输入 7 时，程序会生成 8 行 7 位格雷码，再两两比较不同位数求和，答案就是 57344。

很多学生会把 h 函数当成普通汉明距离直接套公式，或者误以为 m 会等于输入 n（实际是 n+1，因为循环从 m=1 开始，当 i>n 时退出，多了一行全 0）。还有人会忽略 memset 把数组清零这一步，导致第一行不是全 0 而后面逻辑全乱。最致命的坑是以为题目要填空，其实这是完整程序，只需读懂并模拟。

这题考什么

这道题考查二进制反演/格雷码（Gray code）的生成与汉明距离求和。命题人把格雷码的构造过程封装在一段看似复杂的循环里，再用一个 h 函数统计两行之间的不同位数，最后求所有行对的距离之和。这种“生成 + 统计”的组合在 NOIP 提高组初赛里很常见，目的是看学生能否透过代码表象抓住数学规律。

知识点与概念人话版

• 格雷码：一种特殊的二进制编码，特点是相邻两个数在二进制表示上只有一位不同。比如 0, 1, 3, 2, 6, 7, 5, 4 就是 3 位的格雷码序列。本题里，a[1] 到 a[m] 就是格雷码的前 m 行。
• 汉明距离：两个二进制串对应位置上不同位的个数。题目中的 h(u, v) 就是在算第 u 行和第 v 行的汉明距离。
• 为什么相邻格雷码只变一位？ 构造时，新行是复制上一行，然后只在某个特定位置（通常是最低位或根据上一行判断）翻转为 0/1。这样保证了新行和上一行只差一位，而新行和更前面的行差多位。