联想算法笔试——0930

题一：

在一个古代遗迹探险场景中，探险者发现一组神秘木棒，传说只有用所有木棒恰好拼成一个正方形（即“时间之框”），才能打开通往未来的大门。现需判断给定的若干根木棒是否满足以下条件：

1. 所有木棒必须全部使用，不可丢弃、折断或重叠；

2. 拼成的图形为正方形，四条边的长度完全相等。

请你编写程序，对多组木棒数据进行判断，每组数据给出木棒的数量及各根木棒的长度，输出该组木棒能否拼成正方形的结果。

输入描述

输入第一行包含一个正整数 T ，表示测试数据的组数。

接下来 T 行，每行第一个整数为 n （代表木棒的数量， n \geq 4 ），随后紧跟 n 个正整数 a_i （分别表示 n 根木棒的长度）。

输出描述

针对每组测试数据，输出一行结果。若能拼成正方形，输出“yes”；否则输出“no”。

题一题解：（91%）

import sys

def can_make_square(sticks):
    n = len(sticks)
    if n < 4:  # 木棒数量不足4根，无法组成正方形的4条边
        return False
    total = sum(sticks)
    if total % 4 != 0:  # 总长度不能被4整除，无法分成4条等长边
        return False
    side = total // 4
    sticks.sort(reverse=True)  # 降序排序，优先处理长木棒，减少搜索次数
    if sticks[0] > side:  # 最长的木棒超过目标边长，无法放置
        return False
    
    sides = [0, 0, 0, 0]  # 存储4条边的当前长度
    
    def dfs(i):
        if i == n:  # 所有木棒都已放置完毕
            return True
        x = sticks[i]
        tried = set()  # 记录当前层已尝试的边长，避免重复搜索
        for j in range(4):
            if sides[j] in tried:
                continue
            if sides[j] + x <= side:
                tried.add(sides[j])
                sides[j] += x
                if dfs(i + 1):
                    return True
                sides[j] -= x  # 回溯
            # 若当前边长度为0，放入失败则其他空边也会失败，直接剪枝
            if sides[j] == 0:
                break
        return False
    
    return dfs(0)

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    t = data[0]
    idx = 1
    out = []
    for _ in range(t):
        n = data[idx]
        idx += 1
        sticks = data[idx:idx + n]
        idx += n
        out.append("yes" if can_make_square(sticks) else "no")
    sys.stdout.write("\n".join(out) + "\n")

if __name__ == "__main__":
    solve()

题二：

题目描述

某角色扮演游戏中，玩家可以通过合成两种不同类型的魔法石来获得特殊技能。

现有两种魔法石集合：攻击型魔法石集合和防御型魔法石集合。每个魔法石具有能量值（能量值可能为负），每种集合内的魔法石能量值不相同。

当从攻击型和防御型中各选取一块魔法石，且其能量值之和等于特定阈值K时，才能成功合成特殊技能。请问共有多少种不同的合成方案？

注意：从攻击魔法石中选A、从防御魔法石中选B 与 从攻击魔法石中选B、从防御魔法石中选A视为不同方案。若不存在任何有效方案，输出0。

输入描述

第一行包含三个整数 M、N 和 K（M、N 均不超过 10000），分别表示攻击型魔法石集合的大小、防御型魔法石集合的大小和能量阈值K。

第二行包含 M 个不同的整数，表示攻击中各魔法石的能量值ai。

第三行包含 N 个不同的整数，表示防御中各魔法石的能量值di。

|ai|,|di|≤10000

输出描述

输出不同选取方案的数量；如果一种选取方案都不存在，则输出0。

样例输入

5 4 2

-3 2 -1 4 0

5 3 -2 6

样例输出

3

题二题解（100%）

# 读取输入
M, N, K = map(int, input().split())
attack = list(map(int, input().split()))
defense = list(map(int, input().split()))

# 构建防御型魔法石能量值的哈希表，统计每个能量值出现的次数
defense_dict = {}
for d in defense:
    defense_dict[d] = defense_dict.get(d, 0) + 1

count = 0
# 遍历攻击型魔法石，查找对应的防御型魔法石能量值
for a in attack:
    target = K - a
    if target in defense_dict:
        count += defense_dict[target]

print(count)