题解LG1102——A-B数对

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

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

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

于是代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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啦!

而且代码几乎没改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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是什么鬼啊!)