等式数量---hash算法

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 50050
 4 int s[N]={0},a[N],vis[N];
 5 int hash(int x)
 6 {
 7     int y=(x%N+N)%N;
 8     while(vis[y]&&s[y]!=x)
 9     y=(y+1)%N;
10     return y;
11 }
12 int insert(int x)
13 {
14     int y=hash(x);
15     vis[y]=1;
16     s[y]=x;
17 }
18 int find(int x)
19 {
20    return vis[hash(x)];
21 }
22 int main()
23 {
24     int n,i,j;
25     while(~scanf("%d",&n))
26     {
27         memset(vis,0,sizeof(vis));
28         for(i=0;i<n;i++)
29         {
30             scanf("%d",&a[i]);
31             insert(a[i]);
32         }
33         int sum=0;
34         for(i=0;i<n;i++)
35         {
36             for(j=i+1;j<n;j++)
37             {
38                 if(a[i]&&a[j]&&find(a[i]+a[j])==1)
39                 sum++;
40             }
41         }
42         printf("%d
",sum);
43     }
44 }

View Code

D - 等式数量

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status Practice FZU 1707

Description

集合是基本的数学概念，它是集合论的研究对象。关于集合论最简单的说法，是在最原始的集合论《朴素集合论》中的定义：集合就是“一堆东西”。集合里的“东西”，叫作元素。若x是集合A中的元素，记作 x∈A。集合中的元素是互不相同的。
表示相等关系的式子叫做等式。
给你一个包含有N个整数的集合，如果从集合中找到三个不同的整数a,b,c使得a+b=c，那么我们说这个集合包含一个等式。
你的任务是从集合中找出所有的等式数量。

Input

每组输入数据的第一行为一个整数N (3<=N<=5,000)，表示集合中一共有N个不同的整数。之后一行有N个整数，表示集合中的元素，元素的整数值大小为(-10,000,000~10,000,000)。

Output

对于每组数据输出一个整数占一行，表示该集合的等式数量。

Sample Input

4
3 1 2 5

Sample Output