稀疏向量svector（认证：CSP 20年6月）

稀疏向量svector

• 原题链接
• 解题思路&注意点
• 源代码
• 评测记录

原题链接

CSP认证2020年6月 第二题

解题思路&注意点

通过使用稀疏矩阵映射器（map）来处理数据。对于每个输入样本v中的每一个特征（即索引idx及其对应的权重value），首先检查该样本是否包含该特定特征。如果包含，则计算该特征对应的权重并将其累加到结果中。

本来的源代码是：

    // 对于每一对输入的向量v的（idx, value）
    if(u.find(idx) != u.end()){
    	result += u[idx]*value;
    }

运行至此已超出了预期时间限制。因为对map进行了find()方法的调用, 该操作所耗时间较长, 实际上无需如此

    result += u[idx]*value;

由于若某个值在map中不存在对应的键，则将该键的值设为0的原因是因此无需调用find函数

还有一个需要注意的问题是结果需要设置为long long型。

源代码

    #include<iostream>
    #include<map>
    usin