题意:四列,每列找一个数,得到和为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;
}
分类: 二分答案

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注