b512: 高維度稀疏向量

2019-08-15

內容

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

輸入

輸入兩行，分別對應到兩個整數向量。向量維度最高不超過 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

解題思路

輸入 HashTable 時由於 dim 不超過 2³¹所以直接把輸入的 dim 當作當 key。

因為輸入的 value 不為負值且兩項量的任意 dim 最多都只會出現一次，而只有在都出現時該 dim 才會是需要計算成內積的，所以用負負得正的觀念，第一次存入 value 時存-value，第二次又出現(兩個向量都有)時再 *-value，就會變成正值，最後在輸出時沒出現過的會是 0，只出現過一次的會是負值，出現過兩次的才是正值。就可以過濾出兩項量都出現的情況，最後將過濾出的值相加即可。

完整程式碼

AC (6ms, 608KB)

#include <stdio.h>
#include <stdlib.h>

typedef struct Hash
{
    unsigned int Key;
    int Value;
    struct Hash* Next;
}Hash;

Hash HashTable[1024];

inline void AddHash(int key, int value)
{
    Hash* now = &HashTable[key & 1023];
    while (now->Key != key)
    {
        if (now->Next == NULL)
        {
            now = now->Next = malloc(sizeof(Hash));
            now->Key = key;
            now->Next = NULL;
            now->Value = -value;
            return;
        }
        now = now->Next;
    }
    now->Value *= -value;
}

int getInner()
{
    int res = 0;
    Hash* now, * tmp;
    for (int i = 0; i < 1024; i++)
    {
        if (HashTable[i].Next != NULL)
        {
            now = HashTable[i].Next;
            do
            {
                if (now->Value > 0)
                    res += now->Value;
                tmp = now;
                now = now->Next;
                free(tmp);
            } while (now != NULL);
            HashTable[i].Next = NULL;
        }
    }
    return res;
}

int main()
{
    int n, m, v = 1;
    while (scanf(" %d:%d", &n, &m) == 2)
    {
        if (n + m)
            AddHash(n, m);
        else if (v)
            v = 0;
        else
            printf("%d\n", getInner()), v = 1;
    }
    return 0;
}