用中途相遇法的思想来解题。分别枚举两边,和直接暴力枚举四个数组比可以降低时间复杂度。

这里用到一个很实用的技巧:

  求长度为n的有序数组a中的数k的个数num?

    num=upper_bound(a,a+n,k)-lower_bound(a,a+n,k);

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<cctype>
#include<sstream>
using namespace std;
#define INF 1000000000
#define eps 1e-8
#define pii pair<int,int>
#define LL long long int
#define maxn 4005
int T,n,A[maxn],B[maxn],C[maxn],D[maxn],sum[maxn*maxn];
int main()
{
//freopen("in8.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
}
int c=;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
sum[c++]=A[i]+B[j];
}
}
sort(sum,sum+c);
LL ans=;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
ans+=upper_bound(sum,sum+c,-C[i]-D[j])-lower_bound(sum,sum+c,-C[i]-D[j]);
//这一句是全篇的点睛之笔。
}
}
printf("%lld\n",ans);
if(T) printf("\n");
}
//fclose(stdin);
//fclose(stdout);
return ;
}

最新文章

  1. 分享公司DAO层数据库结果映射到对象的方法
  2. 基于webdriver的jmeter性能测试-Eclipse+Selenium+JUnit生成jar包
  3. XUtils3 的 环境搭建
  4. words in view Moqui resource code
  5. Function Scope
  6. Programs vs. processes
  7. SVG之初识
  8. Linux 命令 - killall: 通过进程名向进程发送信号
  9. 用Javascript进行HTML转义(分享)
  10. 打jar包的方法
  11. Android源代码同步脚本(增加设置线程参数)
  12. Memcached缓存
  13. scrapy爬取极客学院全部课程
  14. 原生js实现preAll和nextAll方法
  15. 20190326-HTML5标签、CSS的引用
  16. [Linux/Ubuntu] vi/vim 使用方法讲解
  17. WebStorm for Mac(Web 前端开发工具)破解版安装
  18. .NetCore 分页控件实现原理处理以及条件分页处理
  19. thinkphp3.2 session时间周期无效
  20. 【深度好文】多线程之WaitHandle--&gt;派生-》Mutex信号量构造

热门文章

  1. 【zabbix】zabbix忘记密码,重置密码
  2. 方阵行列式并行化计算(OpenMP,MPI),并计算加速比
  3. python常用模块——random模块
  4. Apache NiFi 开发 安装说明
  5. python调用php函数
  6. 字典树 trie树 学习
  7. [MVC学习日记]2014/12/01 初步认识MVC模型。
  8. $《第一行代码:Android》读书笔记——第9章 服务
  9. HashTable的使用,扑克牌发牌游戏
  10. Linux Shell基础 通配符