首页 > 代码库 > [BZOJ 4827][Hnoi2017]礼物（FFT）

[BZOJ 4827][Hnoi2017]礼物（FFT）

2024-09-20 14:39:03   205人阅读

Description

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手 环，一个留给自己，一
个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。但是在她生日的前一天，我的室友突
然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有
装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，
但是由于上面 装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差
异值最小。在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 1,2,…,n，
其中 n 为每个手环的装饰物个数，第 1 个手环的 i 号位置装饰物亮度为 xi，第 2 个手 环的 i 号位置装饰物
亮度为 yi，两个手环之间的差异值为(参见输入输出样例和样例解释)： \sum_{i=1}^{n}(x_i-y_i)^2麻烦你帮他
计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小， 这个最小值是多少呢？

Solution

列式子然后化成了Σ(xi2+yi2+2xic-2yic)-2*Σ(xi*yi+k)+n*c2

循环卷积来求中间那项的值，经过一些预处理额并枚举c和k最小化答案

#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define PI acos(-1)#define MAXN 50005#define INF 1LL<<60typedef long long LL;using namespace std;int n,m;struct cp{    double r,i;    cp(double r=0,double i=0):r(r),i(i){}    cp operator + (const cp& x)    {return cp(r+x.r,i+x.i);}    cp operator - (const cp& x)    {return cp(r-x.r,i-x.i);}    cp operator * (const cp& x)    {return cp(r*x.r-i*x.i,r*x.i+i*x.r);}}a[MAXN*8],b[MAXN*8];void brc(cp* x,int l){    int j=l/2;    for(int i=1;i<l-1;i++)    {        if(i<j)swap(x[i],x[j]);        int k=l/2;        while(k<=j)        {            j-=k;            k>>=1;        }        if(j<k)j+=k;    }}void fft(cp* x,int l,int on){    brc(x,l);    for(int h=2;h<=l;h<<=1)    {        cp wn(cos(2*on*PI/h),sin(2*on*PI/h));        for(int i=0;i<l;i+=h)        {            cp w(1,0);            for(int j=i;j<i+h/2;j++)            {                cp u=x[j];                cp t=w*x[j+h/2];                x[j]=u+t;                x[j+h/2]=u-t;                w=w*wn;            }        }    }    if(on==-1)for(int i=0;i<l;i++)x[i].r/=l;}int main(){    scanf("%d%d",&n,&m);    int l=1;    while(l<2*n+1)l<<=1;    LL sum=0,t=0;    for(int i=1;i<=n;i++)    {        int x;        scanf("%d",&x);        a[i]=a[i+n]=cp(x,0);        sum+=x*x;        t+=x;    }    for(int i=1;i<=n;i++)    {        int x;        scanf("%d",&x);        b[n-i+1]=cp(x,0);        sum+=x*x;        t-=x;    }    fft(a,l,1),fft(b,l,1);    for(int i=0;i<l;i++)a[i]=a[i]*b[i];    fft(a,l,-1);    t=t>0?t:-t;    LL ans=INF;    for(int i=0;i<=m;i++)    ans=min(ans,i*i*n-2*i*t);    ans+=sum;    LL p=0;    for(int i=0;i<l;i++)    p=max(p,(LL)(a[i].r+0.1));    ans-=2*p;    printf("%lld",ans);    return 0;}

 

[BZOJ 4827][Hnoi2017]礼物（FFT）


联系
我们