t0ur1st

题目描述：

给定两个整数集合，它们的相似度定义为：N​c​​/N​t​​×100%。其中N​c​​是两个集合都有的不相等整数的个数，N​t​​是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入描述：

输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤10​4​​），是集合中元素的个数；然后跟M个[0,10​9​​]区间内的整数。
之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。

输出描述：

对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。

输入样例：

3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3

输出样例：

50.00%
33.33%

解题思路：

我一开始的思路很简单粗暴，就是把每个集合中的元素放入相应的set数组中，然后无脑for-each找出俩个集合中共有的元素个数Nc，根据Nc再算出Nt，从而可以输出结果Nc/Nt*100%。可是在我提交代码之后，有个测试用例TLE了。天真的我以为只要再加上一行ios::sync_with_stdio(false);取消cin和stdin的同步之后就能够避免超时直接AC啦。然而提交之后还是TLE，问了一下学长，他说双层for循环导致的超时，求俩个set中交集可以用到一个函数叫set_intersection()。这个函数有5个参数，分别是：set1.begin(),set1.end(),set2.begin(),set2.end(),back_inserter(vector)。back_inserter()函数是iterator适配器,它能使元素被插入到作为实参的某种容器的尾部。这样就可以直接用Nc = vector.size()来代替原来的那俩层for-each语句啦，提交代码全部AC。tql！

AC代码：TLE代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int N;
    cin >> N;     //集合个数
    set<int> s[N+1];
    for(int i = 1; i <= N; i++)
    {
        int M;
        cin >> M;
        for(int j = 0; j < M; j++)
        {
            int temp;
            cin >> temp;
            s[i].insert(temp);
        }
    }
    int K;
    cin >> K;
    for(int i = 0; i < K; i++)
    {
        int x,y;
        int Nc = 0;    //Nc是两个集合都有的不相等整数的个数
        cin >> x >> y;
        for(auto a : s[x])
        {
            for(auto b : s[y])
            {
                if(a == b)
                {
                    Nc++;
                }
            }
        }
        int Nt = s[x].size()+s[y].size()-Nc;  //Nt是两个集合一共有的不相等整数个数
        double temp = (double)Nc/Nt*100;
        printf("%.2f%%\n",temp);
    }
    return 0;
}

AC代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int N;
    cin >> N;     //集合个数
    set<int> s[N+1];
    for(int i = 1; i <= N; i++)
    {
        int M;
        cin >> M;
        for(int j = 0; j < M; j++)
        {
            int _;
            cin >> _;
            s[i].insert(_);
        }
    }
    int K;
    cin >> K;
    for(int i = 0; i < K; i++)
    {
        int x,y;
        cin >> x >> y;
        vector<int> v;
        set_intersection(s[x].begin(),s[x].end(),s[y].begin(),s[y].end(),back_inserter(v));  //set求交集
        int Nc = v.size();    //Nc是两个集合都有的不相等整数的个数
        int Nt = s[x].size()+s[y].size()-Nc;  //Nt是两个集合一共有的不相等整数个数
        double ans = (double)Nc/Nt*100;
        printf("%.2f%%\n",ans);
    }
    return 0;
}