题解 | #小O的数位翻转#

题目链接

小O的数位翻转

题目描述

给定一个长度为 $n$ 的数组 $a$ ，我们可以对其中任意一个数字 $a_i$ 进行一次“二进制翻转”操作。

二进制翻转的定义是：将数字的二进制表示进行翻转，之后去除前导零。例如，十进制数 $11$ 的二进制是 $1011$ ，翻转后得到 $1101$ ，即十进制的 $13$ 。

我们需要计算，有多少种选择数字的方式，使得操作后的新数字严格大于操作前的原数字。

解题思路

问题的核心在于对数组中的每一个数字 $a_i$ ，计算其二进制翻转后的结果，并与原数进行比较。

1. 二进制翻转的实现

我们可以通过位运算来高效地实现二进制翻转。对于一个给定的正整数 $x$ ，我们可以构建其翻转后的结果 reversed_x。

算法步骤如下：

初始化 reversed_x = 0。
当 $x > 0$ 时，循环执行以下操作： a. 将 reversed_x 左移一位（reversed_x <<= 1），为新的最低位腾出空间。 b. 取 $x$ 的最低位（x & 1），并将其加到 reversed_x 的最低位上（reversed_x |= (x & 1)）。 c. 将 $x$ 右移一位（x >>= 1），去掉已经处理过的最低位。
循环结束后，reversed_x 就是 $x$ 二进制翻转后的结果。

这个过程巧妙地处理了前导零的问题。例如，对于 $x=12=(1100)_2$ ，翻转后应该是 $(0011)_2=(11)_2=3$ 。我们的算法会这样计算：

初始：reversed_x = 0
处理 $1100$ 的最低位 $0$ ：reversed_x 变为 $0$
处理 $110$ 的最低位 $0$ ：reversed_x 变为 $0$
处理 $11$ 的最低位 $1$ ：reversed_x 变为 $1$
处理 $1$ 的最低位 $1$ ：reversed_x 变为 $11_2=3$ 结果正确。

2. 统计方案数

我们只需要遍历整个数组 $a$ 。对于数组中的每个元素 $a_i$ ，我们都调用上述的二进制翻转函数得到其翻转后的值。如果翻转后的值大于 $a_i$ ，我们就将计数器加一。遍历结束后，计数器的值即为最终答案。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;
using ull = unsigned long long;

// 函数用于计算一个数的二进制翻转结果
ull reverse_binary(ull n) {
    ull reversed_n = 0;
    while (n > 0) {
        reversed_n <<= 1;
        reversed_n |= (n & 1);
        n >>= 1;
    }
    return reversed_n;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int count = 0;
    for (int i = 0; i < n; ++i) {
        ull a;
        cin >> a;
        if (reverse_binary(a) > a) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    // 函数用于计算一个数的二进制翻转结果
    public static long reverseBinary(long n) {
        long reversedN = 0;
        while (n > 0) {
            reversedN <<= 1;
            reversedN |= (n & 1);
            n >>= 1;
        }
        return reversedN;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        for (int i = 0; i < n; i++) {
            long a = sc.nextLong();
            if (reverseBinary(a) > a) {
                count++;
            }
        }
        System.out.println(count);
    }
}

# 函数用于计算一个数的二进制翻转结果
def reverse_binary(n):
    reversed_n = 0
    while n > 0:
        reversed_n <<= 1
        reversed_n |= (n & 1)
        n >>= 1
    return reversed_n

def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    count = 0
    for x in a:
        if reverse_binary(x) > x:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

算法及复杂度

算法：模拟 / 位运算
时间复杂度：对于数组中的 $n$ 个元素，我们需要逐个进行处理。对于每个数字 $a_i$ ，二进制翻转操作需要的时间与其二进制表示的位数成正比，即 $\mathcal{O}(\log a_i)$ 。因此，总时间复杂度为 $\mathcal{O}(n \cdot \log(\max(a_i)))$ 。
空间复杂度：我们只需要常数级别的额外空间来存储计数器和中间变量，如果考虑输入数组的存储，则空间复杂度为 $\mathcal{O}(n)$ 。