生活随笔
收集整理的這篇文章主要介紹了
P3723 [AH2017/HNOI2017]礼物 FFT + 式子化简
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
傳送門
文章目錄
題意：
思路：
首先可以知道，我們對(duì)某個(gè)數(shù)組加上一個(gè)正數(shù)數(shù)的操作可以轉(zhuǎn)換成對(duì)一個(gè)數(shù)組加上一個(gè)任意數(shù)，所以我們?cè)O(shè)變化量為xxx。
對(duì)于∑i=1n(ai?bi)2\sum_{i=1}^n(a_i-b_i)^2i=1∑n?(ai??bi?)2我們將變化量加入變成∑i=1n(ai?bi?x)2\sum_{i=1}^n(a_i-b_i-x)^2i=1∑n?(ai??bi??x)2考慮大力展開這個(gè)式子變成∑i=1n(ai2+bi2)+nx2+2x∑i=1n(bi?ai)?2∑i=1naibi\sum_{i=1}^n(a_i^2+b_i^2)+nx^2+2x\sum_{i=1}^n(b_i-a_i)-2\sum_{i=1}^na_ib_ii=1∑n?(ai2?+bi2?)+nx2+2xi=1∑n?(bi??ai?)?2i=1∑n?ai?bi?
可以發(fā)現(xiàn)，對(duì)于前部分就是一個(gè)關(guān)于xxx的二次函數(shù)，比較容易處理最值的問題，問題就轉(zhuǎn)換成了∑i=1naibi\sum_{i=1}^na_ib_i∑i=1n?ai?bi?什么時(shí)候最大了。
對(duì)于這個(gè)問題，考慮其很像卷積的形式，所以套路的將aaa翻轉(zhuǎn)，變成∑i=1nan?i+1bi\sum_{i=1}^na_{n-i+1}b_i∑i=1n?an?i+1?bi?，由于我們旋轉(zhuǎn)任意一個(gè)數(shù)組都是等價(jià)的，這里選擇旋轉(zhuǎn)bbb數(shù)組，我們破環(huán)成鏈，將bbb擴(kuò)展為[1,2n][1,2n][1,2n]，此時(shí)設(shè)fn+1+k=∑i=1nan?i+1bk+if_{n+1+k}=\sum_{i=1}^na_{n-i+1}b_{k+i}fn+1+k?=∑i=1n?an?i+1?bk+i?，所以我們直接卷起來，讓后取[n+1,2n][n+1,2n][n+1,2n]的最大值即可，最后加上前部分的最小值就是答案啦。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
;
int a
[N
],b
[N
];struct FFT {double PI
=acos(-1);int rev
[N
];int bit
,limit
;struct Complex {double x
,y
;void init() { x
=y
=0; }Complex
operator + (const Complex
& t
) const { return {x
+t
.x
,y
+t
.y
}; }Complex
operator - (const Complex
& t
) const { return {x
-t
.x
,y
-t
.y
}; }Complex
operator * (const Complex
& t
) const { return {x
*t
.x
-y
*t
.y
,x
*t
.y
+y
*t
.x
}; } }a
[N
];void init(int n
,int m
) {int x
=max(n
,m
)*2; bit
=0;while((1<<bit
)<=x
) bit
++;limit
=1<<bit
;for(int i
=0;i
<limit
;i
++) rev
[i
]=(rev
[i
>>1]>>1)|((i
&1)<<(bit
-1));}void fft(Complex a
[],int inv
) {for(int i
=0;i
<limit
;i
++) if(i
<rev
[i
]) swap(a
[i
],a
[rev
[i
]]);for(int mid
=1;mid
<limit
;mid
<<=1) {Complex w1
=Complex({cos(PI
/mid
),inv
*sin(PI
/mid
)});for(int i
=0;i
<limit
;i
+=mid
*2) {Complex wk
=Complex({1,0});for(int j
=0;j
<mid
;j
++,wk
=wk
*w1
) {Complex x
=a
[i
+j
],y
=wk
*a
[i
+j
+mid
];a
[i
+j
]=x
+y
; a
[i
+j
+mid
]=x
-y
;}}}if(inv
==-1) {for(int i
=0;i
<=limit
;i
++) {a
[i
].x
/=limit
;a
[i
].y
/=limit
;}}}int solve(int *ans
,int *x
,int n
,int *y
,int m
) {for(int i
=0;i
<=n
;i
++) a
[i
].x
=x
[i
];for(int i
=0;i
<=m
;i
++) a
[i
].y
=y
[i
];init(n
,m
); fft(a
,1); for(int i
=0;i
<limit
;i
++) a
[i
]=a
[i
]*a
[i
];fft(a
,-1);for(int i
=0;i
<=n
+m
;i
++) ans
[i
]=(int)(a
[i
].y
/2+0.5);for(int i
=0;i
<limit
;i
++) a
[i
].init();return n
+m
;}}FT
;int main()
{
scanf("%d%d",&n
,&m
);int sum1
=0,sum2
=0;for(int i
=1;i
<=n
;i
++) scanf("%d",&a
[i
]),sum1
+=a
[i
]*a
[i
],sum2
-=a
[i
];for(int i
=1;i
<=n
;i
++) scanf("%d",&b
[i
]),b
[i
+n
]=b
[i
],sum1
+=b
[i
]*b
[i
],sum2
+=b
[i
];reverse(a
+1,a
+1+n
);int len
=FT
.solve(a
,a
,n
,b
,2*n
);int mx
=0;for(int i
=n
+1;i
<=n
*2+1;i
++) mx
=max(mx
,a
[i
]);int ans
=INF
;for(int i
=-m
*2;i
<=m
*2;i
++) ans
=min(ans
,sum1
+n
*i
*i
+2*i
*sum2
-2*mx
);cout
<<ans
<<endl
;return 0;
}
總結(jié)
以上是生活随笔為你收集整理的P3723 [AH2017/HNOI2017]礼物 FFT + 式子化简的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
