2024华为OD试题及答案-A072-二进制差异数

题目描述

对于任意两个正整数A和B，定义它们之间的差异值和相似值：
差异值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值不相同则为1，否则为0；
相似值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值都为1则为1，否则为0；
现在有n个正整数A0到A（n-1），问有多少(i, j) (0<=i<j<n），Ai和Aj的差异值大于相似值。
假设A=5，B=3；则A的二进制表示101；B的二进制表示011；
则A与B的差异值二进制为110；相似值二进制为001；
A与B的差异值十进制等于6，相似值十进制等于1，满足条件。

输入描述

一个n接下来n个正整数

数据范围：1<=n<=10^5，1<=A[i]<2^30

输出描述

满足差异值大于相似值的对数

用例

解题思路分析

题目要求我们找出一个数组中所有满足差异值大于相似值的数对数量。具体来说，给定两个数 AAA 和 BBB，首先将它们转换为二进制，然后计算它们的差异值和相似值：

• 差异值：通过对两个数进行按位异或（XOR）运算得到。
• 相似值：通过对两个数进行按位与（AND）运算得到。

如果一个数对的差异值大于相似值，那么我们就认为这个数对满足题目条件。最终，我们需要统计所有满足条件的数对数量。

分析步骤

C++ 代码实现

#include <iostream>
#include <vector>

using namespace std;

int countPairs(vector<int>& nums) {
    int count = 0;
    int n = nums.size();

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int diffValue = nums[i] ^ nums[j]; // XOR to get the difference value
            int simValue = nums[i] & nums[j];  // AND to get the similarity value

            if (diffValue > simValue) {
                ++count;
            }
        }
    }

    return count;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    int result = countPairs(nums);
    cout << result << endl;

    return 0;
}

Python 代码实现

def count_pairs(nums):
    count = 0
    n = len(nums)

    for i in range(n):
        for j in range(i + 1, n):
            diff_value = nums[i] ^ nums[j]  # XOR to get the difference value
            sim_value = nums[i] & nums[j]   # AND to get the similarity value

            if diff_value > sim_value:
                count += 1

    return count

def main():
    n = int(input())
    nums = list(map(int, input().split()))

    result = count_pairs(nums)
    print(result)

if __name__ == "__main__":
    main()

解题说明

1. XOR 和 AND 运算：使用 XOR 运算计算差异值，使用 AND 运算计算相似值。这样可以快速判断每一对数是否满足条件。

2. 双重循环：遍历数组中的每一对数，对它们进行 XOR 和 AND 运算，然后判断是否满足差异值大于相似值的条件。如果满足条件，计数器加一。

3. 时间复杂度：当前方法时间复杂度为 O(n2)O(n^2)O(n2)，可以用于处理中等规模的输入数据。如果输入规模更大，可以考虑优化，例如通过预处理或使用其他数据结构来减少计算量。

这个代码逻辑简单且易于理解，适合快速解决这一类问题。如果需要处理更大规模的数据，可以进一步优化。