【华为OD机试2023】统计差异值大于相似值二Python

题目描述：

题目描述： 对于任意两个正整数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

输出描述：

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

示例1

输入：

4

4 3 5 2

输出：

4

说明：

样例一解释：

满足条件的分别是(0,1) (0,3) (1,2) (2,3)，共4对

示例2

输入：

5

3 5 2 8 4

输出：

8

说明：

样例二解释： 满足条件的分别是(0,1) (0,3) (0,4) (1,2) (1,3) (2,3) (2,4) (3,4)

解题思路：

这题两个关键，关键一是如何判断两个数是否统计差异值大于相似值，关键二是读懂题目的样例解释

①判断两个数是否统计差异值大于相似值，就是把两个数都转化为二进制，然后逐位运算，但要注意转化后二进制长度问题——比如1100和11000001110，需要把1100补0，变成00000001100，然后再运算。我采用的方法就是二进制字符串全部转为列表，再倒序排列，列表长度短的补上对应数字的0，然后逐位运算，再把得到的结果倒序，转为十进制

②读懂题目的样例解释

样例一解释：

满足条件的分别是(0,1) (0,3) (1,2) (2,3)，共4对

这里的(0,1) (0,3) (1,2) (2,3)并不是指符合要求的数字，而是指符合要求的差异值、相似值，我看这个样例解释看了半天才看懂

def qiuzhi(a:int,b:int):
    a_lst=list(bin(a)[2:])[::-1]
    b_lst = list(bin(b)[2:])[::-1]
    if len(a_lst)>len(b_lst):
        b_lst.extend(['0']*(len(a_lst)-len(b_lst)))
    elif len(a_lst)<len(b_lst):
        a_lst.extend(['0']*(len(b_lst)-len(a_lst)))
    l=len(a_lst)
    chayizhi_lst=[]
    xiangsizhi_lst=[]
    for i in range(l):
        if a_lst[i]!=b_lst[i]:
            chayizhi_lst.append('1')
        else:
            chayizhi_lst.append('0')
        if a_lst[i]==b_lst[i]=='1':
            xiangsizhi_lst.append('1')
        else:
            xiangsizhi_lst.append('0')
    chayizhi=int(''.join(chayizhi_lst[::-1]),2)
    xiangsizhi=int(''.join(xiangsizhi_lst[::-1]),2)
    if chayizhi>xiangsizhi:
        return True
    else:
        return False


n=int(input())
num=list(map(int,input().split()))
count=0
for i,value in enumerate(num):
    for j in num[i+1:]:
        if qiuzhi(value,j):
            count+=1
print(count)