ZeroJudge 解題筆記：b512. 高維度稀疏向量

作者：王一哲
日期：2025年7月24日


ZeroJudge 題目連結：b512. 高維度稀疏向量

解題想法

這題的維度不連續而且範圍很大，用字典儲存維度及對應的值比較方便，如果用陣列儲存值會有很多浪費掉、沒有儲存資料的空間。

Python 程式碼

先儲存兩個向量的資料，再計算相乘的結果。使用時間約為 43 ms，記憶體約為 6.1 MB，通過測試。

A, B = dict(), dict()
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    A[k] = v
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    B[k] = v
ans = 0
for k, v in A.items():
    ans += v * B.get(k, 0)
    if a in B: ans += n*B[a]  # 也可以這樣寫
print(ans)

只儲存第一個向量的資料，讀取第二個向量資料同時計算相乘的結果。使用時間約為 45 ms，記憶體約為 4.5 MB，通過測試。

A, B = dict(), dict()
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    A[k] = v
ans = 0
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    ans += v*A.get(k, 0)
print(ans)

C++ 程式碼

先儲存兩個向量的資料，再計算相乘的結果。使用時間約為 7 ms，記憶體約為 984 kB，通過測試。

#include <cstdio>
#include <map>
using namespace std;

int main() {
    map<int, int> A, B;
    int k, v;  // key, value
    while(scanf("%d:%d", &k, &v) != EOF && (k != 0 || v != 0)) A[k] = v;
    while(scanf("%d:%d", &k, &v) != EOF && (k != 0 || v != 0)) B[k] = v;
    int ans = 0;
    for(auto it : A) ans += it.second * B[it.first];
    printf("%d\n", ans);
    return 0;
}

使用時間約為 7 ms，記憶體約為 984 kB，通過測試。

#include <cstdio>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<int, int> A, B;
    int k, v;  // key, value
    while(scanf("%d:%d", &k, &v) != EOF && (k != 0 || v != 0)) A[k] = v;
    while(scanf("%d:%d", &k, &v) != EOF && (k != 0 || v != 0)) B[k] = v;
    int ans = 0;
    for(auto it : A) ans += it.second * B[it.first];
    printf("%d\n", ans);
    return 0;
}

只儲存第一個向量的資料，讀取第二個向量資料同時計算相乘的結果。使用時間約為 7 ms，記憶體約為 976 kB，通過測試。

#include <cstdio>
#include <map>
using namespace std;

int main() {
    map<int, int> A, B;
    int k, v, ans = 0;  // key, value
    while(scanf("%d:%d", &k, &v) != EOF && (k != 0 || v != 0)) A[k] = v;
    while(scanf("%d:%d", &k, &v) != EOF && (k != 0 || v != 0)) ans += v * A[k];
    printf("%d\n", ans);
    return 0;
}

使用時間約為 6 ms，記憶體約為 996 kB，通過測試。

#include <cstdio>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<int, int> A, B;
    int k, v, ans = 0;  // key, value
    while(scanf("%d:%d", &k, &v) != EOF && (k != 0 || v != 0)) A[k] = v;
    while(scanf("%d:%d", &k, &v) != EOF && (k != 0 || v != 0)) ans += v * A[k];
    printf("%d\n", ans);
    return 0;
}