P3723 [AH2017/HNOI2017]礼物

斯德哥尔摩 · 2018-05-15 23:02:37 · 个人记录

题目要求：\sum_{i=1}^{n}(x_i-y_i)^2的最小值。

拿到一看，30分暴力分肯定有——直接枚举错多少位与添加多少亮度。

然后，设添加亮度为t，那么不用说，肯定是加，因为另一个手环的减可以转换成这一个手环的加。

则原式为\sum_{i=1}^{n}(x_i-y_i+t)^2

即：\sum_{i=1}^{n}[(x_i-y_i)^2+t^2-2t(x_i-y_i)]

展开：\sum_{i=1}^{n}(x_i-y_i)^2+nt^2-2t\sum_{i=1}^{n}(x_i-y_i)

由于不论错多少位，\sum_{i=1}^{n}(x_i-y_i)的值一定不変，所以预先处理出来即可.

设T=\sum_{i=1}^{n}(x_i-y_i)，那么上式可看做一个二次函数，当t=-\frac{-2T}{2n}=\frac{T}{n}时，函数可以取到最小值。

即转化为\sum_{i=1}^{n}(x_i-y_i)^2的最小值。

那么再对这个式子化简：\sum_{i=1}^{n}(x_i^2+y_i^2-2x_iy_i)

还是拆开：\sum_{i=1}^{n}(x_i^2+y_i^2)-2\sum_{i=1}^{n}x_iy_i

而前面那个\sum_{i=1}^{n}(x_i^2+y_i^2)也是一个定值，故转化成了：

求\sum_{i=1}^{n}x_iy_i的最大值。

乍一看，有点卷积的样子。。。

没错！就是卷积！

但是求和很烦。。。

没关系，我们将数列{x_n}翻转，成了：\sum_{i=1}^{n}x_{n-i+1}y_i

稳稳的卷积。。。

于是，我们将反转的数列{x_n}倍长，与数列{y_n}卷积，得到的答案中第n+1到第2n项中最大值，就是\sum_{i=1}^{n}x_iy_i的最大值。

注：

其实可以不用从第n+1到第2n项，因为这里面最大，一定是第1到第2n项的最大。
FFT因为要转到double在转回long long，有精度误差！所以eps应该开到1e-2
求t时，要在t-1，t，t+1中选出使nt^2-2t\sum_{i=1}^{n}(x_i-y_i)取最小值的t。

到此，我们的思路结束。

但是卷积怎么求？

主角登场——FFT，快速傅里叶变换。

说白了就是在O(nlog_2n)的时间内求出两个多项式的乘积（系数）。

然后我们并不需要知道什么推导过程啦，蝴蝶变换啦什么乱七八糟的玩意，考到了，基本上是推导很烦，但是FFT直接上板子即可的那种板子题。

FFT都是板子题！——巨神CYZ

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN (1<<18)
using namespace std;
int n,m,x[MAXN],y[MAXN];
long long add,s1=0,s2=0,s;
namespace FFT{//用namespace封装的板子
    int n,l,rev[MAXN];
    long long answer=2147483646,ans[MAXN];
    struct node{
        double r,i;
        node operator +(const node &a)const{return (node){r+a.r,i+a.i};}
        node operator -(const node &a)const{return (node){r-a.r,i-a.i};}
        node operator *(const node &a)const{return (node){r*a.r-i*a.i,r*a.i+i*a.r};}
    }a[MAXN],b[MAXN],d[MAXN];
    void DFT(node *a,int f){
        for(int i=0;i<l;i++)d[i]=a[rev[i]];
        for(int i=0;i<l;i++)a[i]=d[i];
        for(int i=2;i<=l;i<<=1){
            node wi=(node){cos(2.00*M_PI/i),f*sin(2.00*M_PI/i)};
            for(int k=0;k<l;k+=i){
                node w=(node){1.00,0.00},x,y;
                for(int j=0;j<i/2;j++){
                    x=a[k+j];y=w*a[k+j+i/2];
                    a[k+j]=x+y;a[k+j+i/2]=x-y;
                    w=w*wi;
                }
            }
        }
        if(f==-1)
        for(int i=0;i<l;i++)a[i].r/=l;
    }
    void FFT(){
        DFT(a,1);DFT(b,1);
        for(int i=0;i<l;i++)a[i]=a[i]*b[i];
        DFT(a,-1);
    }
    void init(int x){
        for(n=l=1;l<x;l<<=1)n++;
        l<<=1;
        for(int i=0;i<l;i++)
        for(int j=0,t=i;j<n;j++,t>>=1){rev[i]<<=1;rev[i]|=t&1;}
    }
    void DSC(int len){
        int l1=0,l2=0;
        for(int i=1;i<=len*2;i++){a[l1].r=x[i];a[l1++].i=0.00;}
        for(int i=1;i<=len;i++){b[l2].r=y[i];b[l2++].i=0.00;}
        reverse(a,a+l1);reverse(b,b+l2);
        init(max(l1,l2));
        FFT();
        for(int i=1;i<=l;i++)ans[i]=(long long)(a[i-1].r+0.5);
        for(int i=1;i<=l;i++)answer=min(answer,s2-ans[i]*2);
        printf("%lld\n",answer+s);
    }
}
inline int read(){//读优
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
void init(){//预处理
    s=2147483646;
    n=read();m=read();
    for(int i=1;i<=n;i++)x[i+n]=x[i]=read();
    for(int i=1;i<=n;i++)y[n-i+1]=read();
    for(int i=1;i<=n;i++){
        s1+=x[i]-y[i];
        s2+=x[i]*x[i]+y[i]*y[i];
    }
    add=(long long)((double)-s1*1.000/n+0.5);
    for(int i=-1;i<=1;i++)s=min(s,(n*(add+i)*(add+i)+2*s1*(add+i)));
}
int main(){//主函数So easy!
    init();
    FFT::DSC(n);
    return 0;
}