UVA 10125 - Sumsets（POJ 2549） hash

题目大意：

给定一个整数几何S，找出一个最大的d，使得a+b+c=d，其中a,b,c,d是S中不同的元素。

S的个数最大为1000。

思路：

直接暴力枚举a,b,c,d必挂。

上面的式子移向得：a+b=d-c。我们先预处理所有的和，并且插入Hash表。

然后枚举d和c，看是否在Hash表中是否存在。

若存在且不同，则更新d。

类似的题目还有：

HDU 1496 Equations hash HDU上排名第一！

POJ 2785 4 Values whose Sum is 0 Hash！

HDU 1407 测试你是否和LTC水平一样高 枚举、二分、hash

PS:

一开始这里的

if(data[i].sum!=sum || data[i].a==a ||data[i].a==b ||data[i].b==a ||data[i].b==b )

data[i].b==b 然后WA到哭了。。呜呜呜呜，后来发现想撞死。。来去吃点好吃的安慰一下我受伤的心灵。哈哈

0.072S，让暴力枚举的见鬼去吧~

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=1024; const int mod=1<<18; int x[MAXN],head[mod],len; struct data { int a,b,sum; int next; }data[MAXN*MAXN]; inline int gethash(int x) { if(x<0) x=-x; //变为正的 return (x) & (mod-1); } void insert(int a,int b,int sum) { int cur=gethash(sum); for(int i=head[cur];i!=-1;i=data[i].next) { if(data[i].sum==sum && data[i].a==a && data[i].b==b) return; } data[len].a=a; data[len].b=b; data[len].sum=sum; data[len].next=head[cur]; head[cur]=len++; } bool search(int a,int b,int sum) { int cur=gethash(sum); for(int i=head[cur];i!=-1;i=data[i].next) { if(data[i].sum!=sum || data[i].a==a || data[i].a==b || data[i].b==a || data[i].b==b ) continue; return true; } return false; } int main() { int n; while(~scanf(%d,&n),n) { len=0; memset(head,-1,sizeof(head)); for(int i=0;i