题意:四列,每列找一个数,得到和为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 条评论