POJ2785 4 Values whose Sum is 0

作者: MayFlyyh 分类: 二分答案 发布时间: 2018-07-16 14:39 ė 6 没有评论

题意:四列,每列找一个数,得到和为0的序列,有几种不同的方案

一开始想的是dfs。。。后来想的是前两列两两组合将和放入多重集multiset里然后后两列每次查询一下就可以,但还是T了。

原来是把前两列两两组合,后两列两两组合然后每次查询就可以。

看来是set常数太大了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
int n,ans;
int x[5000][5];
int min[6],max[6];
int a[5000*5000],b[5000*5000];
int ca,cb;
std::multiset<int> s;
int main (){ 
    //freopen("my.txt","w",stdout);
    memset(min,0x3f,sizeof(min));
    memset(max,-0x3f,sizeof(max));
    max[5]=0x3f3f3f3f;
    min[5]=-0x3f3f3f3f;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=4;++j){
            scanf("%d",&x[i][j]);
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            a[++ca]=x[i][1]+x[j][2];
        }
    }
    std::sort(a+1,a+1+ca);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            b[++cb]=x[i][3]+x[j][4];
            int sum=b[cb];
            ans+=std::upper_bound(a+1,a+1+ca,-sum)-std::lower_bound(a+1,a+1+ca,-sum);
        }
    }
    printf("%d\n",ans); 
    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/293

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部