{"id":65,"date":"2010-01-02T16:22:00","date_gmt":"2010-01-02T08:22:00","guid":{"rendered":"http:\/\/localhost\/?p=65"},"modified":"2010-01-02T16:22:00","modified_gmt":"2010-01-02T08:22:00","slug":"spoj_4580_abcdef","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=65","title":{"rendered":"SPOJ 4580 ABCDEF"},"content":{"rendered":"

\u7ed9\u4e00\u4e2a\u5927\u5c0f\u4e8e100\u7684\u96c6\u5408S
\u6c42\u6ee1\u8db3\u4e0b\u4e24\u5f0f\u7684\u516d\u5143\u7ec4\u4e2a\u6570\u3002\u3002
<\/p>\n


d\uff01\uff1d0\u3002\u3002\u3002
\u5316\u4e00\u4e0b\uff0ca*b+c=(e+f)*d\u3002\u3002
\u73b0\u7528Hash\u628a\u6240\u6709efd\u679a\u4e3e\u4e00\u4e0b\uff0cHash\u5b58\u4e0b\u7ed3\u679c\u3002\u3002
\u7136\u540e\u679a\u4e3eabc\u5c31OK\u4e86\u3002\u3002
O(n^3)
\u8fd9\u63d0\u793a\u6211\u4e00\u822c\u7684\u627e\u4e2a\u6570\u7684\u9898\u76ee\uff0c\u5982\u679c\u9002\u5f53Hash\u90fd\u53ef\u4ee5\u964d\u4f4e\u590d\u6742\u5ea6\u3002\u3002\u3002
Code:
#include<cstdio>
#include<cstring>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int size=100007;
class Hash
{
struct node
{
int x,s;
node*next;
}*H[size],Data[1000000],*Now;
node* new_node(int x,int s,node*n)
{
Now->x=x;Now->s=s;Now->next=n;
return Now++;
}
int Code(int x)
{
if(x<0)x=-x;
return x%size;
}
public:
Hash()
{
Now=Data;
memset(H,0,sizeof(H));
}
void ins(int x)
{
int h=Code(x);
for(node*p=H[h];p;p=p->next)
if(p->x==x)
{p->s++;return;}
node*q=new_node(x,1,H[h]);
H[h]=q;
}
int find(int x)
{
int h=Code(x);
for(node*p=H[h];p;p=p->next)
if(p->x==x)
return p->s;
return 0;
}
};
class solve
{
int n,A[100];
void init()
{
scanf("%d",&n);
REP(i,n)
scanf("%d",A+i);
}
void work()
{
Hash H;
REP(i,n)REP(j,n)REP(k,n)if(A[k])
H.ins((A[i]+A[j])*A[k]);
int ans=0;
REP(i,n)REP(j,n)REP(k,n)
ans+=H.find(A[i]*A[j]+A[k]);
printf<\/a>("%dn",ans);
}
public:
solve()
{
init();
work();
}
};
int main()
{
solve now;
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u7ed9\u4e00\u4e2a\u5927\u5c0f\u4e8e100\u7684\u96c6\u5408S\u6c42\u6ee1\u8db3\u4e0b\u4e24\u5f0f\u7684\u516d\u5143\u7ec4\u4e2a\u6570\u3002\u3002 d\uff01\uff1d0\u3002\u3002\u3002\u5316\u4e00\u4e0b\uff0ca*b+c=(e+f)*d\u3002\u3002\u73b0\u7528Hash\u628a\u6240\u6709efd\u679a\u4e3e\u4e00\u4e0b\uff0cHash\u5b58\u4e0b\u7ed3\u679c\u3002\u3002\u7136\u540e\u679a\u4e3eabc\u5c31OK\u4e86\u3002\u3002O(n^3)\u8fd9\u63d0\u793a\u6211\u4e00\u822c\u7684\u627e\u4e2a\u6570\u7684\u9898\u76ee\uff0c\u5982\u679c\u9002\u5f53Hash\u90fd\u53ef\u4ee5\u964d\u4f4e\u590d\u6742\u5ea6\u3002\u3002\u3002Code:#include<cstdio>#include<cstring>#define REP(i,n) for(int i=0;i<n;i++)using namespace std;const int size=100007;class Hash{ struct node { int x,s; node*next; }*H[size],Data[1000000],*Now; node* new_node(int x,int s,node*n) { Now->x=x;Now->s=s;Now->next=n; return Now++; } int Code(int x) { if(x<0)x=-x; return x%size; } public: Hash() { Now=Data; memset(H,0,sizeof(H)); } void ins(int x) { int h=Code(x); for(node*p=H[h];p;p=p->next) if(p->x==x) {p->s++;return;} node*q=new_node(x,1,H[h]); H[h]=q; } int find(int x) […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/65"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=65"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/65\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=65"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=65"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=65"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}