首页 > 代码库 > P2421 A-B数对（增强版）
P2421 A-B数对（增强版）
题目背景
woshiren在洛谷刷题，感觉第一题：求两数的和(A+B Problem)太无聊了，于是增加了一题：A-B Problem，难倒了一群小朋友，哈哈。
题目描述
给出N 个从小到大排好序的整数，一个差值C，要求在这N个整数中找两个数A 和B，使得A-B=C，问这样的方案有多少种？
例如：N=5，C=2，5 个整数是：2 2 4 8 10。答案是3。具体方案：第3 个数减第1 个数；第3 个数减第2 个数；第5 个数减第4 个数。
输入输出格式
输入格式：
第一行2 个正整数：N,C。
第二行N 个整数：已经有序。注意：可能有相同的。
输出格式：
一个整数，表示该串数中包含的所有满足A-B=C 的数对的方案数。
输入输出样例
输入样例#1：
4 11 1 2 2
输出样例#1：
4
说明
对于50% 的数据：N 的范围是[1…1,000]。
对于另外50% 的数据：N 的范围是[1…100,000]。
对于100% 的数据：C 的范围是[1…1,000,000,000]，N 个整数中每个数的范围是：[0…1,000,000,000]。
代码和未加强的一样
屠龙宝刀点击就送
#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#define in long long#define mo 20047#define mo2 13831using namespace std;struct node{ in cs; in next; in to;}edge[2000001];in ans,tot,head[2000001],a[200001],i,j,n,c,b;in qr(){ in x=1,f=0; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) x=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { f=f*10+(in)ch-48; ch=getchar(); } return x*f;}in get_hash1(in k){ return k*1007%mo;}in get_hash2(in q){ return q*1009%mo2;}void lj(in from,in to){ for(int l=head[from];l;l=edge[l].next) { if(edge[l].to==to) { edge[l].cs++; return; } } tot++; edge[tot].next=head[from]; edge[tot].to=to; head[from]=tot; edge[tot].cs++;}void add(in u,in v){ if(head[u]) lj(u,v); else { tot++; edge[tot].next=head[u]; edge[tot].to=v; head[u]=tot; edge[tot].cs++; }}int query(in u,in v){ for(j=head[u];j;j=edge[j].next) { if(edge[j].to==v) return edge[j].cs; } return 0;}int main(){ n=qr();c=qr(); for(i=0;i<n;++i) { a[i]=qr(); in x=get_hash1(a[i]); in y=get_hash2(a[i]); add(x,y); } for(i=0;i<n;++i) { b=c+a[i]; in y=get_hash1(b); in z=get_hash2(b); ans+=query(y,z); } cout<<ans; return 0;}
P2421 A-B数对（增强版）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。