比链表版快一点吧
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #define REP(s, n) for(int i = s; i <= n; i ++) 7 using namespace std; 8 const int maxn = 2000 + 10; 9 const int hash_max = 5677913; 10 const int hash_check = 2787907; 11 const int hash_delta = 2890003; 12 const int hash_find = 40009; 13 const int inf = 1000000001; 14 int hash[hash_max]; 15 bool vis[hash_max]; 16 int hash_sortn(int v){ 17 v %= hash_max; 18 if(v < 0) v += hash_max; 19 return v; 20 } 21 int hash_checkn(int v){ 22 if(v & 1) { v = v % hash_check; if(v < 0) v += hash_check; } 23 else { v = v % hash_check; if(v < 0) v += hash_check; v += hash_delta; } 24 return v; 25 } 26 int hash_findn(int v){ 27 v = (v * hash_find) % hash_max; 28 if(v < 0) v += hash_max; 29 return v; 30 } 31 int find_insert(int v){ 32 int ids = hash_sortn(v); 33 if(!vis[ids]){ //一致性探查 34 hash[ids] = v; 35 vis[ids] = true; 36 return ids; 37 } 38 else if(v == hash[ids]) return ids; 39 int id = hash_checkn(v); 40 if(!vis[id]){ //二次奇偶性探查 41 hash[id] = v; 42 vis[id] = true; 43 return id; 44 } 45 for(int i = id; ; i += hash_findn(i) + ids * i){ //完全性探查 46 i %= hash_max; 47 if(i < 0) i += hash_max; 48 if(!vis[i]){ //二次奇偶性探查 49 hash[i] = v; 50 vis[i] = true; 51 return i; 52 } 53 else if(v == hash[i]) return i; 54 } 55 } 56 bool find(int v){ 57 int ids = hash_sortn(v); 58 if(!vis[ids]) return false; 59 if(hash[ids] == v) return true; 60 int id = hash_checkn(v); 61 if(!vis[id]) return false; 62 if(hash[id] == v) return true; 63 for(int i = id; ; i += hash_findn(i) + ids * i){ //完全性探查 64 i %= hash_max; 65 if(i < 0) i += hash_max; 66 if(!vis[i]) return false; 67 else if(v == hash[i]) return true; 68 } 69 } 70 int b[maxn], c[maxn], d[maxn], n; 71 bool check(int v){ 72 for(int i = n; i; i --){ 73 int temp = v - b[i]; 74 for(int j = n; j; j --){ 75 if(find(temp - c[j])) return true; 76 } 77 } 78 return false; 79 } 80 void read(int &x){ 81 x = 0; int sig = 1; char ch = getchar(); 82 while(!isdigit(ch)) { if(ch == '-') sig = -1; ch = getchar(); } 83 while(isdigit(ch)) x = 10 * x + ch - '0', ch = getchar(); 84 x *= sig; return ; 85 } 86 void init(){ 87 read(n); 88 int temp; 89 REP(1, n) read(temp), find_insert(temp); 90 REP(1, n) read(b[i]); 91 REP(1, n) read(c[i]); 92 REP(1, n) read(d[i]); 93 sort(d + 1, d + 1 + n); 94 sort(c + 1, c + 1 + n); 95 sort(b + 1, b + 1 + n); 96 return ; 97 } 98 int ans = 2000000000; 99 void work(){ 100 for(int i = n; i; i --){ 101 if(check(d[i])) { ans = d[i]; return ; } 102 } 103 return ; 104 } 105 void print(){ 106 if(ans == 2000000000) puts("No Answer."); 107 else printf("%d ", ans); 108 return ; 109 } 110 int main(){ 111 init(); 112 work(); 113 print(); 114 return 0; 115 }
封装起来：
1 const int hash_max = 5677913; 2 const int hash_check = 2787907; 3 const int hash_delta = 2890003; 4 const int hash_find = 40009; 5 const int inf = 1000000001; 6 struct HASH{ 7 int hash[hash_max]; 8 bool vis[hash_max]; 9 HASH() { memset(vis, false, sizeof(vis)); } 10 int hash_sortn(int v){ 11 v %= hash_max; 12 if(v < 0) v += hash_max; 13 return v; 14 15 } 16 int hash_checkn(int v){ 17 if(v & 1) { v = v % hash_check; if(v < 0) v += hash_check; } 18 else { v = v % hash_check; if(v < 0) v += hash_check; v += hash_delta; } 19 return v; 20 } 21 int hash_findn(int v){ 22 v = (v * hash_find) % hash_max; 23 if(v < 0) v += hash_max; 24 return v; 25 } 26 int find_insert(int v){ 27 int ids = hash_sortn(v); 28 if(!vis[ids]){ 29 hash[ids] = v; 30 vis[ids] = true; 31 return ids; 32 } 33 else if(v == hash[ids]) return inf; 34 int id = hash_checkn(v); 35 if(!vis[id]){ 36 hash[id] = v; 37 vis[id] = true; 38 return id; 39 } 40 for(int i = id; ; i += hash_findn(i) + ids * i){ 41 i %= hash_max; 42 if(i < 0) i += hash_max; 43 if(!vis[i]){ 44 hash[i] = v; 45 vis[i] = true; 46 return i; 47 } 48 else if(v == hash[i]) return inf; 49 } 50 } 51 bool find(int v){ 52 int ids = hash_sortn(v); 53 if(!vis[ids]) return false; 54 if(hash[ids] == v) return true; 55 int id = hash_checkn(v); 56 if(!vis[id]) return false; 57 if(hash[id] == v) return true; 58 for(int i = id; ; i += hash_findn(i) + ids * i){ 59 i %= hash_max; 60 if(i < 0) i += hash_max; 61 if(!vis[i]) return false; 62 else if(v == hash[i]) return true; 63 } 64 } 65 }hash;