刷题笔记合集🔗

二进制差异数

问题描述

对于任意两个正整数 和 ，定义它们之间的差异值和相似值：

差异值： 、 转换成二进制后，对于二进制的每一位，对应位置的 bit 值不相同则为 1，否则为 0；

相似值： 、 转换成二进制后，对于二进制的每一位，对应位置的 bit 值都为 1 则为 1，否则为 0；

现在有 个正整数 到 ，问有多少 ， 和 的差异值大于相似值。

假设 ，；则 的二进制表示 101； 的二进制表示 011；

则 与 的差异值二进制为 110；相似值二进制为 001；

与 的差异值十进制等于 6，相似值十进制等于 1，满足条件。

输入格式

第一行一个整数 。

第二行 个正整数。

输出格式

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

样例输入

4
4 3 5 2

样例输出

4

数据范围

题解

这道题目要求我们找出有多少对数字，使得它们的"差异值"大于"相似值"。

首先理解一下题目中定义的两个概念：

• 差异值：将两个数转成二进制，按位进行异或(XOR)运算的结果
• 相似值：将两个数转成二进制，按位进行与(AND)运算的结果

例如，对于数字5(101)和3(011)：

• 差异值：101 XOR 011 = 110 (十进制为6)
• 相似值：101 AND 011 = 001 (十进制为1) 由于6 > 1，所以这对数字满足条件。

暴力解法就是枚举所有数对，计算它们的差异值和相似值，然后比较大小。但这种方法的时间复杂度是O(n²)，当n达到10⁵时，显然会超时。

那么有没有规律可以帮我们快速判断一对数字是否满足条件呢？

关键在于观察两个数的二进制表示中，最高位1的位置。有两种情况：

1. 如果两个数的最高位1在不同位置，例如：

   • A: 1010 (最高位1在第4位)
   • B: 0110 (最高位1在第3位) 那么差异值的最高位必定是1，而相似值的最高位必定是0。所以差异值一定大于相似值。

2. 如果两个数的最高位1在相同位置，例如：

   • A: 1010 (最高位1在第4位)
   • B: 1100 (最高位1在第4位) 那么差异值的最高位必定是0，而相似值的最高位必定是1。所以相似值一定大于差异值。

由此可得出结论：当且仅当两个数的最高位1不在同一位置时，它们的差异值才会大于相似值。

有了这个结论，我们可以按照最高位1的位置将数字分组，不同组之间的数字对必然满足条件。具体做法是：

1. 统计每个最高位位置上有多少个数字
2. 计算不同组之间数字对的数量总和

这样就将时间复杂度降到了O(n)，能够有效处理大规模的输入数据。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
nums = list(map(int, input().split()))

# 找出每个数的最高位1所在位置，并统计
def get_result(nums):
    # 初始化一个长度为60的数组，用于统计每个位置上有多少个数
    # 由于1 <= A[i] < 2^30，因此最高位最多在第30位
    # 但为了安全起见，我们使用60的长度
    high_bit = [0] * 60
    
    for num in nums:
        # 将数字转成二进制字符串（不带前导0）
        bin_str = bin(num)[2:]  # 去掉"0b"前缀
        
        # 处理特殊情况：0没有最高位1
        if num == 0:
            high_bit[0] += 1
        else:
            # 二进制字符串的长度就是最高位1所在的位置
            position = len(bin_str)
            high_bit[position] += 1
    
    # 计算结果
    result = 0
    # 过滤掉没有数字的位置
    positions = [count for count in high_bit if count > 0]
    
    # 计算不同组之间数字对的数量
    for i in range(len(positions)):
        for j in range(i + 1, len(positions)):
            result += positions[