国产有码一区二区,一本久久a久久精品亚洲,久久视频国产精品免费视频在线

對(duì)于蝸牛來(lái)說(shuō)，狂奔雖不代表極速，但展現(xiàn)的卻是一種拼盡全力的姿態(tài)........

pku 2549

2009年7月19日

題目鏈接：PKU 2549 Sumsets

分類(lèi)：哈希

題目分析與算法原型
題目是求在給定的一些數(shù)的集合中，找最大的d，滿(mǎn)足d=a+b+c,其中a,b,c,d都屬于集合S,且集合中的數(shù)都各不相同，若沒(méi)有這樣的d則輸出“no solution”..........其實(shí)，我們可以把這個(gè)式子變換一下，d-c=a+b,然后枚舉每?jī)蓚€(gè)數(shù)，將他們的和作為關(guān)鍵值建立哈希表，然后再一次枚舉每?jī)蓚€(gè)數(shù)，這次以他們的差（較大的數(shù)減去較小的數(shù)）作為關(guān)鍵值在哈希表中找是否有相同的。
注意，這道題目要求是求滿(mǎn)足條件的最大的d,因此，我們可以先按從大到小排序，然后再?gòu)淖钭筮叺拈_(kāi)始枚舉，若找到則直接退出枚舉，這樣就可以保證找到的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

9

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

__int64 sum;
11

bool finish;
12

13

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

{
15

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

}
17

18

struct node
19

{
20

__int64 next,a,b;
21

__int64 k;
22

}hash[len];
23

24

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

33

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

50

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

評(píng)論

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

int就夠了吧，博主在弄ACM不，是的話(huà)交個(gè)朋友吧！回復(fù) 更多評(píng)論

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

@alpc32
恩，最近在做ACM.......
回復(fù) 更多評(píng)論

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

@蝸牛也Coding
my qq:594400720有興趣一起探討下ACM的加我回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

<

2010年8月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

31

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

28

29

30

31

1

2

3

4

導(dǎo)航

統(tǒng)計(jì)

隨筆 - 78
文章 - 0
評(píng)論 - 96
引用 - 0

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

積分 - 95328
排名 - 261