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;
}