pku 2549

2009年7月19日

题目链接：PKU 2549 Sumsets

分类：哈希

题目分析与算法原型
题目是求在给定的一些数的集合中，找最大的d，满足d=a+b+c,其中a,b,c,d都属于集合S,且集合中的数都各不相同，若没有这样的d则输出“no solution”..........其实，我们可以把这个式子变换一下，d-c=a+b,然后枚举每两个数，将他们的和作为关键值建立哈希表，然后再一次枚举每两个数，这次以他们的差（较大的数减去较小的数）作为关键值在哈希表中找是否有相同的。
注意，这道题目要求是求满足条件的最大的d,因此，我们可以先按从大到小排序，然后再从最左边的开始枚举，若找到则直接退出枚举，这样就可以保证找到的d一定就是最大的。

Code:

1

#include<stdio.h>
2

#include<stdlib.h>
3

#include<string.h>
4

#define max 1005
5

#define pianyi 600000000
6

#define prime 199997
7

#define len 800000
8

__int64 n,a[max],pos,i,j,ans;
10

__int64 sum;
11

bool finish;
12

int cmp(const void *a,const void *b)
14

{
15

return *(__int64 *)b > *(__int64 *)a?1:-1;
16

}
17

struct node
19

{
20

__int64 next,a,b;
21

__int64 k;
22

}hash[len];
23

void Hash(__int64 m)
25

{
26

__int64 now=m%prime;
27

while(hash[now].next!=-1)now=hash[now].next;
28

hash[pos].next=-1;
29

hash[now].next=pos;
30

pos++;
31

}
32

bool Hash_find(__int64 m,int a,int b)
34

{
35

__int64 now=m%prime;
36

while(hash[now].next!=-1)
37

{
38

if(m==hash[hash[now].next].k)
39

{
40

if(a!=hash[hash[now].next].a
41

&&a!=hash[hash[now].next].b
42

&&b!=hash[hash[now].next].a
43

&&b!=hash[hash[now].next].b)return true;
44

}
45

now=hash[now].next;
46

}
47

return false;
48

}
49

int main()
51

{
52

while(scanf("%I64d",&n)!=EOF&&n)
53

{
54

pos=prime+3;
55

finish=false;
56

memset(hash,-1,sizeof(hash));
57

for(i=0;i<n;i++)scanf("%I64d",&a[i]);
58

qsort(a,n,sizeof(a[0]),cmp);
59

for(i=0;i<n;i++)
60

for(j=i+1;j<n;j++)
61

{
62

sum=a[i]+pianyi+a[j]+pianyi;
63

hash[pos].k=sum;
64

hash[pos].a=i;
65

hash[pos].b=j;
66

Hash(sum);
67

}
68

for(i=0;i<n&&!finish;i++)
69

for(j=i+1;j<n&&!finish;j++)
70

{
71

sum=a[i]-a[j]+pianyi+pianyi;
72

if(Hash_find(sum,i,j))
73

{
74

finish=true;
75

ans=a[i];
76

}
77

}
78

if(finish)printf("%I64d\n",ans);
79

else printf("no solution\n");
80

}
81

return 0;
82

}
83

posted on 2009-07-19 13:27 蜗牛也Coding 阅读(378) 评论(3) 编辑收藏引用

# re: pku 2549 2009-08-12 20:20 alpc32

int就够了吧，博主在弄ACM不，是的话交个朋友吧！回复更多评论

# re: pku 2549 2009-08-12 20:32 蜗牛也Coding

@alpc32
恩，最近在做ACM.......
回复更多评论

# re: pku 2549 2009-08-12 22:39 alpc32

@蜗牛也Coding
my qq:594400720有兴趣一起探讨下ACM的加我回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2009年12月

日

一

二

三

四

五

六

统计

随笔 - 78
文章 - 0
评论 - 96
引用 - 0

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

积分 - 90620
排名 - 259