稀疏向量

题目描述

计算两个稀疏向量的点积。两个向量的维度为 $n\le 10^5$，但非零元素数量远小于 $n$（各约 $10^5$ 个）。

算法思路

使用哈希表存储稀疏向量的非零元素：

1. 读取第一个向量，将非零元素的索引和值存入哈希表
2. 读取第二个向量，对于每个非零元素，查找哈希表中是否存在相同索引
3. 如果存在，计算两者的乘积累加到结果中
4. 输出点积结果

代码实现

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n, a, b;
    cin >> n >> a >> b;
    
    unordered_map<int, long long> u;
    for(int i = 0; i < a; i++){
        int idx;
        long long val;
        cin >> idx >> val;
        u[idx] = val;
    }
    
    long long result = 0;
    for(int i = 0; i < b; i++){
        int idx;
        long long val;
        cin >> idx >> val;
        if(u.find(idx) != u.end()){
            result += u[idx] * val;
        }
    }
    
    cout << result << endl;
    return 0;
}

关键点

• 使用哈希表（unordered_map）存储稀疏向量的非零元素
• 时间复杂度 O(a + b)，空间复杂度 O(a)
• 直接用坐标作为键值存储，避免遍历整个长度为n的向量
• 结果可能很大，使用 long long 类型

参考

• CCF-CSP认证