首页 > 代码库 > 数对的个数(cogs610)

数对的个数(cogs610)

2024-08-21 14:39:20   220人阅读

Description
出题是一件痛苦的事情！
题目看多了也有审美疲劳,于是我舍弃了大家所熟悉的A+B Problem,改用A-B了哈哈！

 

好吧，题目是这样的：给出一串数以及一个数字C，要求计算出所有A-B=C的数对的个数。

（不同位置的数字一样的数对算不同的数对）
Input Format
第一行包括2个非负整数N和C，中间用空格隔开。
第二行有N个整数，中间用空格隔开，作为要求处理的那串数。
Output Format
输出一行，表示该串数中包含的所有满足A-B=C的数对的个数。
Sample Input
4 1
1 1 2 3
Sample Output
3
Data Limit
对于90%的数据，N <= 2000；
对于100%的数据，N <= 200000。
所有输入数据都在longint范围内。

/*简单hash*/
#include<cstdio>
#include<iostream>
#define N 200010
#define mod 1654573
using namespace std;
int head[mod+10],a[N],n,C,ans,cnt;
struct node{
    int v,pre,sum;
};node e[N];
void add(int x,int y){
    for(int i=head[x];i;i=e[i].pre)
        if(e[i].v==y){
            e[i].sum++;return;
        }
    ++cnt;
    e[cnt].v=y;
    e[cnt].pre=head[x];
    e[cnt].sum++;
    head[x]=cnt;
}
int query(int x,int y){
    for(int i=head[x];i;i=e[i].v)
        if(e[i].v==y){
            return e[i].sum;
        }
    return 0;
}
void out(long long x){
    if(x<0)x=-x,putchar(‘-‘);
    if(x>9)out(x/10);
    putchar(x%10+‘0‘);
}
int main(){
    //freopen("jh.in","r",stdin);
    freopen("dec.in","r",stdin);
    freopen("dec.out","w",stdout);
    scanf("%d%d",&n,&C);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]-C<0)continue;
        add((a[i]-C)%mod,a[i]-C);
    }
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans+=(long long)(query(a[i]%mod,a[i]));
    }
    out(ans);
    return 0;
}

 

数对的个数(cogs610)


联系
我们