优秀的设计网站,青岛网站设计企业,完整开发网站需要什么,宁波人流哪家医院好题意很好理解#xff0c;就是从四个集合里面取出四个数字的和为0#xff0c;问有多少种取法。
直接枚举肯定是会超时的#xff0c;所以得想办法优化一下。我们可以将两个集合的所有的和都放在一个数组里面#xff0c;这样得到两个数组#xff0c;然后排序#xff0c;对第…题意很好理解就是从四个集合里面取出四个数字的和为0问有多少种取法。
直接枚举肯定是会超时的所以得想办法优化一下。我们可以将两个集合的所有的和都放在一个数组里面这样得到两个数组然后排序对第一个数组中的每一个数据在第二个数组中用lower_bound 和upper_bound查找计数。
有了思路不是很难写重要的还是这种将可能的结果映射在数组上然后进行二分的思想。书上说的是把其中两个集合的和放在数组里面然后枚举一个集合在剩下的那个集合里面查找也可以的欸。
还有就是数据之间要有换行
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN4e35;
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
int s1[MAXN*MAXN];
int s2[MAXN*MAXN];
int n;int first1;ll ans;int main()
{int T;scanf(%d,T);while(T--){scanf(%d,n);for(int i0;in;i){scanf(%d%d%d%d,a[i],b[i],c[i],d[i]);}for(int i0;in;i){for(int j0;jn;j){s1[i*nj]a[i]b[j];}}for(int i0;in;i){for(int j0;jn;j){s2[i*nj]-c[i]-d[j];}}sort(s1,s1n*n);sort(s2,s2n*n);ans0;int tmp;for(int i0,limitn*n;ilimit;i){int ji;while(s1[j1]s1[i]) j;tmpupper_bound(s2,s2n*n,s1[i])-lower_bound(s2,s2n*n,s1[i]);ans(ll)tmp*(j-i1);ij;}if(first) first0;else printf(\n);printf(%lld\n,ans);}return 0;
}
