LG 3723 [AH2017/HNOI2017]礼物
前言
感觉这道 FFT 挺水的（（（
我这种蒟蒻都能做出来，一遍写对。估计这个题是真的有点简单了
解法
我们其实很快可以观察出一个性质：
性质1
对于增加的亮度 \(c\)，可以小于 \(0\)。
这个太好理解了吧，就是不增加这一串的亮度，去增加另一串，不就相当于减小这一串的亮度吗？（挺绕的qwq）
性质2
对于增加的亮度 \(c\)，一定满足 \(-m\leq c\leq m\)。
自证不难。
这个也很容易证明。我们可以想，如果 \(|c|>m\)，由于 \(\forall i\ \ a_i\leq m,b_i\leq m\)，那么此时 \(c\) 一定不是最优的。
我们开始推柿子。
由性质1，我们知道：
\[ans=\min\limits_{x=-m}^m \sum\limits_{i=1}^n(a_i-b_i+x)^2
\]
展开得：
\[ans=\min\limits_{x=-m}^m \sum\limits_{i=1}^n({a_i}^2+{b_i}^2-2\cdot a_i\cdot b_i+2\cdot a_i\cdot x-2\cdot x\cdot b_i+x^2)
\]
略加整理得：
\[ans=\min\limits_{x=-m}^m \sum\limits_{i=1}^n({a_i}^2+{b_i}^2)+2\cdot x\cdot\sum\limits_{i=1}^n (a_i-b_i)+n\cdot x^2+2\cdot\sum\limits_{i=1}^n a_i\cdot b_i
\]
如果我们枚举 \(x\)，那么就只有 \(2\cdot\sum\limits_{i=1}^n a_i\cdot b_i\) 这一项是变量了，我们应该使这个部分的值最大。
这不就是经典的翻转数组 FFT 吗？我们翻转数组 \(a\)，这样这个部分就变为了 \(2\cdot\sum\limits_{i=1}^n a_{n-i+1}\cdot b_i\)。用 FFT 求两个多项式的积，然后看多项式 \(n+1\) 到 \(2\cdot n\) 次项的系数，取最大值即可。最后在 \(-m\) 到 \(m\) 的区间里枚举 \(x\) 即可。时间复杂度 \(O(n\log n+n+2\cdot m)\)
如果你想优化亿点点时间复杂度，你可以用三分法去锁定 \(x\)，把时间复杂度最后一项降低。
或者你可以利用二次函数的性质，把式子想象成一个关于 \(x\) 的二次函数，利用对称轴求最值即可。
但是你没必要在简单问题上耍杂技。除非在女同学面前qwq
代码
//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int MAXN=1e6+10;
const double pi=acos(-1.0);
typedef complex<double> Complex;
int n,m,d,cost,coft;//constant,coefficient
int a[MAXN],b[MAXN],r[MAXN];
Complex f[MAXN],g[MAXN];
void FFT(Complex A[],int inv) {
for(int i=0;i<d;i++) {
if(i<r[i]) {
swap(A[i],A[r[i]]);
}
}
for(int len=1;len<d;len<<=1) {
Complex wn=Complex(cos(pi/len),inv*sin(pi/len));
for(int i=0;i<d;i+=len*2) {
Complex w(1,0);
for(int k=0;k<len;k++,w*=wn) {
Complex x=A[i+k];
Complex y=w*A[i+k+len];
A[i+k]=x+y;
A[i+k+len]=x-y;
}
}
}
if(inv==-1) {
for(int i=0;i<d;i++) {
A[i]/=d;
}
}
}
signed main() {
cin>>n>>m;
for(int i=0;i<n;i++) {
a[i]=read();
cost+=a[i]*a[i];
f[i]=a[i];
}
for(int i=0;i<n;i++) {
b[i]=read();
cost+=b[i]*b[i];
coft+=a[i]-b[i];
g[i]=b[i];
}
reverse(f,f+n);
for(int i=n;i<2*n;i++) {
f[i]=f[i-n];
}
d=1;
int l=0;
while(d<3*n) {
d<<=1;
l++;
}
for(int i=0;i<d;i++) {
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
FFT(f,1);
FFT(g,1);
for(int i=0;i<d;i++) {
f[i]=f[i]*g[i];
}
FFT(f,-1);
int maxx=-1;
for(int i=n;i<n*2;i++) {
maxx=max(maxx,(int)(f[i].real()+0.49)*2);
}
int ans=1e18;
cost-=maxx;
for(int x=-m;x<=m;x++) {
ans=min(ans,cost+n*x*x+2*x*coft);
}
cout<<ans<<endl;
return 0;
}