华为 9 月 16 日笔试：等距三元组与最少设备覆盖

《面试题目》

1. 给定最多 2000 个互不重合的平面整点，坐标范围为负十亿到十亿，怎样统计所有满足 p 到 q、r 距离相同的有序三元组，且三个点互不相同？
2. 对于四个点 (0,0)、(1,0)、(0,1)、(1,1)，为什么有序三元组的总数是 8？
3. 给定最多 30 台设备，每台提供若干能力，业务要求最多 20 种能力，怎样求覆盖全部需求的最少设备数，无解时输出 0？
4. 三台设备分别提供 {1,2}、{2,3}、{1,3}，业务需要 {1,2,3}，为什么最少需要两台？

《参考解析》

等距计数：固定中间的中心点

选定中心 p 后，把其他点按距离的平方分组。同一组里已有 c 个点时，再加入一个点，会新增 2c 个有序三元组：新点可以放在 q，也可以放在 r。这样无需保存三元组，只维护当前中心的距离计数。

下面是独立实现的核心函数：

def count_triples(points):
    total = 0
    for i, (x, y) in enumerate(points):
        counts = {}
        for j, (u, v) in enumerate(points):
            if i == j:
                continue
            distance = (x - u) ** 2 + (y - v) ** 2
            previous = counts.get(distance, 0)
            total += 2 * previous
            counts[distance] = previous + 1
    return total

四个角点中，每个中心都有两个距离平方为 1 的点，贡献 2 组，合计 8。算法平均时间 O(m²)，额外空间 O(m)。Java 或 C++ 实现要在做乘法之前转成 64 位整数：最大平方距离为 8×10¹⁸，32 位整数装不下，最终计数也应使用 64 位整数。

设备覆盖：状态记录需求，别枚举设备组合

给需要的能力依次编号，每种能力对应一个二进制位。一台设备能提供的能力组成一个掩码，需求以外的能力不用进入状态。

设 dp[s] 表示覆盖集合 s 的最少设备数。初始只有 dp[0] = 0，其他状态不可达。处理一台设备时，从上一轮状态转移到 s | cover，费用增加 1。用新数组承接这一轮结果，便于看清每台设备只被考虑一次。

def minimum_devices(devices, required):
    bits = {item: i for i, item in enumerate(dict.fromkeys(required))}
    size = 1 << len(bits)
    infinity = len(devices) + 1
    dp = [infinity] * size
    dp[0] = 0

    for capabilities in devices:
        cover = 0
        for item in capabilities:
            if item in bits:
                cover |= 1 << bits[item]
        next_dp = dp.copy()
        for state, count in enumerate(dp):
            if count != infinity:
                merged = state | cover
                next_dp[merged] = min(next_dp[merged], count + 1)
        dp = next_dp

    return 0 if dp[-1] == infinity else dp[-1]

时间 O(d·2ᵗ)，空间 O(2ᵗ)。先选“新增覆盖最多的设备”不能保证台数最少；这里 t 较小，直接求最优解更合适。输入里的能力编号上界不是状态位数，状态只由实际需求决定。