稀疏向量svector

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

原题链接

CSP认证2020年6月 第二题

解题思路&注意点

利用map 将向量u的稀疏矩阵存储在map中，对于输入的每一对向量v的（idx, value）对，判断向量u中的是否有位置为idx的值，如果有，则结果result += map_u[idx]*value;

本来的源代码是：

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

这样超时了，由于对map调用了find()函数，查找花费了时间，但其实没必要，改成：

result += u[idx]*value;

因为如果map中没有某值对应的键的话，map[key] = 0，所以不需要调用find()函数。

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

源代码

#include<iostream> #include<map> using namespace std; map<int, int> u; // 存放向量u的稀疏表示 int main(){ int n, a, b; scanf("%d%d%d", &n, &a, &b); int idx, value; for(int i=0; i<a; i++){ scanf("%d%d", &idx, &value); u.insert(make_pair(idx, value)); } long long result = 0; for(int i=0; i<b; i++){ scanf("%d%d", &idx, &value); if(u.find(idx) != u.end()){ result += u[idx]*value; } } printf("%lld\n", result); return 0; }

评测记录

没有写成long long结果是60分； 调用了map的find()函数结果是70分；