hdu4277 USACO ORZ-----hash 长春网络赛

USACO ORZTime Limit: 5000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 264 Accepted Submission(s): 94


Problem DescriptionInputOutputSample InputSample OutputSourceRecommend#include<iostream>#include<cstdlib>#include<stdio.h>#include<algorithm>#include<memory.h>using namespace std;#define mm 1000007int s[55],n;struct hashtable{ int size,ans[mm][3],next[mm],h[mm]; int hash(int a,int b,int c) { return ((((a*131+b)*131+c)*131)&0x7FFFFFFF)%mm; } void insert(int a,int b,int c) { int id=hash(a,b,c); for(int i=h[id];i>=0;i=next[i]) if(ans[i][0]==a&&ans[i][1]==b&&ans[i][2]==c) return; ans[size][0]=a,ans[size][1]=b,ans[size][2]=c; next[size]=h[id],h[id]=size++; } void clear() { memset(h,-1,sizeof(h)); size=0; }}g;int ai,bi,ci;void check(int a,int b,int c){ if(a+b<=c||a+c<=b||b+c<=a) return ; g.insert(a,b,c);}void dfs(int id){ if(id>=n) { if(ai<=bi&&bi<=ci) check(ai,bi,ci); return ; } ai+=s[id]; dfs(id+1); ai-=s[id]; bi+=s[id]; dfs(id+1); bi-=s[id]; ci+=s[id]; dfs(id+1); ci-=s[id];}int main(){ int t; scanf("%d",&t); while(t--) { g.clear(); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&s[i]); ai=bi=ci=0; dfs(0); printf("%d\n",g.size); }}