首页 > 试题广场 >

完美对

[编程题]完美对

热度指数：6984 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有 $\ n$ 个物品，每个物品有 $\ k$ 个属性，第 $\ i$ 件物品的第 $\ j$ 个属性用一个正整数表示记为 $a_{i,j}$ ，两个不同的物品 $\ i,j$ 被称为是完美对的当且仅当 $a_{i,1}+a_{j,1} = a_{i,2}+a_{j,2}=\dots=a_{i,k}+a_{j,k}$ ，求完美对的个数。

进阶：时间复杂度 $O(nlogn)\$ ，空间复杂度 $O(n)\$

输入描述:

第一行两个数字。

接下来行，第行个数字表示。

输出描述:

一行一个数字表示答案

示例1

输入

输出

算法知识视频讲解

Python

想去夏威夷的仰泳鲈鱼在参加牛客活动

## python的dict不能以列表为key，所以使用了幽默的手动哈希（摇随机点防止碰撞）：

def readline():
return map(int, input().split())

def hashkey(nums, p=59):
key = 0
for i, n in enumerate(nums):
key += n*(p**i)

return key

n, k = readline()
hashd = {}
for _ in range(n):
ks = list(readline())
key = hashkey([ks[i+1]-ks[i] for i in range(k-1)])
hashd[key] = hashd.get(key, 0)+1

ans = 0
for key, value in hashd.items():
if key == 0:
ans += value*(value-1)
else:
if -key in hashd:
ans += value*hashd[-key]

ans = ans//2
print(ans)

编辑于 2025-03-19 22:26:07 回复(0)

Python

zhq1999

import collections
def ans(data):
    res = 0
    hash_map = collections.defaultdict(int)
    
    for i in range(len(data)):
        diff = []
        for j in range(1,len(data[0])):
            diff.append(data[i][j] - data[i][0]) 
        str_1 = " ".join(str(id) for id in diff)
        str_2 = " ".join(str(-id) for id in diff)  
        res += hash_map[str_2]
        hash_map[str_1] += 1
        
            
    return res
if __name__ == "__main__":
    num = list(map(int,input().split()))
    m = num[0]
    data = []
    for i in range(m):
        data.append(list(map(int,input().split())))
    print(ans(data))

发表于 2022-08-03 18:23:33 回复(0)

Python

O_n2

我真傻，我居然花了这么久的时间优化求交集的过程，没想到一个哈希就解决了。。。

def count(n, k, a_list):
    cnt = 0
    delta_map = dict()
    for i in range(n):
        delta_list = []
        for m in range(k-1):
            delta_list.append(a_list[i][m+1] - a_list[i][0])
        p_str = ' '.join([str(j) for j in delta_list])
        n_str = ' '.join([str(-j) for j in delta_list])
        if delta_map.get(n_str):
            cnt += delta_map.get(n_str)
        if delta_map.get(p_str):
            delta_map[p_str] += 1
        else:
            delta_map[p_str] = 1
    return cnt

编辑于 2021-04-28 14:49:05 回复(0)