本文为 CCF 认证学习笔记，讲解题目稀疏向量。欢迎在评论区与我交流😊

【传送门】

方法一：双重循环

思路

双重循环找两个向量中下标相同的值相乘并求和。此方法会超时，只能过 30 分。

代码

#include <iostream>
#include <vector>
using namespace std;typedef long long ll;int main() {ll n, a, b;scanf("%lld %lld %lld", &n, &a, &b);vector<pair<ll, ll> > u, v;for (int i = 0; i < a; ++i) {ll index, value;scanf("%lld %lld", &index, &value);u.push_back({index, value});}for (int i = 0; i < b; ++i) {ll index, value;scanf("%lld %lld", &index, &value);v.push_back({index, value});}ll ans = 0;for (int i = 0; i < a; ++i) {for(int j = 0; j < b; ++j){if(u[i].first == v[j].first){ // 下标相同ans += u[i].second * v[j].second;break;}}}printf("%lld", ans);return 0;
}

方法二：双指针法

思路

设两个指针 i 和 j，i 指向向量 u，j 指向向量 v，固定 i 移动 j 寻找 index 相等的点，找到后移动 i。

代码

#include <iostream>
#include <vector>
using namespace std;typedef long long ll;int main() {ll n, a, b;scanf("%lld %lld %lld", &n, &a, &b);vector<pair<ll, ll> > u, v;for (ll i = 0; i < a; ++i) {ll index, value;scanf("%lld %lld", &index, &value);u.push_back({index, value});}for (int i = 0; i < b; ++i) {ll index, value;scanf("%lld %lld", &index, &value);v.push_back({index, value});}ll ans = 0;ll j = 0;for (ll i = 0; i < a; ++i) {while (u[i].first > v[j].first) { // 下标不相等时，j++++j;if(j >= b) break; // v 向量溢出}if(j < b){if(u[i].first == v[j].first)ans += u[i].second * v[j].second;}else break; // v 向量溢出结束查找}printf("%lld\n", ans);return 0;
}