b512 - 高維度稀疏向量
題目描述
題目要求計算兩個高維度稀疏向量的內積。向量以 "dim:value" 的形式表示，其中 dim 是維度，value 是該維度的值。輸入以 "0:0" 結束。
解題思路
這題的核心在於處理稀疏向量，避免不必要的計算。程式使用 map 資料結構來儲存非零元素的維度和值。首先，讀取第一個向量，將非零元素儲存在 map 中。然後，讀取第二個向量，對於每個非零元素，檢查它是否存在於第一個向量的 map 中。如果存在，則將兩個向量對應維度的值相乘，加到總和 sum 中。最後輸出 sum。
複雜度分析
- 時間複雜度: O(n + m)，其中 n 和 m 分別是兩個向量中非零元素的數量。
map的查找、插入操作平均時間複雜度為 O(1)。 - 空間複雜度: O(n + m)，用於儲存兩個向量的非零元素。
程式碼
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(){
long long int sum=0;
string a;
map <string,long long int> va;
while(cin >> a){
if(a=="0:0")break;
string b;
long long int i,c=0;
for(i=0;a[i]!=':';i++)
b+=a[i];
for(i++;i<a.length();i++){
c*=10;
c+=(a[i]-48);
}
va[b]=c;
}
while(cin >> a){
if(a=="0:0")break;
string b;
long long int i,c=0;
for(i=0;a[i]!=':';i++)
b+=a[i];
if(va.find(b)!=va.end()){
for(i++;i<a.length();i++){
c*=10;
c+=(a[i]-48);
}
sum+=va[b]*c;
}
}
cout << sum << "\n";
}