UVA11524 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)\)

代码如下

#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