H-Hash Function

Shining_xzl大佬題解

本題答案符合題意的充分必要條件是：不能是任意兩個(gè)數(shù)的差以及他們的因數(shù)，因此只需用用FFT求出這些數(shù)的差，記為差的集合。

從小到大考慮一個(gè)答案，以及答案的倍數(shù)是不是上述差的集合，不是則符合。

#include<bits/stdc++.h>using namespace std; using ll=long long;const int maxn=(1<<20)+5; const double PI=acos(-1); struct Complex {double x,y;Complex operator+(const Complex &o) const{return{x+o.x,y+o.y};} Complex operator-(const Complex &o) const{return{x-o.x,y-o.y};} Complex operator*(const Complex &o) const{return{x*o.x-y*o.y,x*o.y+y*o.x};} }A[maxn],B[maxn]; int rev[maxn]; void FFT(Complex *a,int N,int inv) {for(int i=0;i<N;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);for(int mid=1;mid<N;mid<<=1){Complex Wn=Complex({cos(PI/mid),inv*sin(PI/mid)});for(int i=0;i<N;i+=mid*2){Complex w=Complex({1,0});for(int j=0;j<mid;j++,w=w*Wn){Complex x=a[i+j],y=w*a[i+j+mid];a[i+j]=x+y,a[i+j+mid]=x-y;}}}if(inv==-1) for(int i=0;i<N;i++) A[i].x/=N; } // --------FFTint n; const int Bs=500000;int vis[maxn];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++){int a;cin>>a;A[a].x=1;B[Bs-a].x=1;}int num=1<<20,bit=20;for(int i=1;i<num;i++) rev[i]=rev[i>>1]>>1|(i&1)<<(bit-1); FFT(A,num,1),FFT(B,num,1);for(int i=0;i<num;i++) A[i]=A[i]*B[i];FFT(A,num,-1);for(int i=0;i<=Bs;i++) vis[i]=int(A[i+Bs].x+0.5);for(int i=n;;i++){bool ok=1;for(int j=i;j<=Bs;j+=i)if(vis[j]) {ok=0;break;}if(ok) return cout<<i<<'\n',0;}return 0; }

暴力_鏈表維護(hù)差值

鏈表維護(hù)差值，如果差值不存在，則O(1)刪除，非常快，但是后續(xù)被出題人卡了~~

#include<bits/stdc++.h>using namespace std; using ll=long long;const int N=(1<<20)+5;int fr[N],to[N];void del(int x){to[fr[x]]=to[x];fr[to[x]]=fr[x];}int n,a[N]; int no[N],vis[N],mx; int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);to[0]=1,fr[500001]=-1;for(int i=1;i<=500000;i++) fr[i]=i-1,to[i]=i+1;cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];vis[a[i]]=1;mx=max(mx,a[i]);}for(int i=1;i<=n;i++)for(int j=to[0];j!=-1&&a[i]+j<=mx;j=to[j])if(vis[a[i]+j]) {del(j);no[j]=1;}for(int i=n;;i++){bool ok=1;for(int j=i;j<=mx;j+=i) if(no[j]){ok=0;break;}if(ok) return cout<<i<<'\n',0;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021牛客暑期多校训练营1 H-Hash Function（数学+FFT）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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