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
 9__int64 n,a[max],pos,i,j,ans;
10__int64 sum;
11bool finish;
12
13int cmp(const void *a,const void *b)
14{
15    return *(__int64 *)b > *(__int64 *)a?1:-1;
16}
17
18struct node
19{
20    __int64 next,a,b;
21    __int64 k;
22}hash[len];
23
24void 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
33bool 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
50int 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 阅读(433) 评论(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   博问   Chat2DB   管理


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜