題目描述
出題是一件痛苦的事情！

題目看多了也有審美疲勞，于是我舍棄了大家所熟悉的A+BA+B ProblemProblem，改用A-BA?B了哈哈！

好吧，題目是這樣的：給出一串數(shù)以及一個數(shù)字CC，要求計算出所有A-B=C的數(shù)對的個數(shù)。（不同位置的數(shù)字一樣的數(shù)對算不同的數(shù)對）

輸入輸出格式
輸入格式：
第一行包括22個非負整數(shù)NN和CC，中間用空格隔開。

第二行有NN個整數(shù)，中間用空格隔開，作為要求處理的那串數(shù)。

輸出格式：
輸出一行，表示該串數(shù)中包含的所有滿足A-B=CA?B=C的數(shù)對的個數(shù)。

輸入輸出樣例
輸入樣例#1：
4 1
1 1 2 3
輸出樣例#1：
3
說明
對于73%的數(shù)據(jù)，N ≤ 2000;
對于100%的數(shù)據(jù)，N ≤200000。
所有輸入數(shù)據(jù)都在longint范圍內(nèi)。

.
.
.
.
.
.
分析
我用了哈希來做,數(shù)組開得夠大
注意：所有輸入數(shù)據(jù)都在longint范圍內(nèi)！
這說明int可能會爆，并且，它可能會有負數(shù)
所以哈希的做法要注意一下
.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long mo=1555553; long long h[1555553][2],a[1555553]; long long tj=0,ans=0;long long abs(long long x) {return x<0?-x:x; }int find(int x) {long long w=abs(x)%mo,i=0;while (i<mo&&h[(w+i)%mo][0]!=-1&&h[(w+i)%mo][0]!=x) i++;if (h[(w+i)%mo][0]==x) return (w+i)%mo; }inline int read(){int s=0,w=1;char ch=getchar();while(ch<='0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w; }void hash(int x) {long long w=abs(x)%mo,i=0;while (i<mo&&h[(w+i)%mo][0]!=-1&&h[(w+i)%mo][0]!=x) i++;if (h[(w+i)%mo][0]==-1){h[(w+i)%mo][0]=x;h[(w+i)%mo][1]++;tj++;a[tj]=x;} elseif (h[(w+i)%mo][0]==x) h[(w+i)%mo][1]++; }int main() {int n,c;n=read();c=read();memset(h,-1,sizeof(h));for (int i=1;i<=n;i++){long long w;w=read();hash(w);}sort(a+1,a+tj+1);for (int i=1;i<=tj;i++){int w=find(a[i]+c),z=find(a[i]);if (h[w][0]==a[i]+c&&h[z][0]==a[i]) ans=(long long)ans+(long long)(h[z][1]+1)*(long long)(h[w][1]+1); }printf("%lld",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10292791.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結(jié)

以上是生活随笔為你收集整理的A−B数对的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。