POJ 2785 4 Values whose Sum is 0(哈希表)
2024-10-17 22:35:05
【题目链接】 http://poj.org/problem?id=2785
【题目大意】
给出四个数组,从每个数组中选出一个数,使得四个数相加为0,求方案数
【题解】
将a+b存入哈希表,反查-c-d
【代码】
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=4500,mod=1<<22;
int n,a[N],b[N],c[N],d[N],head[mod],cnt;
struct data{int x,nxt,s;}g[mod];
long long ans;
inline int hash(int x){return (x+mod)&(mod-1);}
void insert(int x){
int key=hash(x);
for(int i=head[key];i!=-1;i=g[i].nxt){
if(g[i].x==x){g[i].s++;return;}
}g[cnt].s=1; g[cnt].x=x;
g[cnt].nxt=head[key]; head[key]=cnt++;
}
int search(int x){
int key=hash(x);
for(int i=head[key];i!=-1;i=g[i].nxt){
if(g[i].x==x)return g[i].s;
}return 0;
}
void init(){cnt=0;memset(head,-1,sizeof(head));ans=0;}
int main(){
while(~scanf("%d",&n)){
init();
for(int i=0;i<n;i++)scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)insert(a[i]+b[j]);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)ans+=search(-c[i]-d[j]);
printf("%lld\n",ans);
}return 0;
}
最新文章
- Kafka 如何读取offset topic内容 (__consumer_offsets)
- PIC12F508/505/509/510/506/519/526/527单片机破解芯片解密方法!
- 4、python列表
- NodeJs解析web一例
- 还是要好好研究开源的php
- header
- cdr创建样式与样式集的方法
- (转)CentOS 6.5下Redis安装详细步骤
- gif压缩
- PCAP 文件内容解析命令
- 搜索提示時jquery的focusout和click事件沖突問題完美解决
- 钟表维修管理系统技术解析(一) MVC架构搭建
- MySQL数据库my.cnf配置文件注释详解
- Swift - 35 - 使用闭包简化语法
- C# 常用参数
- sqlserver跨数据库与跨服务器使用
- 使用VMware Workstation Pro 12 虚拟机安装Mac OS系统教程 全程图解
- hihocoder [Offer收割]编程练习赛52 D 部门聚会
- java HTTP请求工具
- CodeSmith如何生成实体类
热门文章
- dpkg.cfg
- ImportError: dynamic module does not define module export function (PyInit__caffe)
- Redis String
- Crash的游戏 [组合+递推]
- 全球顶尖的内容创作引擎,Unity为创造而生
- 真&#183;APIO2018滚粗记
- 51NOD 1554 欧姆诺姆和项链 巧妙利用KMP
- POJ 2406 Power Strings 暴力
- POJ 3177 Redundant Paths 无向图边双联通基础题
- linux设置永久别名