首页 > ACM题库 > HDU-杭电 > Hdu 1895 Sum Zero-二分[解题报告] C++
2013
12-23

Hdu 1895 Sum Zero-二分[解题报告] C++

Sum Zero

问题描述 :

There are 5 Integer Arrays and each of them contains no more than 300 integers whose value are between -100,000,000 and 100,000,000, You are to find how many such groups (i,j,k,l,m) can make A[0][i]+A[1][j]+A[2][k]+A[3][l]+A[4][m]=0. Maybe the result is too large, you only need tell me the remainder after divided by 1000000007.

输入:

In the first line, there is an Integer T(0<T<20), means the test cases in the input file, then followed by T test cases.
For each test case, there are 5 lines Integers, In each line, the first one is the number of integers in its array.

输出:

For each test case, just output the result, followed by a newline character.

样例输入:

1
3 4 -2 3
5 -5 -1 -7 -10 -1
5 -10 2 4 -6 2
2 -4 -1
5 -7 -7 -1 -4 -6

样例输出:

11

/*hdu 1895  A[0][i]+A[1][j]+A[2][k]+A[3][l]+A[4][m]=0
一共5个数组,合并成2次,变成3个数组,这是空间是90000*90000*3000
对三个数组排序,用300*90000*log(90000),大家应该想到是二分查找吧*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#define MOD 1000000007
#define MAXN 305
using namespace std;
int a[5][MAXN], b[2][MAXN*MAXN];
int cmp( int p1, int p2 )
{
 return p1 < p2;
}
int Find( int x, int c[] )
{
 int l = 1, r = c[0], mid;
 while ( l <= r )
 {
  mid = ( l + r ) >> 1;
  if( x > c[r] || x < c[l] )
  {
   return 0;
  }
  if( c[mid] == x )
  {
   int sum = 1;
   for( l = mid - 1; l >= 0 && c[l] == x; l--, sum++ );
   for( r = mid + 1; r <= c[0] && c[r] == x; r++, sum++ );
   return sum;
  }
  else if( x > c[mid] )
  {
   l = mid + 1;
  }
  else
  {
   r = mid - 1;
  }
 }
 return 0;
}
void Connect( int k1, int k2, int k3 )
{
 int i, j, len = 0;
 for( i = 1; i <= a[k1][0]; i++ )
 {
  for( j = 1; j <= a[k2][0]; j++ )
  {
   b[k3][++len] = a[k1][i] + a[k2][j];
  }
 }
 b[k3][0] = len;
}
void Solve( int c1[], int c2[], int c3[] )
{
 int i, j, num, sum = 0;
 sort( c1+1, c1+c1[0]+1, cmp );
 sort( c2+1, c2+c2[0]+1, cmp );
 sort( c3+1, c3+c3[0]+1, cmp );
 for( i = 1; i <= c1[0]; i++ )
 {
  for( j = 1; j <= c2[0]; j++ )
  {
   num = -( c1[i] + c2[j] );
   if( num < c3[1] || num > c3[c3[0]] )
   {
    continue;
   }
   sum += Find( num, c3 );
  }
 }
 printf("%d\n", sum);
}
int main()
{ 
 int cas;
 scanf("%d", &cas);
 while ( cas-- )
 {
  int i, j;
  for( i = 0; i < 5; i++ )
  {
   scanf("%d", &a[i][0]);
   for( j = 1; j <= a[i][0]; j++ )
   {
    scanf("%d", &a[i][j]);
   }
  }
  Connect( 0, 1, 0 );
  Connect( 2, 3, 1 );
  Solve( a[4], b[0], b[1] );
 }
 return 0;
}

 


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。