题目链接：http://poj.org/problem?id=2785
强烈鄙视自己啊，开始以为数据简单，结果用map标记一下，TLE了，然后改成动态化的hash，结果还是TLE！后来无奈改成静态化的hash才AC！至于动态化的hash超时，应该是申请内存的时候占用了太多的CPU的资源吧。这题sort+二分也可以做，但是map就不能搞了，可见STL的效率啊！
1 //STATUS:C++_AC_4844MS_132304KB 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<math.h> 6 #include<iostream> 7 #include<string> 8 #include<algorithm> 9 #include<vector> 10 #include<queue> 11 #include<stack> 12 #include<map> 13 using namespace std; 14 #define LL __int64 15 #define pii pair<int,int> 16 #define Max(a,b) ((a)>(b)?(a):(b)) 17 #define Min(a,b) ((a)<(b)?(a):(b)) 18 #define mem(a,b) memset(a,b,sizeof(a)) 19 #define lson l,mid,rt<<1 20 #define rson mid+1,r,rt<<1|1 21 const int MAX=4010,INF=0x3f3f3f3f,MOD=9999997; 22 const LL LLNF=0x3f3f3f3f3f3f3f3fLL; 23 24 struct Node{ 25 int a,c,next; 26 }e[MAX*MAX*2]; 27 int num[MAX][4],g[MAX*MAX],hal[MOD],har[MOD]; 28 int n,m; 29 30 int build(int *ha,int a) 31 { 32 int i,t=(a%MOD+MOD)%MOD; 33 for(i=ha[t];i!=-1;i=e[i].next){ 34 if(a==e[i].a) 35 return ++e[i].c; 36 } 37 e[m].a=a;e[m].c=1; 38 e[m].next=ha[t]; 39 ha[t]=m++; 40 return 0; 41 } 42 43 int find(int *ha,int a) 44 { 45 int i,t=(a%MOD+MOD)%MOD; 46 for(i=ha[t];i!=-1;i=e[i].next){ 47 if(a==e[i].a) 48 return e[i].c; 49 } 50 return 0; 51 } 52 53 int main() 54 { 55 // freopen("in.txt","r",stdin); 56 int i,j,ans,t; 57 scanf("%d",&n); 58 ans=m=0; 59 g[0]=0; 60 mem(hal,-1); 61 mem(har,-1); 62 for(i=0;i<n;i++) 63 scanf("%d%d%d%d",num[i],num[i]+1,num[i]+2,num[i]+3); 64 for(i=0;i<n;i++){ 65 for(j=0;j<n;j++){ 66 t=-num[i][0]-num[j][1]; 67 if(!build(hal,t)) 68 g[++g[0]]=t; 69 } 70 } 71 for(i=0;i<n;i++){ 72 for(j=0;j<n;j++){ 73 t=num[i][2]+num[j][3]; 74 build(har,t); 75 } 76 } 77 for(i=1;i<=g[0];i++) 78 if(t=find(har,g[i]))ans+=find(hal,g[i])*t; 79 80 printf("%d\n",ans); 81 return 0; 82 }