给出四个长度为n的数列a,b,c,d,求从这四个数列中每个选取一个元素后的和为0的方法数。n<=4000,abs(val)<=2^28.

考虑直接暴力,复杂度O(n^4).显然超时。

# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int res=, flag=;
char ch;
if((ch=getchar())=='-') flag=;
else if(ch>=''&&ch<='') res=ch-'';
while((ch=getchar())>=''&&ch<='') res=res*+(ch-'');
return flag?-res:res;
}
void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
const int N=;
//Code begin... int a[N], b[N], c[N], d[N];
VI vis; int main ()
{
int n;
LL ans=;
n=Scan();
FOR(i,,n) a[i]=Scan(), b[i]=Scan(), c[i]=Scan(), d[i]=Scan();
FOR(i,,n) FOR(j,,n) vis.pb(-c[i]-d[j]);
sort(vis.begin(),vis.end());
FOR(i,,n) FOR(j,,n) {
int temp=a[i]+b[j];
ans+=upper_bound(vis.begin(),vis.end(),temp)-lower_bound(vis.begin(),vis.end(),temp);
}
printf("%lld\n",ans);
return ;
}

枚举a,二分b+c+d.复杂度O(n+n^3*log(n^3)+n*log(n^3))~O(n^3*logn).

枚举a+b,二分b+c.复杂度O(n^2+n^2*log(n^2)+n^2*log(n^2))~O(n^2*logn).

枚举a+b+c,二分d.复杂度O(n^3+logn+n^3*logn)~O(n^3*logn).

另外此题map常数大过不了。

最新文章

  1. 5.2 Array类型的方法汇总
  2. UNIX系统基本结构
  3. windows脚本配置ip地址
  4. JS控制图片显示的大小(图片等比例缩放)
  5. yii2接收activeform表单信息
  6. 10.11 安装pod
  7. Firefox SVG getBBox方法返回&#39;NS_ERROR_FAILURE&#39;错误分析
  8. task mysqld:26208 blocked for more than 120 seconds
  9. maven仓库私服配置
  10. centos 6安装redis 2.8.19
  11. Python状况:为什么PyPy是Python的未来?
  12. [html]HTML &lt;form&gt; 标签的 enctype 属性
  13. Linux/U-Boot Git Repo
  14. mysql修改root密码的方法
  15. 虚拟机LUN扩大后,重新分区
  16. hdu--1800--字典树&amp;&amp;其他
  17. Sql Server之旅——第五站 确实不得不说的DBCC命令
  18. html与xhtml有什么区别?
  19. Django DetailView 多重继承 关系整理
  20. .NET 开源项目 Anet 介绍

热门文章

  1. 武汉Uber优步司机奖励政策(8月31日~9月6日)
  2. 基于Redis+Kafka的首页曝光过滤方案
  3. 2019年猪年海报PSD模板-第二部分
  4. Object里面的方法
  5. 如何理解一台服务器可以绑定多个ip,一个ip可以绑定多个域名
  6. PyCharm 2018 最新激活方式总结(最新最全最有效)!!!
  7. C#使用EF连接PGSql数据库
  8. Java算法2
  9. Tensorflow中使用tfrecord方式读取数据-深度学习-周振洋
  10. Python高级编程-使用SQLite