題目

https://zerojudge.tw/ShowProblem?problemid=b512

輸入兩個向量，計算向量內積值。兩個向量的內積，是各項相乘然後加總。例如 [1,2,3] 和 [4,5,6] 內積是 14+25+3*6 = 32

我們考慮高維度的稀疏向量，也就是大多數的元素都是零，只有少數不為零。資料的表示方式如下 dim1: value1 dim2: value2 dim3:value3 … 0:0 最後以 0:0 結束。例如

向量 [0,5,0,0,9,0,0,33] 是一個 8 維向量，可表示成 2:5 5:9 8:33 0:0 值為 0 的維度都可以忽略不需描述，只需記錄非零的維度。利用上述的表示法，讀取兩個向量，然後算出它們的內積。

Input

輸入兩行，分別對應到兩個整數向量。向量維度最高不超過 2 的 31 次方。記憶體用量不超過 32 MB。每一行都是以 0:0 結束

Output

內積值 最後記得換行

破題

如題所示，這種稀疏向量如果照著正常的方式來儲存，不僅浪費空間而且沒有效率，因此會採用題目所提到的格式來儲存 dim1: value1

而該格式自然而然的會讓人想到鍵值對(有點類似電話簿，名稱對應電話號碼，在這個例子中是維度對應數值)，而在 C++ 中的鍵值對就是 map 。

因此首先先宣告一個 map 物件

map<long long ,long long> m;

使用 long long 避免潛在的溢位問題

接下來，因為題目提到 **每一行都是以 0:0 結束 ，**所以要用個while迴圈持續接收資料，因此先宣告 dim 跟 val 變數，因為它在未初始化的前提下可能會等於 0 ，所以先給它強制初始化成 -1 ，避免潛在錯誤。而 prod 是用來儲存答案的變數，一樣先初始化成 0，因為從0開始。

	long long  dim=-1,val=-1,prod=0;

然後開始讀入 dim 跟 val ，對於使用 C++ 的人，建議使用 scanf 而不要使用 cin ，不然還要自己做字串處理，而藉由 scanf 的格式化輸入功能就能自動擷取出 dim1: value1 。

然後讀取成功後將他存入 m 物件

while(dim!=0 && val!=0) {
		scanf(" %lld:%lld",&dim,&val);
		m[dim]=val;
	}

當跳出這個迴圈後，代表已經讀取完第一個稀疏向量了，要開始讀取第二個了。

有以下幾種情況

• 第二個向量的第i維度是 0
• 第一個向量的第i維度是 0
• 或是同時兩者成立
• 兩者都不成立

第一個情況好處理，沒有在第二個向量獨到的維度忽略就好，順順讀就好。

第二種情況的話，可以轉換成，在剛剛 m 鍵值對物件中， 該維度是找不到對應的值得。

第三種情況轉換成最簡單的第一種情況就好。

第四種情況就把透過該維度為鍵所查詢到的值，跟剛剛獨到的 val 相乘，加上 prod 上就好

綜合以上情形，可以這樣處理

while (dim!=0 && val!=0){
		scanf(" %lld:%lld",&dim,&val);
		if(m.find(dim)!=m.end()){
			prod+=m[dim]*val;
		}
	}

其中 m.find(key) 會回傳 鍵 key 在 m 物件所在的位置，重點來了，如果沒找到(找不到對應的鍵)，會回傳 m.end() ，因此可以用這個判斷情況二的成立與否。

最後印出來就好

printf("%lld\n",prod);

完整C++程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
	map<long long ,long long> m;
	long long  dim=-1,val=-1,prod=0;
	while(dim!=0 && val!=0) {
		scanf(" %lld:%lld",&dim,&val);
		m[dim]=val;
	}
	dim=-1,val=-1;
	while (dim!=0 && val!=0){
		scanf(" %lld:%lld",&dim,&val);
		if(m.find(dim)!=m.end()){
			prod+=m[dim]*val;
		}
	}
	printf("%lld\n",prod);
}