编程介的小学生 2017-11-18 00:47 采纳率: 20.5%
浏览 578
已结题

Trouble

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

  • 写回答

1条回答 默认 最新

  • 银河曼巴 2018-07-23 13:56
    关注

    给定五个集合,每个集合有n个数,从每个集合各取一个数使和为0。如果能输出Yes,不能则输出No。

        看了网上的题解有很多解法,个人感觉这题暴力就能过。

        首先将一二两个集合合并为数组a,再将三四两个集合合并数组b,然后进行从小到大排序,

        设第五个数组为数组c,依次遍历c中的每一个数,看在a,b中是否存在两个数的和与c中的数的和为0,

        将数组a,b进行sort排序,然后一个正序即从小到大遍历,一个逆序从大到小遍历,

        如果三个数的和小于0,a数组后移一位,否则b后移一位。

        这题WA了两次,第一次WA后发现else if用的是三个i,忘了改成i,j,k了。

        第二次WA后发现Yes输出成了YES,No输出成了NO。

    #include
    #include
    #include
    #include
    using namespace std;
    long long a[40005],b[40005],c[205],d[205],e[205],f[205],g[205];
    long long i,j,x,k,l,n,t,flag=0,p;
    int main()
    {
    scanf("%lld",&t);
    while(t--)
    {
    flag=0;
    //输入
    scanf("%lld",&n);
    for(i=0;i scanf("%lld",&d[i]);
    for(i=0;i scanf("%lld",&e[i]);
    for(i=0;i scanf("%lld",&f[i]);
    for(i=0;i scanf("%lld",&g[i]);
    for(i=0;i scanf("%lld",&c[i]);
    //合并
    int cnt1=0;
    for(i=0;i for(j=0;j a[cnt1++]=d[i]+e[j];
    int cnt2=0;
    for(i=0;i for(j=0;j b[cnt2++]=f[i]+g[j]; //三四合并
    sort(a,a+cnt1);
    sort(b,b+cnt2);
    //计算
    for(i=0;i {
    j=0;
    k=cnt2-1;
    while(j=0)
    {
    if(a[j]+b[k]+c[i]==0LL)
    {
    flag=1;
    break;
    }
    else if(a[j]+b[k]+c[i]<0)
    j++;
    else
    k--;
    }

        }
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
    

    }

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题