b418. 八成真物 - 高中生程式解題系統

內容

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

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

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

輸入說明

每組測資，第一行會有兩個整數 $N, M$ ，表示有 $N$ 個物品、 $M$ 種特徵。

接下來會有 $N$ 行，每一行上會有 $M$ 個 01 字符，第 $i$ 行上的第 $j$ 個字元，表示第 $i$ 個物品，是否擁有特徵 $j$ 。

$1 < N \leq 1024, 0 < M \leq 512$

輸出說明

對於每一組輸出一行，輸出一個小數點兩位，相似度高於 0.8 的對數 / 總對數的百分比。

範例輸入 #1

範例輸出 #1

53.57
25.00

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 3.0s , <10M
公開測資點#3 (20%): 5.0s , <10M
公開測資點#4 (20%): 5.0s , <10M

提示：

注意浮點數誤差，感謝 liouzhou_101 提醒。

標籤:

LSH bitset 概率

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」