题目传送门
轻轻戳我
Solution
题目欲求
∑ni=1(xi+c−yi)2
的最小值。
先处理
+c
的问题，将式子展开
∑i=1n(xi+c−yi)2=∑i=1n(xi−yi)2+2∑i=1n(xi−yi)c+nc2
由于那些
x,y
什么的都是常量，于是我们得到了一个关于
c
的开口向上的二次函数，现在要求其极小值，学过初三数学的我直接O(1)算对称轴求出
c
。
然后 c的限制被去掉了。 原问题理所当然地变成了求
∑ni=1(xi−yi)2
的值。
∑i=1n(xi−yi)2=∑i=1nx2i+∑i=1ny2i−2∑i=1nxiyi
前面一堆常量，预处理搞出。最后那项把
y
数组翻转过来后，就是个裸的卷积，直接上FFT。
但由于可以旋转，所以其实要求的是循环卷积。
有一个普通的类似破环为链的作法：我们发现如果将
x
旋转，相当于将x倍长，
xi
变成
xi+j
。
于是：
∑i=1n(xi+j−yi)2=∑i=1nx2i+j+∑i=1ny2i−2∑i=1nxi+jyi
只用求最后那项，直接将
y
反过来，用FFT求卷积即可。
由于
m
挺小，其实也可以先FFT，再直接枚举
c
，计算出答案。
对于旋转的处理，还有一种神奇的方法：
把两个序列画出来，发现如果旋转一定位置的话，那么答案就是两个序列前i部分卷起来加上把剩下部分卷起来的和。
那么只要正着反着分别做一次
FFT
即可。(还是自己画个图容易懂一点。。)
Code
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#define MAXN 100010
#define oo 0x7fffffff
using namespace std;
const double PI =
acos(-
1.0);
int n, m, nn, X[MAXN], Y[MAXN], P[MAXN], sumX, sumY, sum, C, ans;
struct Complex{
double real, image;
Complex() {}
Complex(
double _real,
double _image){real = _real, image = _image;}
friend Complex
operator + (Complex A, Complex B){
return Complex(A.real + B.real, A.image + B.image);}
friend Complex
operator - (Complex A, Complex B){
return Complex(A.real - B.real, A.image - B.image);}
friend Complex
operator * (Complex A, Complex B){
return Complex(A.real * B.real - A.image * B.image, A.real * B.image + A.image * B.real);}
}a[MAXN<<
2], b[MAXN<<
2], c[MAXN<<
2];
void Get_P(){
for(
int i =
1, t =
1; i < MAXN; i++)
P[i] = (t < i) ? (t <<=
1) : t;
}
void Reverse(Complex *A){
for(
int i =
0; i < nn-
1; i++){
int j =
0;
for(
int k =
1, tmp = i; k < nn; k <<=
1, tmp >>=
1)
j = ((j <<
1) | (tmp &
1));
if(i < j) swap(A[i], A[j]);
}
}
void FFT(Complex *A,
int DFT){
Reverse(A);
for(
int s =
1; (
1<<s) <= nn; s++){
int m =
1 << s;
Complex wm = Complex(
cos(DFT*
2*PI/m),
sin(DFT*
2*PI/m));
for(
int k =
0; k < nn; k += m){
Complex w = Complex(
1,
0);
for(
int j =
0; j < (m>>
1); j++){
Complex u = A[k+j], t = w * A[k+j+(m>>
1)];
A[k+j] = u + t;
A[k+j+(m>>
1)] = u - t;
w = w * wm;
}
}
}
if(!(~DFT))
for(
int i =
0; i < nn; i++) A[i].real /= nn;
}
int main(){
freopen(
"bzoj4827.in",
"r", stdin);
freopen(
"bzoj4827.out",
"w", stdout);
Get_P();
scanf(
"%d%d", &n, &m);
nn = P[n<<
1] <<
1;
for(
int i =
0; i < n; i++)
scanf(
"%d", &X[i]), sumX += X[i];
for(
int i =
0; i < n; i++)
scanf(
"%d", &Y[i]), sumY += Y[i];
C = (sumY - sumX) / n;
int Val1 = n * C * C +
2 * (sumX - sumY) * C;
int Val2 = n * (C+
1) * (C+
1) +
2 * (sumX - sumY) * (C+
1);
if(Val1 > Val2) C ++;
if(C >
0)
for(
int i =
0; i < n; i++) X[i] += C;
else for(
int i =
0; i < n; i++) Y[i] += C;
for(
int i =
0; i < n; i++) sum += X[i] * X[i], a[i] = a[i+n] = Complex(X[i],
0);
for(
int i =
0; i < n; i++) sum += Y[i] * Y[i], b[i] = Complex(Y[n-i-
1],
0);
for(
int i = n<<
1; i < nn; i++) a[i] = Complex(
0,
0);
for(
int i = n; i < nn; i++) b[i] = Complex(
0,
0);
FFT(a,
1);
FFT(b,
1);
for(
int i =
0; i < nn; i++) c[i] = a[i] * b[i];
FFT(c, -
1);
ans = oo;
for(
int i = n-
1; i < (n<<
1); i++) ans = min(ans, sum -
2 * (
int)(c[i].real+
.5));
printf(
"%d\n", ans);
return 0;
}
