思路如下：
由于「相似度 = 共有元素 / 所有元素」
我的思路是「共有元素 = 兩集合所有元素 - 兩集合不重複元素」，比如集合一 {87, 99 , 101}，集合二去重後 {5, 87, 101} 共 6 個元素，而兩集合不重複元素 {5, 87, 99, 101} 共 4 個元素，那麼這兩個集合共有元素就是 2 個
順着這個思路非常暴力地寫出了第一個算法：
/* 僞碼 */
1. 輸入：由于一開始不知道要計算哪兩個集合，是以先将所有輸入資料另行儲存
2. 處理：
1) 根據集合對，選出相應兩集合，周遊集合1，枚舉每個元素并加入 set1 和 set_total；再周遊集合2，枚舉每個元素加入 set2 和 set_total
2) 計算共有元素 = (set1.size() + set2.size()) - set_total.size();
3) 計算相似度 = 共有元素 / set_total.size() 
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
static const int maxn = 50;
static const int maxm = 2000;
vector<vector<int> > set_dat(maxn);//set data
vector<vector<int> > set_pai(maxm);//set pair
int main() {
set<int> set_tot;//set total
set<int> set_1, set_2;
int n, k, m;
//1. INPUT
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &k);
for (int j = 0; j < k; ++j) {
int inp;
scanf("%d", &inp);
set_dat[i].push_back(inp);
}
}
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 2; ++j) {
int inp;
scanf("%d", &inp);
set_pai[i].push_back(inp);
}
}
//2. EXECUTE
for (int i = 0; i < m; ++i) {
int set_idx_1, set_idx_2;
set_idx_1 = set_pai[i][0] - 1;
set_idx_2 = set_pai[i][1] - 1;
set_1.clear(); set_2.clear(); set_tot.clear();
for (int j = 0; j < set_dat[set_idx_1].size(); ++j) {//traversal first set
set_1.insert(set_dat[set_idx_1][j]);
set_tot.insert(set_dat[set_idx_1][j]);
}
for (int j = 0; j < set_dat[set_idx_2].size(); ++j) {//traversal second set
set_2.insert(set_dat[set_idx_2][j]);
set_tot.insert(set_dat[set_idx_2][j]);
}
double Nc, Nt;
Nc = (set_1.size() + set_2.size()) - set_tot.size();
Nt = set_tot.size();
printf("%.1lf%%\n", Nc / Nt * 100);
}
return 0;
} 第一次暴力解完整代碼
後來最後一個測試點逾時，看了晴神解析發現能優化的地方有兩處：
1. 我一開始是先将所有輸入儲存到 vector，然後再周遊 vector 将元素加入 set，那不如直接一步到位将所有輸入儲存到 set
2. 題意所求共有元素 Nc、不重複元素 Nt，實際就是求交集并集，而這個求交集并集有一個更快的方法是：
2-1. 求并集：直接将并集元素初始為另一集合 y 元素個數，這樣隻需周遊一個集合 x 便可得到結果——集合 x 目前元素在集合 y 不存在，并集元素加一
2-2. 求交集：将交集元素初始為零，這樣也是隻需周遊一個集合 x 便可得到結果——集合 x 目前元素在集合 y 存在，交集元素加一
修改代碼後送出便 A 了
完整代碼點選此處