題目連結：http://120.78.128.11/Problem.jsp?pid=3445
最開始的思路就是直接暴力求解，先把所有的數值兩兩存入結構體，再從小到大枚舉。用二分的思路去判斷數值以及出現，結果TLE，但優化一下應該也能過，因為題目說隻有兩組資料。代碼如下：
1 #include <iostream>
2 #include <string>
3 #include <cstdio>
4 #include <cstdlib>
5 #include <sstream>
6 #include <iomanip>
7 #include <map>
8 #include <stack>
9 #include <deque>
10 #include <queue>
11 #include <vector>
12 #include <set>
13 #include <list>
14 #include <cstring>
15 #include <cctype>
16 #include <algorithm>
17 #include <iterator>
18 #include <cmath>
19 #include <bitset>
20 #include <ctime>
21 #include <fstream>
22 #include <limits.h>
23 #include <numeric>
24
25 using namespace std;
26
27 #define F first
28 #define S second
29 #define mian main
30 #define ture true
31
32 #define MAXN 1000000+5
33 #define MOD 1000000007
34 #define PI (acos(-1.0))
35 #define EPS 1e-6
36 #define MMT(s) memset(s, 0, sizeof s)
37 typedef unsigned long long ull;
38 typedef long long ll;
39 typedef double db;
40 typedef long double ldb;
41 typedef stringstream sstm;
42 const int INF = 0x3f3f3f3f;
43
44 int n;
45 int ans,tot;
46 int a[1010];
47 struct node{
48 int x,a,b;
49 bool operator < (const node &b) const{
50 return x < b.x;
51 }
52 }q[MAXN];
53
54 int find_f(int x,int a,int b){
55 int l(0),r = tot;
56 while(l<r){
57 int mid = (l + r) >> 1;
58 if(q[mid].x < x)
59 l = mid+1;
60 else
61 r = mid;
62 }
63 while(l < tot && q[l].x == x){
64 if(q[l].a != a && q[l].b != a && q[l].a != b && q[l].b != b)
65 break;
66 l++;
67 }
68 if(q[l].x != x)
69 return 0;
70 return 1;
71 }
72
73 int main(){
74 ios_base::sync_with_stdio(false);
75 cout.tie(0);
76 cin.tie(0);
77 while(scanf("%d",&n)!=EOF){
78 if(!n)
79 break;
80 for(int i = 1; i <= n; i++)
81 scanf("%d",&a[i]);
82 ans = -INF;
83 tot = 0;
84 MMT(q);
85 for(int i = 1; i < n; i++){
86 for (int j = i+1; j <= n; j++){
87 q[tot].x = a[i] + a[j];
88 q[tot].a = i;
89 q[tot++].b = j;
90 }
91 }
92 sort(q,q+tot);
93 for(int i = 1; i <= n; i++){
94 for(int j = 1; j <= n; j++){
95 if(i != j){
96 int t = a[i]-a[j];
97 if(find_f(t,i,j)){
98 if(a[i] > ans)
99 ans = a[i];
100 }
101 }
102 }
103 }
104 if(ans == -INF)
105 printf("No Solution\n");
106 else
107 printf("%d\n",ans);
108 }
109 return 0;
110 } View Code
AC思路是隊友告訴我的，在暴力枚舉的基礎上加一個Hash維護。還是記錄兩兩的和，再枚舉第三個數，但這裡判斷一下第三個數和答案是否在兩兩數和中存在就行了。判斷就是每兩個數标記一下，排進哈希散清單就行了。值得注意的是，哈希因為本質是同餘，是以需要加一句特判，在判斷存在之後，取出組成兩兩和的那兩數，再判斷三個值是否相等。
為什麼要加特判 ，因為哈希是MOD 一個 P ,是以可能出現重複。
還有就是哈希MOD P而不能是任意數，開始就mod1e6+5雖然對于兩組資料可能沒問題，但是最好還是改成質數例如(1e6+3);
AC代碼：
1 #include <iostream>
2 #include <string>
3 #include <cstdio>
4 #include <cstdlib>
5 #include <sstream>
6 #include <iomanip>
7 #include <map>
8 #include <stack>
9 #include <deque>
10 #include <queue>
11 #include <vector>
12 #include <set>
13 #include <list>
14 #include <cstring>
15 #include <cctype>
16 #include <algorithm>
17 #include <iterator>
18 #include <cmath>
19 #include <bitset>
20 #include <ctime>
21 #include <fstream>
22 #include <limits.h>
23 #include <numeric>
24
25 using namespace std;
26
27 #define F first
28 #define S second
29 #define mian main
30 #define ture true
31
32 #define MAXN 1000000+5
33 #define MOD 1000000007
34 #define PI (acos(-1.0))
35 #define EPS 1e-6
36 #define MMT(s) memset(s, 0, sizeof s)
37 typedef unsigned long long ull;
38 typedef long long ll;
39 typedef double db;
40 typedef long double ldb;
41 typedef stringstream sstm;
42 const int INF = 0x3f3f3f3f;
43
44 int n, a[1001], Hash[1000005],d;
45 int MAXn = MAXN - 2;
46 struct node{
47 int x,a,b;
48 bool operator < (const node &b) const{
49 return x < b.x;
50 }
51 }q[MAXN];
52
53 int check(int tp, int a, int b){
54 return (q[tp].a == a || q[tp].b == a || q[tp].b == a || q[tp].b == b);
55 }
56
57 int main(){
58 ios_base::sync_with_stdio(false);
59 cout.tie(0);
60 cin.tie(0);
61 while(scanf("%d",&n)!=EOF){
62 d = 0;
63 MMT(Hash);
64 MMT(q);
65 for(int i = 1; i <= n; i++)
66 scanf("%d",a+i);
67 sort(a+1,a+1+n);
68 for(int i = 1; i < n; i++)
69 for(int j = i+1; j <= n; j++){
70 int k = (a[i]+a[j]) % MAXn;
71 if(k < 0) k += MAXn;
72 if(!Hash[k]) {
73 Hash[k] = ++d;
74 q[d].a = i, q[d].b = j;
75 }else{
76 d++;
77 int tp = Hash[k];
78 while(q[tp].x)
79 tp = q[tp].x;
80 q[tp].x = d;
81 q[d].a = i, q[d].b = j;
82 }
83 }
84
85 int ans = n, flag = 1;
86 for(; ans && flag; ans--)
87 for(int i = n; i; i--){
88 if(i == ans)
89 continue;
90 int k = (a[ans]-a[i]) % MAXn;
91 if(k < 0)
92 k += MAXn;
93 if(!Hash[k])
94 continue;
95 int tp = Hash[k];
96 while(check(tp, i, ans) && q[tp].x)
97 tp = q[tp].x;
98 if(!check(tp, i, ans) && tp){
99 if(a[q[tp].a] + a[q[tp].b] + a[i] != a[ans]) continue;
100 flag = 0;
101 printf("%d\n", a[ans]);
102 break;
103 }
104 }
105 if(flag)
106 printf("No Solution\n");
107 }
108 return 0;
109 } emmmm還有就是沖突處理，數組模拟一下連結清單就行了 =7=
這個題可能無從入手的地方就是不知道該怎麼模拟，直接四個數枚舉肯定炸，然後二二模拟也不行，是以就肯定需要一些手段進行維護和判斷。是以就要開數組标記呀， 但肯定這麼大的數開不了，那麼就隻好壓縮數組了，這裡就想到了二分去判斷第三個數以及答案是否存在，但是又TLE，那就hash呗，反正處理資料的隻有那麼幾種方法。
一些小問題就是寫hash遇到負數情況，重複沖突情況以及特判。其他的話也就沒什麼了。