解題區/解題區 - Zerojudge

b418. 八成真物

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

「偽物比真物更有價值」—貝木泥舟
「真物和偽物一樣有價值」—忍野咩咩
「偽娘比真娘更有價值」—精英島民

任兩個物品的相似度$sim(A, B) = \frac{|A \cap B|}{|A \cup B|}$，換句話說把 $A$ 具有的特徵和 $B$ 具有的特徵類型取交集、聯集個數，相除就能得到其相似度。例如有 5 個特徵，若 A 表示成 11001、B 表示成 01100$sim(A, B) = \frac{|{2}|}{|{1, 2, 3, 5}|} = 0.25$。

現在盤面上有 N 個物品、M 種特徵，請問相似度大於等於 0.8 的相似對數 $S$ 有多少種。為了讓這一題更有趣味，算法允許偽物，輸出$\frac{S}{N(N-1)/2} \times 100$。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
8 10
0111101101
0111101100
0111101100
0111101101
1100101010
0111101100
0111101100
0011101111
  
8 10
1111101100
1011101100
1010101100
1010111010
0100110100
1011101100
1110110000
1011111100

Sample Output

1
2
53.57
25.00

Solution

利用 std::bitset 加速交集和聯集運算，將數個屬性壓縮到一個 32-bits 單位，然後藉 bitcount 盡可能在 $O(1)$ 的時間內完成，就有機會通過這一題。一般的 $O(N^2 M)$ 比 $O(N^2 M/32)$ 慢個五六倍。

此外，特別小心浮點數計算誤差，5.0/4.0 >= 0.8 == false，用乘法判定大於閥值的操作。

關於 LSH 的部分，還在進行測試，若 signature 計算太慢，還不如直接暴力法，若能分散找到 signature 或者是預先有辦法處理好，那分桶計算就會好一點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h> 
using namespace std;
int main() {
    int n, m;
    char s[1024];
    while (scanf("%d %d", &n, &m) == 2) {
        bitset<512> attr[n];
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            attr[i] = bitset<512>(s);
        }
        
        double ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int a = (attr[i]&attr[j]).count();
                int b = (attr[i]|attr[j]).count();
                if (5 * a >= 4 * b)
                    ret++;
            }
        }
        printf("%.2lf\n", ret * 100 / (n * (n-1)/2));
    }
    return 0;
}