POJ_2785

思路

可以发现时间给了15000ms，这道题枚举的话4000^4次，会T。用折半枚举的方法。先枚举a，b的16000000的可能性，在用lower，upper bound去这帮查找。复杂度40004000log(4000)。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <complex>
#include <cstdio>
using namespace std;
#define ll long long
#define N 4008
int a[N],b[N],c[N],d[N],ab[N*N];
int main(){
    int n;cin>>n;
    for(int i=0 ; i<n ; i++){
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
    }
    for(int i=0 ; i<n ;i++)
        for(int j=0 ; j<n ;j++)
            ab[i*n +j]=a[i]+b[j];
    sort(ab,ab+n*n);
    int ans=0;
    for(int i=0 ; i<n ;i++)
        for(int j=0 ; j<n ;j++){
            int tmp=-(c[i]+d[j]);
            ans+=upper_bound(ab,ab+n*n,tmp)-lower_bound(ab,ab+n*n,tmp);
        }
    printf("%d\n",ans);
}