P2421 A-B数对（增强版）

蔚落 2021-12-12 13:59 158阅读 0赞

## 题目背景 ##

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 1
    1 1 2 2

输出样例\#1：

## 说明 ##

对于50% 的数据：N 的范围是\[1…1,000\]。

对于另外50% 的数据：N 的范围是\[1…100,000\]。

对于100% 的数据：C 的范围是\[1…1,000,000,000\]，N 个整数中每个数的范围是：\[0…1,000,000,000\]。

代码和未加强的一样

[屠龙宝刀点击就送][Link 1]

#include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #define in long long
    #define mo 20047
    #define mo2 13831
    using 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;
    }

转载于:https://www.cnblogs.com/ruojisun/p/6413583.html

[Link 1]: https://www.luogu.org/problem/show?pid=2421