垃圾佬的旅游III(Hash + 暴力)

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

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

垃圾佬的旅游III(Hash + 暴力)垃圾佬的旅游III(Hash + 暴力)
  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遇到负数情况,重复冲突情况以及特判。其他的话也就没什么了。

上一篇:POJ - 3984 迷宫问题 (搜索)


下一篇:python sorted函数