小小小朋友的小小世界

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

首先，暴力$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是什么鬼啊！）