SP1296 SUMFOUR - 4 values whose sum is 0 题解

原题目链接

首先想到$\Theta(n^4)$的暴力枚举，但$n\le 4000$显然不行。

考虑先预处理出c数组和d数组的和，再暴力计算答案。

由于c数组和d数组的和可能会有重复，排序后使用二分来降低时间复杂度

最终时间复杂度$\Theta (n^2\log n)$

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=4010;
int n,nn,a[N],b[N],c[N],d[N],sum[N*N],ans=0;
inline void read(int &x)
{
    char ch=getchar();
    int f=1;
    x=0;
    while(!('0'<=ch&&ch<='9'))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    do
    {
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }while('0'<=ch&&ch<='9');
    x*=f;
}
inline int calc(int x,int y)//降维，将二维转化成一维
{
	return (x-1)*n+y;
}
int main()
{
	read(n);
	nn=n*n;
	for(int i=1;i<=n;++i)
		read(a[i]),read(b[i]),read(c[i]),read(d[i]);
	for(int i=1;i<=n;++i)//预处理出c数组和d数组的和
		for(int j=1;j<=n;++j)
		{
			sum[calc(i,j)]=c[i]+d[j];
		}
	sort(sum+1,sum+nn+1);//排序，因为二分需要单调性
	for(int i=1;i<=n;++i)//暴力枚举a数组和b数组的和
	{
		for(int j=1;j<=n;++j)
		{
			ans+=upper_bound(sum+1,sum+nn+1,-a[i]-b[j])-lower_bound(sum+1,sum+nn+1,-a[i]-b[j]);//二分计算有多少个重复答案
		}
	}
	printf("%d",ans);
	return 0;
}