正題

---

大意

一個序列A，求滿足

An+Am+Ap=Ai(n,m,p<i)An+Am+Ap=Ai(n,m,p<i)
這個要求的 AiAi的個數(shù)

---

解題思路

我們先移一個項

An+Am=Ai?ApAn+Am=Ai?Ap
然后用hash表儲存 An+AmAn+Am的所有答案，然后到達(dá)一個數(shù)的時候枚舉 pp就可以O(n2)O(n2)求出答案
玄學(xué)的是map庫只有40，這個故事告訴我們不要偷懶

---

代碼

#include<cstdio> #include<algorithm> #define maxn 25000004 using namespace std; int n,s,hash[maxn+10],a[5001]; bool v[maxn+10]; int hashmath(int x) {return (x%maxn+maxn)%maxn;} int locate(int x)//查找位置 {int i=0,w=hashmath(x);while (i<maxn&&v[(w+i)%maxn]&&hash[(w+i)%maxn]!=x)i++;return (w+i)%maxn; } void ins(int x)//插入 {int w=locate(x);hash[w]=x;v[w]=true; } bool find(int x)//查找 {int w=locate(x);if (hash[w]==x&&v[w]) return true;else return false; } int main() {//freopen("good.in","r",stdin);//freopen("good.out","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i]);for (int j=1;j<=i;j++){if (i!=j&&find(a[i]-a[j]))//查找{s++;//統(tǒng)計答案break;//退出循環(huán)}}for (int j=1;j<=i;j++)ins(a[i]+a[j]);//加入新的答案}printf("%d",s); }

總結(jié)

以上是生活随笔為你收集整理的jzoj3508-好元素【hash,优雅的暴力】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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