[Hnoi2017]礼物 – FFT

Description

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


Input
输入数据的第一行有两个数n, m,代表每条手环的装饰物的数量为n,每个装饰物的初始 亮度小于等于m。
接下来两行,每行各有n个数,分别代表第一条手环和第二条手环上从某个位置开始逆时 针方向上各装饰物的亮度。1≤n≤50000, 1≤m≤100, 1≤ai≤m


Output
输出一个数,表示两个手环能产生的最小差异值。
注意在将手环改造之后,装饰物的亮度 可以大于 m。


Solution

可以想到,先旋转到最优方案,再枚举亮度。而关键在于怎样求旋转到的最优方案。

把差异值的式子展开得到下图这个式子。

所以目标就是让下面这个式子最大。

此时可以发现,如果旋转第一个环之后第一个环的第1个是原来第一个环的第k个,那么容易得出此时的差异值为:

如果分别把第一个环和第二个环翻转,并把环看作多项式,那么可以发现下图两个式子都是两个多项式的乘积中一个系数的值,这个可以做两遍FFT求出。

               

//这次用了一下C++自带的Complex,果然巨慢!!!!非常推荐手写Complex!!!


Code

#include<set>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<complex>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define N 200010
#define ll long long
#define lowbit(x) (x&-x)
#define maxint 2147483647
#define abs(x) (a<0?-a:a)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ckmax(a,b) (a=max(a,b))
#define ckmin(a,b) (a=min(a,b))
#define isd(c) ('0'<=c&&c<='9')
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c='\0'){char ch[(sizeof(T)+1)<<1];if (x<0) putchar('-'),x=-x;
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!='\0') putchar(c);
}
typedef complex<double> cpx;
const double pi=acos(-1.0);
int n,m,a[N],b[N],rev[N],lef[N],rig[N],ff,tmp[N];
cpx A[N],B[N];
inline void FFT(int n,cpx *y,int op) {
    for (int i=0; i<n; i++) if (i<rev[i]) swap(y[i],y[rev[i]]);
    for (int k=1; k<n; k<<=1) {
        cpx x(cos(pi/k),op*sin(pi/k));
        for (int i=0; i<n; i+=(k<<1)) {
            cpx w(1,0);
            for (int j=0; j<k; j++) {
                cpx u=y[i+j],v=w*y[i+j+k];
                y[i+j]=u+v;y[i+j+k]=u-v;w=w*x;
            }
        }
    }
}
inline void solve() {
    int tot=0;ff=1;
    while (ff<=(n<<1)-2)ff<<=1,tot++;
    memset(rev,0,sizeof(rev));
    for (int i=0; i<=ff; i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<tot-1);
    FFT(ff,A,1);FFT(ff,B,1);
    for (int i=0; i<=ff; i++)A[i]=A[i]*B[i];
    FFT(ff,A,-1);
}
int main() {
    int sum=0,pos=0,now=maxint,ans=maxint,sm=0;
    read(n),read(m);
    for (int i=1; i<=n; i++) read(a[i]),sum+=a[i]*a[i];
    for (int i=1; i<=n; i++) read(b[i]),sum+=b[i]*b[i];
    for (int i=0; i<n; i++) A[i]=a[n-i],B[i]=b[i+1];
    solve();
    for (int i=1; i<=n; i++)rig[i]=((int)(A[n-i].real()/ff+0.5));
    for (int i=0; i<=ff; i++) A[i]=B[i]=0;
    for (int i=0; i<n; i++) A[i]=a[i+1],B[i]=b[n-i];
    solve();
    for (int i=1; i<=n; i++)lef[i]=((int)(A[i-1].real()/ff+0.5));
    for (int i=1; i<=n; i++) {int x=sum-(lef[i-1]+rig[i]<<1);if (x<now) now=x,pos=i;}
    if (pos>1) {
        for (int i=pos; i<=n; i++) tmp[i]=a[i];
        for (int i=n; i>=n-pos+2; i--) a[i]=a[i-n+pos-1];
        for (int i=pos; i<=n; i++) a[i-pos+1]=tmp[i];
    }
    for (int i=1; i<=n; i++) sm+=a[i]-b[i];
    for (int i=-100; i<=100; i++)ans=min(ans,now+n*i*i+2*sm*i);
    printf("%d\n",ans);return 0;
}

点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s