[AH2017]礼物 - A-Failure的博客

题目

题目描述

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。

但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号1,2,…,n，其中 n 为每个手环的装饰物个数，第 1 个手环的 i 号位置装饰物亮度为 xi，第 2 个手环的 i 号位置装饰物亮度为 yi，两个手环之间的差异值为(参见输入输出样例和样例解释)：

$\sum_{i=1}^{n} (x_i-y_i)^2$

麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？

输入输出格式

输入格式：

输入数据的第一行有两个数n, m，代表每条手环的装饰物的数量为n，每个装饰物的初始亮度小于等于m。

接下来两行，每行各有n个数，分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。

输出格式：

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

可以大于 m。

输入输出样例

输入样例#1：

5 6
1 2 3 4 5
6 3 3 4 5

输出样例#1：

说明

【样例解释】

需要将第一个手环的亮度增加1，第一个手环的亮度变为： 2 3 4 5 6

旋转一下第二个手环。对于该样例，是将第二个手环的亮度6 3 3 4 5向左循环移动一个位置，使得第二手环的最终的亮度为： 3 3 4 5 6。

此时两个手环的亮度差异值为1

【数据范围】

30%的数据满足n≤500, m≤10；

70%的数据满足n≤5000；

100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。

题解

答案为$\sum_{i=0}^{n-1}(x_{(i+k)\%n}-y_i+c)^2$

拆开化简$\sum_{i=0}^{n-1}x_i^2+y_i^2+2c(x_i-y_i)+c^2-2x_{(i+k)\%n}y_i$

前面$4$项都是定值，要求的就是$\sum_{i=0}^{n-1}x_{(i+k)\%n}y_i$的最大值

破环成链，就成了$\sum_{i=0}^{n-1}x_{i+k}y_i$

这挺像卷积的形式啊，把$x$倒过来，就是$\sum_{i=0}^{n-1}x_{n-i-1+k}y_i$

这样把$x$与$y$卷积，第$n+k$项就是旋转$k$位的值

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=4e5+5;
const double Pi=acos(-1.0);
struct Complex{
	double x,y;
	Complex(double X=0,double Y=0) {x=X,y=Y;}
}a[MAX],b[MAX];
int n,m,N,M,lim=1,L;
LL A,B,C,ans=1e18;
int R[MAX];
Complex operator+ (Complex x,Complex y) {return Complex(x.x+y.x,x.y+y.y);}
Complex operator- (Complex x,Complex y) {return Complex(x.x-y.x,x.y-y.y);}
Complex operator* (Complex x,Complex y) {return Complex(x.x*y.x-x.y*y.y,x.y*y.x+x.x*y.y);}
void FFT(Complex *A,int tt=1)
{
	for(int i=0;i<lim;++i)
	  if(i<R[i]) swap(A[i],A[R[i]]);
	for(int i=1;i<lim;i<<=1)
	  {
	  	Complex w1=Complex(cos(Pi/i),tt*sin(Pi/i));
	  	for(int l=i<<1,j=0;j<lim;j+=l)
	  	  {
	  	  	Complex w=Complex(1,0),x,y;
	  	  	for(int k=0;k<i;++k,w=w*w1)
	  	  	  x=A[j+k],y=w*A[i+j+k],A[j+k]=x+y,A[i+j+k]=x-y;
		  }
	  }
}
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
int main()
{
	n=read(),m=read();
	for(int i=0;i<n;++i)
	  a[i].x=a[i+n].x=read(),A+=a[i].x,B+=a[i].x*a[i].x;
	for(int i=0;i<n;++i)
	  b[i].x=read(),A-=b[i].x,B+=b[i].x*b[i].x;
	M=n-1,N=M+n-1,reverse(a,a+N+2);
	while(lim<=N+M) lim<<=1,++L;
	for(int i=0;i<lim;++i)
	  R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
	FFT(a),FFT(b);
	for(int i=0;i<=lim;++i)
	  a[i]=a[i]*b[i];
	FFT(a,-1);
	for(int i=n;i<N;++i)
	  C=max(C,(LL)(a[i].x/lim+0.5));
	for(int i=-m;i<=m;++i)
	  ans=min(ans,B+2*i*A-2*C+n*i*i);
	return printf("%lld",ans),0;
}

题目