zcmimi's blog
查看原题

点击跳转

给两个手环同时增加亮度,与给其中一个增/减亮度是一样的

同时旋转两个手环,旋转其中一个是一样的

设旋转后两个手环分别为a,b,其中一个加上x

那么就是让\sum_{i=1}^n (a_i-b_{i}+x)^2最小

\displaystyle \sum_{i=1}^n (a_i-b_{i}+x)^2\\ =\sum_{i=1}^n a_i^2+\sum_{i=1}^n b_i^2+nx^2+2x(\sum_{i=1}^n a_i-b_i)-2\sum_{i=1}^n a_ib_i

其中只有最后一项是变化的,前几项都可以直接求得

nx^2+2x(\sum_{i=1}^n a_i-b_i)是关于x的二次函数,直接求得最小值

考虑\sum_{i=1}^n a_ib_i

可以发现\sum_{i=1}^n a_{n-i+1}b_i是卷积的形式

那么我们把a倍长,把b翻转,然后再卷积,得到n+12n次项中的最大值就是\sum_{i=1}^n a_ib_i的最大值

#include<bits/stdc++.h>
typedef double db;
typedef long long ll;
const int N=50011,M=1<<18;
const db Pi=acos(-1);
int n,m;
struct cp{
    db r,i;explicit cp(db R=0,db I=0){r=R,i=I;}
    cp operator+(const cp&x)const{return cp(r+x.r,i+x.i);}
    cp operator-(const cp&x)const{return cp(r-x.r,i-x.i);}
    cp operator*(const cp&x)const{return cp(r*x.r-i*x.i,r*x.i+i*x.r);}
}a[M],b[M];
int L,r[M];
void swap(cp&x,cp&y){cp t=x;x=y;y=t;}
void getL(int n){
    for(L=1;L<n;L<<=1);
    for(int i=0;i<L;++i)
        r[i]=(r[i>>1]>>1)|((i&1)?(L>>1):0);
}
void fft(cp*A,int typ){
    for(int i=0;i<L;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<L;len<<=1){
        cp Wn(std::cos(Pi/len),typ*std::sin(Pi/len));
        for(int i=0;i<L;i+=len<<1){
            cp w(1);
            for(int k=0;k<len;++k,w=w*Wn){
                cp t=A[i+k+len]*w;
                A[i+k+len]=A[i+k]-t;
                A[i+k]=A[i+k]+t;
            }
        }
    }
    if(~typ)return;
    for(int i=0;i<L;++i)
        A[i].r/=L,A[i].i/=L;
}
void cmin(ll&x,ll y){if(y<x)x=y;}
int main(){
    scanf("%d%d",&n,&m);
    int x;
    ll ans=1ll<<60,a1=0,a2=0,b1=0,b2=0;
    for(int i=1;i<=n;++i)
        scanf("%d",&x),
        a1+=x,a2+=x*x,
        a[i]=a[n+i]=cp(x);
    for(int i=1;i<=n;++i)
        scanf("%d",&x),
        b1+=x,b2+=x*x,
        b[n-i+1]=cp(x);
    getL(n<<2);
    fft(a,1),fft(b,1);
    for(int i=0;i<L;++i)a[i]=a[i]*b[i];
    fft(a,-1);
    for(int i=1;i<=n;++i)
        for(x=-m;x<=m;++x)
            cmin(ans,a2+b2+1ll*n*x*x+2ll*x*(a1-b1)-2ll*ll(a[i+n].r+0.5));
    printf("%lld\n",ans);
}
LG 3723 [AH2017]礼物
comment评论
Search
search