题面

传送门：洛咕

Solution

调得我头大，我好菜啊好吧，我们来颓柿子吧：我们可以只旋转其中一个手环。对于亮度的问题，因为可以在两个串上增加亮度，我们也可以看做是可以为负数的。所以说，我们可以假设我们旋转$B$串，上下要加上的亮度差为$p$,可以直接拍出一个最暴力的柿子：设$f(x)$表示$B$串以$x$为开头的差异值，有： $f(x)=\sum_{i=0}^{x-1}(B[i]-A[i+n-x]+p)^2+\sum_{i=x}^{n-1}(B[i]-A[i-x]+p)^2$ 大力展开化简后有： $f(x)=\sum_{i=0}^{n-1}A[i]^2+\sum_{i=0}^{n-1}B[i]^2+n*p^2-2p\sum_{i=0}^{n-1}(A[i]-B[i])-2\sum_{i=0}^{x-1}(B[i]*A[i+n-x])-2\sum_{i=x}^{n-1}(B[i]*A[i-x])$ 前两项$\sum_{i=0}^{n-1}A[i]^2+\sum_{i=0}^{n-1}B[i]^2$显然$O(n)预处理出来$ 中间两项$n*p^2-2p\sum_{i=0}^{n-1}(A[i]-B[i])$是一个关于$p$的二次函数，我们找最小值就好。（因为这题$m$非常小，我们也可以暴力枚举），复杂度$O(1)$或$O(m)$。最后两项$-2\sum_{i=0}^{x-1}(B[i]*A[i+n-x])-2\sum_{i=x}^{n-1}(B[i]*A[i-x])$看起来非常像卷积，但是并不是，因此我们得做点处♂理。蒟蒻本人是这样处理的：首先，后面那个循环范围是肯定没法卷的，因此我们先把后面的循环处理一下得： $-2\sum_{i=0}^{x-1}(B[i]*A[i+n-x])-2\sum_{i=0}^{n-x-1}(A[i]*B[i+x])$ 然后我们可以考虑把前面那项的$A$反转(这样可以处理掉$n$来方便卷积)，把后面那项的$B$反转(这样可以制造$n$与$\sum$对应) $-2\sum_{i=0}^{x-1}(B[i]*A’[x-1-i])-2\sum_{i=0}^{n-x-1}(A[i]*B’[n-1-i-x])$ 哦豁，卷积，搞定。时间复杂度$O(n*logn)$

Code

我什么时候才能一次性写对FFT啊

//Luogu P3723 [AH2017/HNOI2017]礼物
//Jan,20th,2019
//颓柿子+FFT加速计算
#include<iostream>
#include<cstdio>
#include<cmath>
#include<complex>
#include<algorithm>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x\*10+c-'0';c=getchar();}
    return x\*f;
}
const int M=50000+100;
const int N=M\*4;
const double PI=acos(-1);
typedef complex <double> cp;
inline cp omega(int K,int n)
{
    return cp(cos(2\*PI\*K/n),sin(2\*PI\*K/n));
}
void FFT(cp a[],int n,bool type)
{
    static int tmp[N],num=n-1,len=0;
    while(num!=0) num/=2,len++;
    for(int i=0,j;i<=n;i++)
    {
        for(j=0,num=i;j<len;j++)
            tmp[j]=num%2,num/=2;
        reverse(tmp,tmp+len);
        for(j=0,num=0;j<len;j++)
            num+=tmp[j]\*(1<<j);
        if(i<num) swap(a[i],a[num]);
    }
    for(int l=2;l<=n;l\*=2)
    {
        cp x0=omega(1,l);
        if(type==true) x0=conj(x0);
        int m=l/2;
        for(int j=0;j<n;j+=l)
        {
            cp x(1,0);
            for(int k=0;k<m;k++,x\*=x0)
            {
                cp temp=x\*a[j+k+m];
                a[j+k+m]=a[j+k]-temp;
                a[j+k]=a[j+k]+temp;
            }
        }
    }
}
int n,m,a[N],b[N];
cp B1[N],A1[N],B2[N],A2[N];
long long ans;
int main()
{
    freopen("3723.in","r",stdin);

    n=read(),m=read();
    for(int i=0;i<n;i++)
        a[i]=read();
    for(int i=0;i<n;i++)
        b[i]=read();

    long long dif=0;
    for(int i=0;i<n;i++)
        ans+=a[i]\*a[i]+b[i]\*b[i],dif+=a[i]-b[i];
    long long t_ans=0x3f3f3f3f\*0x3f3f3f3f;
    for(int i=-m;i<=m;i++)
        t_ans=min(t_ans,n\*i\*i-2\*i\*dif);
    ans+=t_ans;

    int t=1;
    while(t<2\*n) t\*=2;
    reverse(a,a+n);
    for(int i=0;i<n;i++)
        A1[i]=a[i],B1[i]=b[i];
    FFT(A1,t,false);
    FFT(B1,t,false);
    for(int i=0;i<t;i++)
        A1[i]\*=B1[i];
    FFT(A1,t,true);
    for(int i=0;i<t;i++)
        A1[i].real()/=t;

    reverse(a,a+n);
    reverse(b,b+n);
    for(int i=0;i<n;i++)
        A2[i]=a[i],B2[i]=b[i];
    FFT(A2,t,false);
    FFT(B2,t,false);
    for(int i=0;i<t;i++)
        A2[i]\*=B2[i];
    FFT(A2,t,true);
    for(int i=0;i<t;i++)
        A2[i].real()/=t;

    t_ans=(long long)(2\*floor(A2[n-1].real()+0.5));
    for(int i=1;i<n;i++)
        t_ans=max(t_ans,(long long)(2\*floor(A1[i-1].real()+A2[n-i-1].real()+0.5)));
    ans-=t_ans;
    printf("%lld",ans);
    return 0;
}

[Luogu P3723] [AH2017/HNOI2017]礼物

题面

Solution

Code