A92172 详细题解

首先，我们观察样例，前两个对参考意义不大，直接看第三个：

1 2 3 4 5

我们先转成二进制观察：

001 010 011 100 101

然后对齐：

001
010
011
100
101

发现每一位上都有 1（也就是说，最大可以转成的数字是 111），每一位上也都有 0（最小可以转成的数字是 000），111 - 000 = 111 = 7，答案为 7。

再看第四个样例，转换：

0010100
1010101
1100100
0101001
1001100
0110001
0100100

发现每一位上都有 0（也就是说，最小可以转成的数字是 0000000），但第六位上没有 1，所以，最大可以转成的数字是 1111101，两数之差为 125。

思路已经十分明显，Python 示例代码如下：

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    mxl = len(bin(max(a))[2:]) # Python 二进制转换结果为 0bxxxxx，所以要去除前缀
    for j in range(n):
        tmp = bin(a[j])[2:]
        a[j] = '0' * (mxl - len(tmp)) + tmp
    h0 = [False] * mxl # 包含 0 的位的记录数组
    h1 = [False] * mxl # 包含 1 的位的记录数组
    mx = 0
    min = 2 ** mxl - 1
    for j in range(n):
        for k in range(mxl-1,-1,-1):
            if a[j][k] == '0':
                h0[k] = True
            else:
                h1[k] = True
    #print("@",h1,h0,mxl)
    for k in range(mxl):
        if h1[k]:
            mx += (2 ** (mxl - k - 1))
            #print(f"@{k,mx,h1[k]}")
        if h0[k]:
            min -= (2 ** (mxl - k - 1))
            #print(f"#{k,min,h0[k]}")
    # 上方循环能保证找出的 mx 和 min 一定是最大值和最小值
    print(mx - min)

# 上方部分“#”是我的调试代码，所以结果不对的话调试也是十分重要的

其实我认为，这题应该升橙（）