PAT(A) 1063 Set Similarity：STL set 求 Jaccard 相似度

題目要求

給 N 個集合（元素為整數），Q 次查詢：兩集合的 Jaccard 相似度 = |A∩B| / |A∪B| × 100%，保留一位小數。N≤50, 元素總數≤1000, Q≤2000。

STL set 高效實現

• 用 set<int> st[55] 存儲各集合，自動去重、有序。
• 查詢時遍歷較小集合，st[y].find(*it) != st[y].end() 判斷交集，計數 cnt。
• 並集大小 = st[x].size() + st[y].size() - cnt。
• 緩存查詢結果 dp[x][y] 避免重複計算（對稱性）。

代碼實現

#include <cstdio>
#include <set>
using namespace std;
set<int> st[55];
double dp[55][55];

int main() {
    int n, m, k;
    while(scanf("%d", &n)==1) {
        for(int i=1;i<=n;++i) {
            st[i].clear();
            scanf("%d", &m);
            for(int j=0;j<m;++j) { scanf("%d",&k); st[i].insert(k); }
        }
        // 初始化緩存
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dp[i][j]=-1;
        int q; scanf("%d", &q);
        while(q--) {
            int x,y; scanf("%d%d",&x,&y);
            if(dp[x][y] < 0) {
                int cnt=0;
                for(auto it=st[x].begin(); it!=st[x].end(); ++it)
                    if(st[y].find(*it)!=st[y].end()) ++cnt;
                dp[x][y] = dp[y][x] = cnt * 100.0 / (st[x].size() + st[y].size() - cnt);
            }
            printf("%.1f%%\n", dp[x][y]);
        }
    }
    return 0;
}

複雜度分析

構建集合 O(總元素 log 總元素)。單次查詢 O(min(|A|,|B|) log max(|A|,|B|))，緩存後重複查詢 O(1)。極易通過。