PAT甲级1063.

目录

A1063

题目

样例

输入:

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

输出:

50.0%
33.3%

思路和坑点

　　使用map容器筛选掉重复的数据，并且使用map映射标记，记录每一个数的归属，属于第一组数据，还是第二组数据，还是共有的。

AC代码

#include<bits/stdc++.h>
using namespace std;
void check(vector<int> &a,vector<int> &b){        //求解一组数据 
    unordered_map<int,int> mp;                    //mp容器记录所有出现过的数字 
    int cnt=0;                                    //cnt为共有数字的个数 
    for(int i=0;i<a.size();i++)                    // 如果该数为第一组所有则标记为1 
        mp[a[i]]=1;
    for(int i=0;i<b.size();i++){
        switch(mp[b[i]]){            
            case 0: mp[b[i]]=2;break;            //如果第一组数中没出现过，说明为第二组数所有，标记为2 
            case 1: mp[b[i]]=3;cnt++;break;        //如果第一组也有，第二组也有，共有标记为3，并计数 
            case 2: 
            case 3: continue;break;                //如果已经标记为特有或者共有，则跳过 
        }
    }
    printf("%.1f%%\n",cnt*100.0/mp.size());        //计算结果 
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,k;
    scanf("%d",&n);
    vector<int> v[n+1];
    for(int i=1;i<=n;i++){
        int m;
        scanf("%d",&m);
        v[i].resize(m);
        for(int j=0;j<m;j++){
            scanf("%d",&v[i][j]);
        }
    } 
    scanf("%d",&k);
    for(int i=0;i<k;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        check(v[a],v[b]);
    }
    return 0;
} 

AC代码（更优）

#include<bits/stdc++.h>
using namespace std;
#define MAXN 51                            //最多有MAXN组
unordered_map<int,int>G[MAXN];            //创建一个map容器的数组
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){        //读入n组数据，记录在map中
        int m;
        scanf("%d", &m);
        for (int j = 0; j < m; j++){
            int num;
            scanf("%d", &num);
            G[i][num] = 1;
        }
    }
    
    int k;
    scanf("%d", &k);
    for (int i = 0; i < k; i++){            //k组查询
        int a, b;                           //查询的组号
        int nc = 0,nt = 0;                  //nc为共同数字个数，nt为不同数字个数    
        scanf("%d%d", &a, &b);
        nt = G[b].size();                   //nt初始化为其中一个序列包含的数字个数，然后遍历第二个序列，继续统计
        for (auto it = G[a].begin(); it != G[a].end(); it++){
            if (G[b].find(it->first) != G[b].end())
                nc++;                       //如果是共有的，nc加一
            else
                nt++;                       //如果不是共有的，nt加一
        }
        float ans = (1.0 * nc) / (1.0 * nt) * 100;
        printf("%.1f", ans); puts("%");
    }


    return 0;
}