P1102 A-B数对

2019-07-13 23:22:53


这道题是一道方法非常多的题……

首先,暴力 $O(n^2)$ 肯定过不了……

于是,我们的视线转向枚举B,找有几个C+A,然后我们就想到cnt数组,看了一眼数据范围,是小于long long的……果断想写哈希,但是突然想到可以用map映射啊……(STL大法好)

于是代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll> m;//映射
ll c,n,t,ans=0,k[200005];
int main(){
    cin>>n>>c;
    for(int i=0;i<n;i++){
        cin>>k[i];
        m[k[i]]++;
    }
    for(int i=0;i<n;i++){
        ans+=m[c+k[i]];//加上c+k[i]的个数
        if(c==0) ans--;
    }
    cout<<ans;
    return 0;
}

但是呢,map是一个自带排序的STL,所以时间慢了很多,怎么解决呢?散列我在OiWiki和C++ Reference查到了这样一个神奇的STL:unordered_map(同样还有unordered_set)唯一的问题是——只支持C++11或以上……但是万能的洛谷都支持到C++17啦!

而且代码几乎没改:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<ll,ll> m;//不排序的映射!
ll c,n,t,ans=0,k[200005];
int main(){
    cin>>n>>c;
    for(int i=0;i<n;i++){
        cin>>k[i];
        m[k[i]]++;
    }
    for(int i=0;i<n;i++){
        ans+=m[c+k[i]];//加上c+k[i]的个数
        if(c==0) ans--;
    }
    cout<<ans;
    return 0;
}

时间只用了300ms左右!(辣么多打表提交0ms是什么鬼啊!)