UVA 10125 - Sumsets(POJ 2549) hash
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1066
http://poj.org/problem?id=2549
テーマ:
整数幾何学Sが与えられ、a+b+c=dとなるように最大の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で1位!
POJ 2785 4 Values whose Sum is 0 Hash!
HDU 1407はあなたがLTCレベルと同じように高い列挙、2点、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.072 S、暴力列挙の鬼に会いに行こう~
http://poj.org/problem?id=2549
テーマ:
整数幾何学Sが与えられ、a+b+c=dとなるように最大の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で1位!
POJ 2785 4 Values whose Sum is 0 Hash!
HDU 1407はあなたがLTCレベルと同じように高い列挙、2点、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.072 S、暴力列挙の鬼に会いに行こう~
#include<cstdio>
#include<cstring>
#include<algorithm>
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<n;i++)
scanf("%d",&x[i]);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
insert(i,j,x[i]+x[j]);
// insert(x[i],x[j],x[i]+x[j]); , 。
// 。
bool ok=false;
int ans=-999999999;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j) continue;
if(search(i,j,x[i]-x[j]))
{
ok=true;
ans=max(ans,x[i]);
break;
}
}
}
if(ok) printf("%d
",ans);
else puts("no solution");
}
return 0;
}