NOIP 提高 2012 第一轮 第 25 题：相邻等数合并（二进制进位计数）

题目

#include <iostream>
using namespace std;
const int SIZE = 20;
int data[SIZE];
int n, i, h, ans;
void merge()
{
    data[h-1] = data[h-1] + data[h];
    h--;
    ans++;
}
int main()
{
    cin>>n;
    h = 1;
    data[h] = 1;
    ans = 0;
    for (i = 2; i <= n; i++)
    {
        h++;
        data[h] = 1;
        while (h > 1 && data[h] == data[h-1])
            merge();
    }
    cout<<ans<<endl;
}

输入：8
输出：_

输入：2012
输出：_

答案

7; 2004

题解

考点定位

本题考「二进制合并计数」,对应大纲 4.2.1 模拟（难度【4】）。

解题过程

程序模拟「二进制计数器」：每插入一个 1，相邻相等则合并（ans++）。n=8：

（其余 i 无合并。）输出 7。

输入 2012：总合并数 = 二进制计数从 1 到 2012 的总进位次数 = n − popcount(n) = 2012 − 8 = 2004。

（2012 = 11111011100₂，含 8 个 1。）

易错提醒

① 合并次数 = 二进制进位次数 = n − popcount(n)；② 逐位模拟的正确性：二进制计数器每一位 1→0 进位的次数恰等于「该位被跨越的次数」。