垃圾佬的旅游III（Hash + 暴力）

题目链接：http://120.78.128.11/Problem.jsp?pid=3445

最开始的思路就是直接暴力求解，先把所有的数值两两存入结构体，再从小到大枚举。用二分的思路去判断数值以及出现，结果TLE，但优化一下应该也能过，因为题目说只有两组数据。代码如下：

 #include <iostream>

 #include <string>

 #include <cstdio>

 #include <cstdlib>

 #include <sstream>

 #include <iomanip>

 #include <map>

 #include <stack>

 #include <deque>

 #include <queue>

 #include <vector>

 #include <set>

 #include <list>

 #include <cstring>

 #include <cctype>

 #include <algorithm>

 #include <iterator>

 #include <cmath>

 #include <bitset>

 #include <ctime>

 #include <fstream>

 #include <limits.h>

 #include <numeric>

 using namespace std;

 #define F first

 #define S second

 #define mian main

 #define ture true

 #define MAXN 1000000+5

 #define MOD 1000000007

 #define PI (acos(-1.0))

 #define EPS 1e-6

 #define MMT(s) memset(s, 0, sizeof s)

 typedef unsigned long long ull;

 typedef long long ll;

 typedef double db;

 typedef long double ldb;

 typedef stringstream sstm;

 const int INF = 0x3f3f3f3f;

 int n;

 int ans,tot;

 int a[];

 struct node{

     int x,a,b;

     bool operator < (const node &b) const{

         return x < b.x;

     }

 }q[MAXN];

 int find_f(int x,int a,int b){

     int l(),r = tot;

     while(l<r){

         int mid = (l + r) >> ;

         if(q[mid].x < x)

             l = mid+;

         else

             r = mid;

     }

     while(l < tot && q[l].x == x){

         if(q[l].a != a && q[l].b != a && q[l].a != b && q[l].b != b)

             break;

         l++;

     }

     if(q[l].x != x)

         return ;

     return ;

 }

 int main(){

     ios_base::sync_with_stdio(false);

     cout.tie();

     cin.tie();

     while(scanf("%d",&n)!=EOF){

         if(!n)

             break;

         for(int i = ; i <= n; i++)

             scanf("%d",&a[i]);

         ans = -INF;

         tot = ;

         MMT(q);

         for(int i = ; i < n; i++){

             for (int j = i+; j <= n; j++){

                 q[tot].x = a[i] + a[j];

                 q[tot].a = i;

                 q[tot++].b = j;

             }

         }

         sort(q,q+tot);

         for(int i = ; i <= n; i++){

             for(int j = ; j <= n; j++){

                 if(i != j){

                     int t = a[i]-a[j];

                     if(find_f(t,i,j)){

                         if(a[i] > ans)

                             ans = a[i];

                     }

                 }

             }

         }

         if(ans == -INF)

             printf("No Solution\n");

         else

             printf("%d\n",ans);

     }

     return ;

 }

AC思路是队友告诉我的，在暴力枚举的基础上加一个Hash维护。还是记录两两的和，再枚举第三个数，但这里判断一下第三个数和答案是否在两两数和中存在就行了。判断就是每两个数标记一下，排进哈希散列表就行了。值得注意的是，哈希因为本质是同余，所以需要加一句特判，在判断存在之后，取出组成两两和的那两数，再判断三个值是否相等。

为什么要加特判，因为哈希是MOD 一个 P ,所以可能出现重复。

还有就是哈希MOD P而不能是任意数，开始就mod1e6+5虽然对于两组数据可能没问题，但是最好还是改成质数例如(1e6+3);

AC代码：

 #include <iostream>

 #include <string>

 #include <cstdio>

 #include <cstdlib>

 #include <sstream>

 #include <iomanip>

 #include <map>

 #include <stack>

 #include <deque>

 #include <queue>

 #include <vector>

 #include <set>

 #include <list>

 #include <cstring>

 #include <cctype>

 #include <algorithm>

 #include <iterator>

 #include <cmath>

 #include <bitset>

 #include <ctime>

 #include <fstream>

 #include <limits.h>

 #include <numeric>

 using namespace std;

 #define F first

 #define S second

 #define mian main

 #define ture true

 #define MAXN 1000000+5

 #define MOD 1000000007

 #define PI (acos(-1.0))

 #define EPS 1e-6

 #define MMT(s) memset(s, 0, sizeof s)

 typedef unsigned long long ull;

 typedef long long ll;

 typedef double db;

 typedef long double ldb;

 typedef stringstream sstm;

 const int INF = 0x3f3f3f3f;

 int n, a[], Hash[],d;

 int MAXn = MAXN - ;

 struct node{

     int x,a,b;

     bool operator < (const node &b) const{

         return x < b.x;

     }

 }q[MAXN];

 int check(int tp, int a, int b){

     return (q[tp].a == a || q[tp].b == a || q[tp].b == a || q[tp].b == b);

 }

 int main(){

     ios_base::sync_with_stdio(false);

     cout.tie();

     cin.tie();

     while(scanf("%d",&n)!=EOF){

         d = ;

         MMT(Hash);

         MMT(q);

         for(int i = ; i <= n; i++)

             scanf("%d",a+i);

         sort(a+,a++n);

         for(int i = ; i < n; i++)

             for(int j = i+; j <= n; j++){

                 int k = (a[i]+a[j]) % MAXn;

                 if(k < ) k += MAXn;

                 if(!Hash[k]) {

                     Hash[k] = ++d;

                     q[d].a = i, q[d].b = j;

                 }else{

                     d++;

                     int tp = Hash[k];

                     while(q[tp].x)

                         tp = q[tp].x;

                     q[tp].x = d;

                     q[d].a = i, q[d].b = j;

                 }

             }

         int ans = n, flag = ;

         for(; ans && flag; ans--)

             for(int i = n; i; i--){

                 if(i == ans)

                     continue;

                 int k = (a[ans]-a[i]) % MAXn;

                 if(k < )

                     k += MAXn;

                 if(!Hash[k])

                     continue;

                 int tp = Hash[k];

                 while(check(tp, i, ans) && q[tp].x)

                     tp = q[tp].x;

                 if(!check(tp, i, ans) && tp){

                     if(a[q[tp].a] + a[q[tp].b] + a[i] != a[ans]) continue;

                     flag = ;

                     printf("%d\n", a[ans]);

                     break;

                 }

             }

         if(flag)

             printf("No Solution\n");

     }

     return ;

 }

emmmm还有就是冲突处理，数组模拟一下链表就行了 =7=

这个题可能无从入手的地方就是不知道该怎么模拟，直接四个数枚举肯定炸，然后二二模拟也不行，所以就肯定需要一些手段进行维护和判断。所以就要开数组标记呀，但肯定这么大的数开不了，那么就只好压缩数组了，这里就想到了二分去判断第三个数以及答案是否存在，但是又TLE，那就hash呗，反正处理数据的只有那么几种方法。

一些小问题就是写hash遇到负数情况，重复冲突情况以及特判。其他的话也就没什么了。

巴特西

垃圾佬的旅游III（Hash + 暴力）

最新文章

热门文章