您的位置: 首页  >  IT文章  >  P3723 [AH2017/HNOI2017]礼物

P3723 [AH2017/HNOI2017]礼物

分类: IT文章 • 2022-09-01 15:08:59

(n) 个装饰物，并且每个装饰物都有一定的亮度。

(c)（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。

(yi)，两个手环之间的差异值为(参见输入输出样例和样例解释)：

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

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

输入输出格式

(m)。

(n)个数，分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。

(m)。

输入输出样例

输入样例#1：

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

输出样例#1：

1

说明

【样例解释】

(6)

(6)。

(1)

【数据范围】

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

(70\%)的数据满足(n≤5000)；

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

(DP)+二分使劲写写不出来。

(C)可正可负即可。这样式子就变成了

$$sum(x_i + y_i + k) ^ 2$$

(y_i)的顺序问题。）

紧接着我们把式子展开，得到：

$$sum x_i^2 + sum y_i^2 + N * K ^ 2 + 2 * K * (sum x_i -y_i) - 2 * sum x_i * y_i$$

(y)数列翻转倍长（翻转是便于卷积，倍长是为了可以忽略顺序问题，断环为链。）

(N * 2)位找一个最大的值，就是手链顺序对答案产生的最大贡献了。

#include <bits/stdc++.h>
using namespace std;

#define LL long long
const int N = 100010;
const double pi = acos (-1);

struct Complex {
	double x, y;
	Complex (double xx = 0, double yy = 0) {x = xx, y = yy;}
	Complex operator + (Complex rhs) {return Complex (x + rhs.x, y + rhs.y);}
	Complex operator - (Complex rhs) {return Complex (x - rhs.x, y - rhs.y);}
	Complex operator * (Complex rhs) {return Complex (x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);}
}X[N], Y[N], S[N];

int n, m, l, lim = 1, x[N], y[N], r[N]; LL ans, res;

void fast_fast_tle (Complex *A, int type) {
	for (int i = 0; i < lim; ++i) {
		if (i < r[i]) {
			swap (A[i], A[r[i]]);
		}
	}
	for (int mid = 1; mid < lim; mid <<= 1) {
		Complex Wn (cos (pi / mid), type * sin (pi / mid));
		for (int p = 0; p < lim; p += (mid << 1)) {
			Complex w (1, 0);
			for (int k = 0; k < mid; ++k, w = w * Wn) {
				Complex xx = A[p + k];
				Complex yy = w * A[p + k + mid];
				A[p + k] = xx + yy;
				A[p + k + mid] = xx - yy;
			}
		}
	}
	if (type == -1) {
		for (int i = 0; i < lim; ++i) {
			A[i].x /= lim;
		}
	}
}

int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> x[i];
	for (int i = 1; i <= n; ++i) cin >> y[i];
	for (int i = 1; i <= n; ++i) {
		ans += x[i] * x[i];
		ans += y[i] * y[i];
	    res += y[i] - x[i];
	}
	int T1 = ceil  ((double) res / (double) n);
	int T2 = floor ((double) res / (double) n);
	ans += min (
				n * T1 * T1 - 2 * T1 * res,
				n * T2 * T2 - 2 * T2 * res
				);
	n = n - 1;
	for (int i = 0; i <= n; ++i) {
		X[i].x = x[i + 1];
		Y[i].x = y[n - i + 1];
	}
	for (int i = n + 1; i <= n * 2 + 1; ++i) {
		Y[i] = Y[i - n - 1];
	}
	while (lim <= n * 2 + 1) ++l, lim <<= 1;
	for (int i = 0; i < lim; ++i) {
		r[i] = (r[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
	}
	fast_fast_tle (X, 1);
	fast_fast_tle (Y, 1);
	for (int i = 0; i < lim; ++i) {
		S[i] = X[i] * Y[i];
	}
	fast_fast_tle (S, -1);
	LL tmp = (LL) -1e18;
	for (int i = n + 1; i <= n * 2 + 1; ++i) {
		tmp = max (tmp, (LL) (S[i].x + 0.5));
	}
	cout << ans - tmp * 2 << endl;
}

相关推荐