广联达7月29日笔试

楼主python，具体题目不发了，可以找找其他帖子

第一题（AC）

思路：直接最小堆，每次弹出最小高度，加上增量x，再push进堆中，直到药剂用完，弹出此时最小高度即可。

from heapq import *

n, m, x = [int(_) for _ in input().split()]
heights = [int(_) for _ in input().split()]

heapify(heights)
for i in range(m):
    min_height = heappop(heights)
    heappush(heights, min_height + x)
print(heappop(heights))

第二题（AC）

思路：感觉是一个模拟题，难点在于最终的序列还要保持原有顺序。

解题要点：

1. 考虑从小到大遍历消除重复，假设当前消除的数为x，从小到大地消除才能保保证后续不会因为消除x/2而再次产生重复。

2. 要记录第一个重复数字和第二个重复数字的下标，才能保证原有的序列顺序。

数据结构：

1. 使用一个小顶堆keys保存剩余需要消除的数（经过去重的），保证每次消除的都是最小的数。

2. 使用字典stat保存值为x的下标集合，下标集合仍旧是一个小顶堆，保证每次弹出的两个下标是最小的。

步骤：

1. 初始化keys和存储下标的字典stat。

2.从stat中弹出当前最小数，消除该重复数字，并更新keys和stat。

3. 重复执行步骤2，直到所有数均被消除（keys为空）

import heapq

n = int(input())
nums = [int(_) for _ in input().split()]
# n = 5
# nums = [5,1,4,5,4]

def init(nums):
    statistic = {}
    for i, x in enumerate(nums):
        if x not in statistic:
            statistic[x] = [i]
        else:
            heapq.heappush(statistic[x], i)
    return statistic

def main(nums):
    stat = init(nums)
    keys = list(stat.keys())
    heapq.heapify(keys)
    while keys:
        k = heapq.heappop(keys)  # 每次选择序列中的最小值
        while k in stat and len(stat[k]) >= 2:  # 若该值出现次数大于等于2
            idx1 = heapq.heappop(stat[k])
            idx2 = heapq.heappop(stat[k])
            x = nums[idx1] * 2

            nums[idx1] = 0
            nums[idx2] = x

            if x in stat:
                heapq.heappush(stat[x], idx2)
            else:
                stat[x] = [idx2]
                heapq.heappush(keys, x)
    nums = [i for i in nums if i > 0]
    return nums

res = main(nums)
for i in res:
    print(i, end=' ')
print()

第三题（54%）

思路：一看就知道A不了，所以能混过去多少就混多少。

若A&B=B，则B的二进制中1对应的位置，A也肯定为1，则有A>=B，

故考虑将所有数从大到小排序，当B<A时，B必然不可能成为A的底座。

考虑初始化一个底座集合，每添加一个数x进去，就计算x与底座集合中的每一个底座h的值，则有如下两种情况：

1. x&h=x，表示x能够放在底座h上，则直接跳出。

2.x&h即不等于x也不等于h，则将x作为新底座加入底座集合中。

不存在x&h=h的情况，因为我们实现经过排序，故有x<h成立，则x&h必然不可能等于h。

遍历完所有数字，直接输出底座集合大小-1，为啥-1呢，因为大胆猜测修改某个底座的二进制能够让该底座与其他某一个底座合并（懵就完了）

n, m = [int(_) for _ in input().split()]
nums = [int(_) for _ in input().split()]
# nums = [10, 2, 4, 8, 9]
nums.sort(reverse=True)   # 越大的数越可能成为底座

heap = []
for x in nums:
    add_flag = True
    if len(heap) == 0:
        heap.append(x)

    for h in heap:
        if x & h == x:
            add_flag = False
            continue

    if add_flag:
        heap.append(x)

print(len(heap)-1)

#笔经##Python工程师#