多校4题目之Trouble

Trouble

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1870 Accepted Submission(s): 588

Problem Description

Hassan is in trouble. His mathematics teacher has given him a very difficult problem called 5-sum. Please help him.
The 5-sum problem is defined as follows: Given 5 sets S_1,...,S_5 of n integer numbers each, is there a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0?

Input

First line of input contains a single integer N (1≤N≤50). N test-cases follow. First line of each test-case contains a single integer n (1<=n<=200). 5 lines follow each containing n integer numbers in range [-10^15, 1 0^15]. I-th line denotes set S_i for 1<=i<=5.

Output

For each test-case output "Yes" (without quotes) if there are a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0, otherwise output "No".

Sample Input

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

Sample Output

No Yes

Source

2012 Multi-University Training Contest 4

Recommend

zhoujiaqi2010

这道题目确实比较坑爹用set写了个代码现在还是TLE 时间卡得好死开始以为是Dp 而且我DP也不熟练

写了很久算了一下时间复杂度应该能卡过去不知道为什么却一直还是TLE

纠结了差不多三个小时

其他的题目又不会做总的来说还是能力的问题吧我们这只队伍还是得全部提高我也得提高呵呵

题目意思：

给你五个序列要你在每一个序列用找一个数如果存在和为0的情况就输出Yes 否则输出No 总共用120*10^6*log已经超过10^8 所以超时了后来才算出来

害得我纠结了很久

解题报告是说开始用两个数组sum把分别计算s1+s2的和s3+s4的和

排序后用指针下标i 指向sum1的开头用指针下标J 指向sum2的结尾如果

sum1+sum2+s[4][k]<0 i++

>0 j--

=0 直接跳出循环说明已经找到了

View Code

 1 #include <iostream>
 2 #include <set>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 __int64 a[5][205];
 7 __int64 b[2][40001];
 8 
 9 int main()
10 {
11     int T;
12     scanf("%d",&T);
13     while (T--)
14     {
15         int i,j;
16         int n,k=0;
17         scanf("%d",&n);
18         for (i=0;i<5;i++)        
19             for (j=0;j<n;j++)            
20                 scanf("%I64d",&a[i][j]);                
21             sort(a[4],a[4]+n);
22             int f=0;
23             for (i=0;i<n;i++)        
24                 for (j=0;j<n;j++)                                        
25                     b[0][f++]=a[0][i]+a[1][j];            
26                 for (i=0;i<n;i++)        
27                     for (j=0;j<n;j++)                                        
28                         b[1][k++]=(a[2][i]+a[3][j]);    
29                     sort(b[0],b[0]+f);
30                     sort(b[1],b[1]+k);
31                     int p;    
32                     bool flag=0;                
33                         for (i=0;i<n;i++)
34                         {
35                             for (j=k-1,p=0;j>=0&&p<f;)
36                         {
37                             if (a[4][i]+b[1][j]+b[0][p]>0)                                    
38                                 j--;                                    
39                             else 
40                                 if (a[4][i]+b[1][j]+b[0][p]<0)
41                                     p++;
42                                 else 
43                                 {
44                                     flag=1;
45                                     break;
46                                 }                                        
47                         }
48                     }
49                     if (flag)                        
50                         printf("Yes\n");                        
51                     else printf("No\n");                    
52     }
53     return 0;
54 }