CSP-稀疏向量Python实现100分

向量Python实现100分"/>

CSP-稀疏向量Python实现100分

思路：用俩个字典分别记录俩个向量的非零值的位置以及对应的值，将位置作为key，对应的值作为value，因为位置肯定不会重复的，然后计算的时候遍历非零值较少的那个向量（可以通过比较a和b的大小得出），这样做可以降低一点时间复杂的，因为求向量内积必须是俩个向量中相同位置的值都不为0才需要计算，其他情况都为0。
测试数据：

测试数据
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40

代码：

n,a,b = map(int,input().split())
# 将俩个向量的非0部分的位置和值分别放入字典中，以位置作为key
map_a = {}
map_b = {}
for _ in range(a):ind,val = map(int,input().split())map_a[ind] = val
for _ in range(b):ind,val = map(int,input().split())map_b[ind] = val
# 保存结果
result = 0
# 在长度的小的字典中进行遍历，可以省一点时间
if a<b:# 遍历字典的语法for key,value in map_a.items():# 看在b向量中这个位置的值为0吗，不为0才需要计算if key in map_b:result += value*map_b[key]
else:# 遍历字典的语法for key,value in map_b.items():if key in map_a:result += value*map_a[key]
print(result)