題意：

兩個數(shù)列，每個數(shù)列都可以順序旋轉，也可以對所有數(shù)同時增加一個非負整數(shù)，現(xiàn)在問
的最小值

題解：

在求卷積前要將A數(shù)組倍長，B數(shù)組翻轉
B數(shù)組翻轉好理解，為什么A數(shù)組倍長，因為題目的數(shù)列是可以移動的，而我們不知道哪一部分和B卷積是最佳答案，所以講A數(shù)組倍增，然后每次取A中連續(xù)長度為n的區(qū)間與B倍增，最后取最小值即為最佳答案
因為c是我們設的變量，所以最后循環(huán)c找式子最小值

關于FFT求卷積（多項式乘法）

如果有兩個無限序列a和b，那么它們卷積的結果是
如果a和b是有限序列，a最低的項為a0，最高的項為an，b同理，我們可以把a和b超出范圍的項都設置成0。

【模板】多項式乘法（FFT）

套上FFT的模板就可以

代碼：

#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int maxn=4e5+5; const double pi=3.1415926535898; int t, n, m, len=1, l, r[maxn*2]; int a[maxn],b[maxn]; struct Cpx{ //復數(shù)double x, y;Cpx (double t1=0, double t2=0){ x=t1, y=t2; } }A[maxn*2], B[maxn*2], C[maxn*2]; Cpx operator +(Cpx a, Cpx b){ return Cpx(a.x+b.x, a.y+b.y); } Cpx operator -(Cpx a, Cpx b){ return Cpx(a.x-b.x, a.y-b.y); } Cpx operator *(Cpx a, Cpx b){ return Cpx(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x); }void fdft(Cpx *a, int n, int flag){ //快速將當前多項式從系數(shù)表達轉換為點值表達for (int i=0; i<n; ++i) if (i<r[i]) swap(a[i], a[r[i]]);for (int mid=1; mid<n; mid<<=1){ //當前區(qū)間長度的一半Cpx w1(cos(pi/mid), flag*sin(pi/mid)), x, y;for (int j=0; j<n; j+=(mid<<1)){ //j:區(qū)間起始點Cpx w(1, 0);for (int k=0; k<mid; ++k, w=w*w1){ //系數(shù)轉點值x=a[j+k], y=w*a[j+mid+k];a[j+k]=x+y; a[j+mid+k]=x-y;}}} }inline int getint(int &x){char c; int flag=0;for (c=getchar(); !isdigit(c); c=getchar())if (c=='-') flag=1;for (x=c-48; c=getchar(), isdigit(c);)x=(x<<3)+(x<<1)+c-48;return flag?x:-x; }int main(){getint(n); getint(m); int x;int m1=m;m=n;ll A1=0,A2=0,B1=0,B2=0;for (int i=1; i<=n; ++i) {getint(x);A[i].x=x;A[i+n].x=x;A1+=A[i].x*A[i].x;A2+=A[i].x;} // cout<<A1<<" "<<A2<<endl;for (int i=1; i<=m; ++i) {getint(x);B[i].x=x;B1+=B[i].x*B[i].x;B2+=B[i].x;b[i]=B[i].x;} // cout<<B1<<" "<<B2<<endl;for(int i=1;i<=n;i++){B[i].x=b[n-i+1];}ll sum=1e15;while (len<=n+n+m) len<<=1, ++l; //idft需要至少l1+l2個點值for (int i=0; i<len; ++i) //編號的字節(jié)長度為lr[i]=(r[i>>1]>>1)|((i&1)<<(l-1));fdft(A, len, 1); fdft(B, len, 1);for (int i=0; i<=len; ++i) C[i]=A[i]*B[i];fdft(C, len, -1); //idftfor (int i=0; i<=len; ++i)C[i].x=int(C[i].x/len+0.5);for(int i=1;i<=n;i++){for(int j=-m1;j<=m1;j++){sum=min(A1+B1+2ll*j*A2-2ll*j*B2+n*j*j-2ll*(ll)C[i+n].x,sum);// cout<<"sum="<<-2ll*(ll)A[i+n].x<<endl;}}cout<<sum;return 0; }

總結

以上是生活随笔為你收集整理的[AH2017/HNOI2017]礼物的全部內容，希望文章能夠幫你解決所遇到的問題。

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