题解

题面描述

给定一个数组包含 $n$ 个整数：$\{a_1,a_2,\ldots,a_n\}$。对于每个整数 $a_i$，如果它可以表示为恰好 $k$ 个 $2$ 的幂次之和，则称 $a_i$ 是 $k$ 和谐的。注意，允许相同的 $2$ 的幂次重复使用。例如：

• $9$ 可以表示为 $1+2+2+4$，所以 $9$ 是 $4$ 和谐的。
• 同时 $9$ 也可以表示为 $1+8$，所以 $9$ 也是 $2$ 和谐的。

要求依次统计 $1$ 和谐、$2$ 和谐、$\ldots$、$30$ 和谐的数字个数。

思路

我们可以观察到，对于正整数 $a$，如果使用 $2$ 的幂次进行拆分，可以得到两个重要结论：

1. 最少需要的个数
   用二进制表示数 $a$ 时，二进制中 $1$ 的个数即为最少需要的 $2$ 的幂次的个数。记为 $\mathrm{popcount}(a)$。

2. 最多可以拆分到的个数
   由于可以将除了 $2^0=1$ 外的其他 $2$ 的幂拆分成两个更小的幂次（例如 $8$ 可以拆成 $4+4$），所以最多可以拆分到 $a$ 个 $1$，即最大为 $a$ 个。但本题中 $k$ 的取值范围为 $1$ 到 $30$，因此最大只需要考虑到 $\min(a, 30)$。

综上，对于 $a>0$，如果存在整数 $k$ 使得

则 $a$ 是 $k$ 和谐的。
对于 $a=0$，由于无法用正的 $2$ 的幂次凑出 $0$（空和不计数），因此不统计。

统计时，对每个数 $a$（若 $a>0$），令

• $L = \mathrm{popcount}(a)$
• $R = \min(a,30)$

然后对所有 $k$ 满足 $L \le k \le R$，将答案计数加 $1$。

代码分析

• 遍历数组：对每个数 $a$ 进行处理，如果 $a$ 为 $0$，跳过；否则计算 $L$ 和 $R$。
• 区间更新：对 $k$ 从 $L$ 到 $R$ 的所有值，将计数加 $1$。由于 $k$ 的最大值为 $30$，循环最多 $30$ 次，因此总体复杂度为 $O(n\times30)$，满足题目要求。
• 输出结果：最终输出 $k=1$ 到 $30$ 的计数结果。

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> ans(31, 0); // 用下标 1 到 30 表示 k 和谐数字的计数

    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        if(a == 0) continue; // 0无法表示
        int ones = __builtin_popcount(a); // 计算 a 的二进制中 1 的个数
        int R = min(a, 30); // 最大 k 为 min(a, 30)
        // 对 k 从 ones 到 R 更新计数
        for(int k = ones; k <= R; k++){
            ans[k]++;
        }
    }
    // 输出 1 到 30 的结果
    for(int k = 1; k <= 30; k++){
        cout << ans[k] << " ";
    }
    return 0;
}

Python

# -*- coding: utf-8 -*-
import sys

def main():
    input_data = sys.stdin.read().split()
    n = int(input_data[0])
    ans = [0] * 31  # 下标 1 到 30 的计数
    idx = 1
    for _ in range(n):
        a = int(input_data[idx])
        idx += 1
        if a == 0:
            continue  # 0 不计入
        # 计算 a 的二进制中 1 的个数
        ones = bin(a).count('1')
        # 最大 k 为 min(a, 30)
        R = min(a, 30)
        # 对 k 从 ones 到 R 更新计数
        for k in range(ones, R + 1):
            ans[k] += 1
    # 输出 1 到 30 的结果
    print(" ".join(str(ans[k]) for k in range(1, 31)))

if __name__ == "__main__":
    main()

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 输入读取
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[] ans = new int[31]; // 下标 1 到 30 的计数
        String[] parts = br.readLine().split(" ");
        
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(parts[i]);
            if(a == 0) continue; // 0 不计入
            // 计算 a 的二进制中 1 的个数
            int ones = Integer.bitCount(a);
            // 最大 k 为 min(a, 30)
            int R = Math.min(a, 30);
            // 对 k 从 ones 到 R 更新计数
            for (int k = ones; k <= R; k++) {
                ans[k]++;
            }
        }
        
        // 输出 1 到 30 的结果
        StringBuilder sb = new StringBuilder();
        for (int k = 1; k <= 30; k++) {
            sb.append(ans[k]);
            if (k != 30) {
                sb.append(" ");
            }
        }
        System.out.println(sb.toString());
    }
}

题目内容

小美有 $n$ 个整数 {$a_1,a_2,...,a_n$}，对于第 $i$ 个数字 $a_i$ ，如果其能被 $k$ 个 $2$ 的幂次数之和表示，那么定义 $a_i$ 是 $k$ 和谐的。例如：$9$ 是 $4$ 和谐的，因为 $9=1+2+2+4$ 成立，同时也是 $2$ 和谐的，因为 $9=1+8$ 成立。

现在，你需要依次输出 $1$ ~ $30$ 和谐的数字有多少个。

输入描述

第一行输入一个整数 $n(1≦n≦2×10^5)$代表数组中的元素数量。

第二行输入 $n$ 个整数

$a_1,a_2,...,a_n(0≦a_i≦10^9)$代表初始数组。

输出描述

在一行上输出 $30$ 个整数，依次代表 $1,2,...,30$ 和谐的数字个数。

样例1

输入

3
1 2 3

输出

2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0