b512: 高維度稀疏向量
標籤 : 向量 特殊輸入
通過比率 : 98% (131 人 / 134 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2015-09-07 14:17

內容

輸入兩個向量,計算向量內積值。兩個向量的內積,是各項相乘然後加總。例如 [1,2,3] 和 [4,5,6] 內積是 1*4+2*5+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 的維度都可以忽略不需描述,只需記錄非零的維度。利用上述的表示法,讀取兩個向量,然後算出它們的內積。

輸入說明

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

輸出說明

內積值
最後記得換行

範例輸入
1:5 1000:55 1000000:555 0:0 
10:6 10000:66 100000:666 1000000:2 0:0 
範例輸出
1110 
測資資訊:
記憶體限制: 32 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1M
提示 :
標籤:
向量 特殊輸入
出處:
清華 MOOCs 2014 程式設計導論期末考 [編輯:
spocktsai (囧rz)
]


編號 身分 題目 主題 人氣 發表日期
13645
mmi366127 (unknown)
b512
42 2018-04-01 00:27