最新日韩欧美,亚洲欧美视频在线,一区二区在线视频播放

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 閱讀(461) 評論(3) 編輯收藏引用

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

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

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

pku 2549

評論

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理