HDU 4334 5-sum

题目大意：

从5个集合中个选取一个数出来，使5个数相加之和为0 ，判断是否存在这种可能

因为集合数目最多200，那么200^3 = 8000000 ，那么这里很明显要把5个数拆成2个和3个计算，因为3个的话有8000000种可能，不好保存

所以只先算前两个数40000种相加的可能性保存到hash表中，然后再后面800000次找hash表中是否存在对应的值

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <set>

 #include <queue>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 using namespace std;

 #define N 205

 #define MOD 1000007

 typedef long long ll;

 int n;

 ll v[][N] ;

 int head[MOD+] , k;

 struct HashNode{

     ll val;

     int next;

 }_hash[MOD];

 void insert(ll key)

 {

     int pos = abs(key)%MOD;

     _hash[k].val = key , _hash[k].next = head[pos];

     head[pos] = k++;

 }

 bool search(ll key)

 {

     int pos = abs(key)%MOD;

     for(int i=head[pos] ; ~i ; i=_hash[i].next)

         if(key == _hash[i].val) return true;

     return false;

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("a.in" , "r" , stdin);

     #endif // ONLINE_JUDGE

     int T;

     scanf("%d" , &T);

     while(T--)

     {

         memset(head , - , sizeof(head));

         k = ;

         scanf("%d" , &n);

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

             for(int j= ; j<n ; j++) scanf("%I64d" , &v[i][j]);

         }

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

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

                 insert(v[][i]+v[][j]);

         bool flag = false;

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

         {

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

             {

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

                 {

                     if(search(-v[][i]-v[][j]-v[][k])) flag=true;

                 }

                 if(flag) break;

             }

             if(flag) break;

         }

         printf("%s\n" , (flag?"Yes":"No"));

     }

     return ;

 }

巴特西

HDU 4334 5-sum

最新文章

热门文章