拼多多4.18笔试题解

第1题

枚举菱形z的中点

def solve(x: int, y: int):
    cnt1 = sum((x - i) // 2 for i in range(x))
    cnt2 = sum((y - i) // 2 for i in range(y))
    return cnt1 * cnt2

第2题

暴力遍历交换的两个下标

def solve(pos: List[Tuple[int, int]]):
    # pos[i]: (xi, yi)
    pos.sort()
    (x, y), n = zip(*pos), len(pos)
    width = [0] * n
    for i in range(n):
        width[i] = x[min(i + 1, n - 1)] - x[max(i - 1, 0)]
    best, besti, bestj = 0, None, None
    for i in range(n):
        for j in range(i + 1, n):
            if (inc := (y[i] - y[j]) * (width[j] - width[i])) > best:
                best, besti, bestj = inc, i, j
    if best: print(x[besti], x[bestj])
    else: print(-1)

第3题

【4.19更新】想出来了，补充一下代码！

在M项配置中，遍历所有的配置项的可能组合，代码里面用一个M位的二进制数sel表示，例如sel = 0b01010代表尝试合并第1和第3项配置，然后剩下了一些未合并的配置组合，用nxt存储，再用函数递归处理。

from math import prod
from collections import defaultdict
# 输入
M = int(input())
cnt = []
for i in range(M):
    cnt.append(int(input().split()[0]))
T = int(input())
configs = defaultdict(list)
for _ in range(T):
    line = input().split()
    configs[int(line[-1])].append(line[:-1])

# 计算合并后的配置数量
def combine(cfgs):
    ret = float("inf")
    for sel in range(1 << M):
        # 将sel位为1的配置项合并（如果可以的话）
        d, ans, nxt = defaultdict(list), 0, []
        for idx, cfg in enumerate(cfgs):
            key = tuple(cfg[i] for i in range(M) if sel >> i & 1)
            d[key].append(idx)
        for key, idxs in d.items():
            # 只需check一下该配置项的数量是否等于所有可能的配置项数量
            if prod(cnt[i] for i in range(M) if not sel >> i & 1) == len(idxs):
                ans += 1
            else:
                nxt.extend(cfgs[idx] for idx in idxs)
        ans += len(nxt) if not ans else combine(nxt)
        ret = min(ret, ans)
    return ret

print(sum(combine(cfgs) for cfgs in configs.values()))

第4题

动态规划。剩偶数个金币时，如果拿掉一半还剩偶数个的话，就只拿一个（让对方只能拿一个），特殊的情况是剩4个的时候，应该拿一半

@cache
def solve(n):
    if n == 1: return 1
    if n == 4 or n & 3 == 2: 
        return n - solve(n >> 1)
    return n - solve(n - 1)