做这种题就是大胆列柿子
设已经匹配好的两串为$a,b$,加$x$
即$\sum\limits_{i=1}^n (a_i+x-b_i)^2$。
展开它
$\sum\limits _{i=1}^n {a_i}^2+{b_i}^2+x^2+2*x*a_i-2*x*b_i-2*a_i*b_i\\\sum\limits_{i=1}^na_i^2+\sum\limits_{i=1}^nb_i^2+n*x^2+2*x*(\sum\limits_{i=1}^na_i-\sum\limits_{i=1}^nb_i)-2*\sum\limits_{i=1}^na_ib_i$
发现前几项都是定值,就是$\sum\limits_{i=1}^na_ib_i$是个变量,变形$\sum\limits_{i=1}^na_{n-i+1}b_i$
把$a$倍长后,直接上$fft$,最大值从$n+1\sim 2*n$中找。
至于$x$的取值,由于$a_i,b_i\in[1,m]$,那么$w=a_i-b_i\in[m-1,-m-1]$
则$x\in[-m.m]$,暴力枚举$x$就好了。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int mod=1e9+7,N=1<<18;
const double pi=acos(-1);
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct CP
{
double x,y;
CP(double x=0.0,double y=0.0):x(x),y(y){}
CP operator +(const CP a)const{return CP(x+a.x,y+a.y);}
CP operator -(const CP a)const{return CP(x-a.x,y-a.y);}
CP operator *(const CP a)const{return CP(x*a.x-y*a.y,x*a.y+y*a.x);}
}f[N],g[N];
int tr[N],n,m;
void fft(CP *f,int op)
{
for(int i=0;i<n;i++)
if(tr[i]<i)swap(f[i],f[tr[i]]);
for(int p=2;p<=n;p<<=1)
{
int len=p>>1;
CP tg=CP(cos(2*pi/p),sin(2*pi/p)*op);
for(int k=0;k<n;k+=p)
{
CP buf=CP(1,0);
for(int l=k;l<k+len;l++)
{
CP t=buf*f[l+len];
f[l+len]=f[l]-t;
f[l]=f[l]+t;
buf=buf*tg;
}
}
}
}
int a[N],b[N];
int main()
{
qr(n),qr(m);int t=n,mx=m,s1=0,s2=0;
for(int i=1;i<=n;i++)qr(a[i]),s1+=a[i]*a[i],s2+=2*a[i];
for(int i=1;i<=n;i++)qr(b[i]),s1+=b[i]*b[i],s2-=2*b[i];
for(int i=1;i<=n;i++)f[i-1].x=a[i],g[n-i]=b[i];
for(int i=0;i<n;i++)g[i+n]=g[i];
m=2*n-1;n--;
for(m+=n,n=1;n<=m;n<<=1);
for(int i=0;i<n;i++)
tr[i]=tr[i>>1]>>1|((i&1)?n>>1:0);
fft(f,1),fft(g,1);
for(int i=0;i<n;i++)f[i]=f[i]*g[i];
fft(f,-1);
int w=0,ans=0x3f3f3f3f;
for(int i=t-1;i<=2*t-1;i++)
w=max(w,(int)(2*f[i].x/n+0.49));
for(int c=-mx;c<=mx;c++)
{
int sum=s1+c*s2-w+t*c*c;
ans=min(ans,sum);
}
qw(ans);puts("");
return 0;
}
最后一次更新于2020-03-22
0 条评论