题意：四个元素个数相等的A,B,C,D，问a+b+c+d=0的个数$(a\in{A},b\in{B},c\in{C},d\in{D})$,$n<=10^3$

 

所以

$n^4$????

肯定不行的啊

用sum1处理出a+b的和

用sum2处理出c+d的和

然后枚举sum1，二分找sum2，求ans

然而。。。。。WA

 

原因：可能在sum2中有相同元素，然而只算了一次

改：不用判断是否=0，求一个upper_bound和一个lower_bound，加上它们的差即可

#include
     
      #include
      
       #include
       
        using namespace std;int n;int a[4020];int b[4020];int c[4020];int d[4020];int sum1[16005000];int sum2[16005000];int len;int ans;int main(){    ios::sync_with_stdio(false);    ans=0;    cin>>n;    for(int i=1;i<=n;i++)        cin>>a[i]>>b[i]>>c[i]>>d[i];    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            sum1[++len]=a[i]+b[j];    len=0;    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            sum2[++len]=c[i]+d[j];    sort(sum2+1,sum2+len+1);    for(int i=1;i<=len;i++)    {        int cnt=upper_bound(sum2+1,sum2+len+1,-sum1[i])-sum2;        int pos=lower_bound(sum2+1,sum2+len+1,-sum1[i])-sum2;        ans=ans+cnt-pos;    }     cout<
        
         <