UVa 1152 - 4 Values whose Sum is 0(hash_map/hash/二分查找)
题目链接
1.题目大意:给出四个数组,求出满足a+b+c+d=0的四元组{a,b,c,d}的个数
2.首先四重暴力肯定不用想就超时,对于原问题,我们可以看做是对于每个已知的a+b求有多少个-c-d和它相等。很明显能想到用map来存,但是刘老师特地说明STL的map会超时,因为红黑树实现的map自动排序影响效率。因此,我们需要hash_map,在C++11以后直接使用头文件unordered_map即可。当然,如果自己实现hash函数的话会很快的,但是我是个菜鸟不会写,下面是看的别人的一个博客。至于二分的解法,先求出所有的a+b保存在数组中,接着对该数组排序,那么对于每一个-c-d二分查找上下界即可
3.我觉得应该离散化数组,因为某个数组里重复的元素对四元组的计数来说是不必要的,但是好像题目要求的就是可重复的,好奇怪…
明天就步入四月份了,得快点淦了💪
hash_map(6570ms)
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int maxn=5005;
unordered_map<ll,int> mp;
ll a[maxn],b[maxn],c[maxn],d[maxn];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld%lld%lld%lld",&a[i],&b[i],&c[i],&d[i]);
}
mp.clear();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
mp[a[i]+b[j]]++;
}
ll ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ans+=mp[-c[i]-d[j]];
printf("%lld\n",ans);
if(t) printf("\n");
}
return 0;
}
hash(760ms)
#include<cstdio>
#include<cstring>
const int N=4005;
int a[4][N];
struct Hash_map
{
static const int mask=0x7fffff;
int p[mask+1],q[mask+1];
void clear()
{
memset(q,0,sizeof(q));
}
int& operator [](int k)
{
int i;
for(i=k&mask;q[i]&&p[i]!=k;i=(i+1)&mask);
p[i]=k;
return q[i];
}
};
Hash_map Hash;
int main()
{
int T;scanf("%d",&T);
for(int t=0;t<T;t++){
int n;
scanf("%d",&n);
for(int j=0;j<n;j++)
for(int i=0;i<4;i++)scanf("%d",&a[i][j]);
Hash.clear();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
Hash[a[0][i]+a[1][j]]++;
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ans+=Hash[-a[2][i]-a[3][j]];
if(t)printf("\n");
printf("%d\n",ans);
}
return 0;
}
二分(3050ms)
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=16000000+10;
const int maxn=5005;
int a[maxn],b[maxn],c[maxn],d[maxn];
int sum1[N],sum2[N];
int lowerbound(int l,int r,int v){
while(l<r){
int mid=l+((r-l)>>1);
if(sum1[mid]>=v) r=mid;
else l=mid+1;
}
return l;
}
int upperbound(int l,int r,int v){
while(l<r){
int mid=l+((r-l)>>1);
if(sum1[mid]>v) r=mid;
else l=mid+1;
}
return l;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld%lld%lld%lld",&a[i],&b[i],&c[i],&d[i]);
}
int m1=0,m2=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
sum1[m1++]=a[i]+b[j];
sum2[m2++]=-c[i]-d[j];
}
sort(sum1,sum1+m1);
ll ans=0;
for(int i=0;i<m2;i++){
ans+=upperbound(0,m1,sum2[i])-lowerbound(0,m1,sum2[i]);
}
printf("%lld\n",ans);
if(t) printf("\n");
}
return 0;
}