[数据结构与算法]UVA1152 4 Values whose Sum is 0 题解

UVA1152 4 Values whose Sum is 0

题目链接：UVA1152 4 Values whose Sum is 0

题意：给定四个数组，求 $a_i+b_j+c_k+d_l=0$ 的个数，多组数据+奇怪的输出格式

解法一

$O(n^4)$ 枚举肯定过不去

想一想，我们有必要在枚举 $i,j$ 的时候再去枚举 $k,l$ 吗？

没有，因为 $k,l$ 的组合是有限的，只有这么多

我们可以先 $O(n^2)$ 把所有 $c_k+d_l$ 枚举出来，然后排个序，就可以二分找出所有的 $?(a_i+b_j)$ 了

时间复杂度 $O(n^2\log n^2)$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(4e3+5)
template<typename T>inline void read(R T &k)
{
	R char ch=getchar();R T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	k=x*f;
}
template<typename T>inline void write(R T k)
{
	if(k<0)putchar('-'),k=-k;
	if(!k){putchar('0');return;}
	if(k>9)write(k/10);
	putchar(k%10+'0');
}
int Q,n,ans;
int a[MAXN],b[MAXN],c[MAXN],d[MAXN],t[MAXN*MAXN+MAXN];
void solve()
{
	ans=0;read(n);
	for(R int i=1; i<=n; i++)
	{
		read(a[i]);read(b[i]);
		read(c[i]);read(d[i]);
	}
	for(R int i=1; i<=n; i++)
		for(R int j=1; j<=n; j++)
			t[(i-1)*n+j]=c[i]+d[j];
	sort(t+1,t+n*n+1);
	for(R int i=1; i<=n; i++)
		for(R int j=1; j<=n; j++)
		{
			R int tmp=a[i]+b[j];
			ans+=upper_bound(t+1,t+n*n+1,-tmp)-lower_bound(t+1,t+n*n+1,-tmp);
		}
	write(ans);puts("");
	if(Q)puts("");
}
signed main()
{
	read(Q);
	while(Q--)solve();
	return 0;
}

解法二

通过刚才的分析，我们会惊奇的发现这个 $i,j$ 的组合其实是有限的！

那么我们就可以预处理所有的 $a_i+b_j$ 和 $c_k+d_l$

然后用哈希表搞一搞，每次去暴力查表（注：查有没有相反数）

时间复杂度 $O(n^2)$

真的有这么简单吗？

我们来重新分析一下时间复杂度

首先题目中说明给的数小于等于 $2^{28}$

那么每个组合（和）小于$2^{29}$

如果用哈希表搞，理论上来说可以构造hack数据，特别是简单的哈希函数很容易hack

为什么？因为如果哈希函数不是很好，那么至多在一个位置放了 $n^2$ 个数

好耶时间复杂度退化为 $O(n^4)$? 直接TLE

什么你要表内排序？ $O(n^2\log n^2)$? + 可能较大常数 （来自本文作者的奇思妙想）

所以其实理论上来说这个解法是行不通的

如果数据生成器能够分析提交的代码原理并构造hack数据，那么直接玩完

好在没有那么恶心这题，数据比较简单，手写哈希表也能过

代码就不贴了，个人感觉实现很简单而且这解法不是很好 qwq

转载请说明出处