BZOJ 4827 [Hnoi2017]礼物

题目大意

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

题目极为可怕= =

首先各种推式子：

$$\sum\limits_{i=1}^{n} (x_i - y_i + c)^2 = \sum\limits_{i=1}^{n}(x_i - y_i)^2 + c^2 - 2 c(x_i - y_i)$$

(c为$y$增加的亮度值)

之后发现最终的答案和前面部分无关，只与$n c^2 - 2 c (sum_x - sum_y)$有关。

这个函数在$c = \frac{sum_x - sum_y}{n}$时最小，因为只能是整数所以需要四舍五入。

得到了$c$，$b$加上去就变成裸求了。

因为它是个环上问题所以可以倍增求解。答案就变成了$\min {\sum\limits_{i=1}^{n}a_i^2+\sum\limits_{i=1}^{n}b_i^2-\sum\limits_{i=1}^{n}2 a_i b_{i+n}}$

前两个预处理，最后一个倒过来FFT一下就可以求出来了。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const double pi=acos(-1);
int n,m,len=1;
double sum,ans;
struct cp
{
	double x,y;
	cp(){x=y=0;}
	cp(double _x,double _y){x=_x,y=_y;}
	cp operator+(const cp &tg)const{return cp(x+tg.x,y+tg.y);}
	cp operator-(const cp &tg)const{return cp(x-tg.x,y-tg.y);}
	cp operator*(const cp &tg)const{return cp(x*tg.x-y*tg.y,x*tg.y+y*tg.x);}
}a[1000000],b[1000000],c[1000000];
void fft(cp *x,int flg)
{
	for(int j,k=0,i=0;i<len;++i)
	{
		if(i>k) swap(x[i],x[k]);
		for(j=(len>>1);(k^=j)<j;j>>=1);
	}
	for(int i,j,k=2;k<=len;k<<=1)
	{
		cp wn(cos(2*pi*flg/k),sin(2*pi*flg/k));
		for(i=0;i<len;i+=k)
		{
			cp t,w(1,0);
			for(j=0;j<(k>>1);++j)
			{
				t=w*x[i+j+(k>>1)];
				x[i+j+(k>>1)]=x[i+j]-t;
				x[i+j]=x[i+j]+t;
				w=w*wn;
			}
		}
	}
	if(flg==-1) for(int i=0;i<len;++i) x[i].x/=len;
}
int main()
{
	double tmp=0;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i) scanf("%lf",&a[i].x),tmp+=a[i].x,sum+=a[i].x*a[i].x;
	for(int i=n-1;~i;--i) scanf("%lf",&b[i].x),tmp-=b[i].x;
	tmp=round(tmp/n);
	for(int i=0;i<n;++i) a[n+i]=a[i],b[i].x+=tmp,sum+=b[i].x*b[i].x;
	while(len<(n*3)) len<<=1;
	fft(a,1),fft(b,1);
	for(int i=0;i<len;++i) c[i]=a[i]*b[i];
	fft(c,-1);
	for(int i=n-1;i<=(n<<1)-2;++i) ans=max(ans,c[i].x);
	printf("%.0lf\n",sum-(ans*2));
	return 0;
}