CF159B 题解

crz_2025 · 2024-01-12 21:48:21 · 题解

思路

根据题意，既然优秀的配对是要颜色和大小都相等，不妨二元化一元，考虑哈希，n\le 10^5，那么可以轻松得到哈希值：a_i+b_i\times 10^5，这样可以保证哈希值不会重复，可以用 map 记录，到时候算出笔盖的哈希值并判断是否有就可以了，即优秀的配对。

普通的配对要记录每根笔的大小，如果大小相同，就是普通的配对。

时间复杂度：O(n\log n)

CODE

#include<bits/stdc++.h>
#define M 100007
using namespace std;
int n,m,s,c;
int Size[M];
map<int,int> Color;
int ans1,ans2;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>c>>s;
        Size[s]++;
        Color[c+(s*M)]++; // 哈希 
    }
    for(int i=1;i<=m;i++){
        cin>>c>>s;
        if(Size[s]) ans1++; // 普通的配对 
        if(Color[c+(s*M)]) ans2++,Color[c+(s*M)]--; // 优秀的配对，注意，要把这只笔删掉，防止重复 
    }
    cout<<ans1<<' '<<ans2;
    return 0;
}