[AH/HNOI2017]礼物

\[推推公式，即求\Sigma^{n}_{i=1} (x_{i+k}-y_i+c)^2最小，c范围为[-m, m]
\]

\[拆开，就是\Sigma x_i^2 + \Sigma y_i^2 + n * c^2 + 2*c*\Sigma(x_{i+k}-y_i) - 2*\Sigma^{n}_{i=1} x_{i+k}y_i
\]

\[即求2*\Sigma^{n}_{i=1} x_{i+k}y_i最大，再枚举c即可
\]

七十分暴力代码（暴力分贼多）

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int _(1e5 + 10);

IL ll Read(){

    char c = '%'; ll x = 0, z = 1;

    for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';

    return x * z;

}

int n, m;

ll sqx, sqy, sx, sy, x[_], y[_], ans = -1e18, mn = 1e18;

int main(RG int argc, RG char *argv[]){

    n = Read(); m = Read();

    for(RG int i = 1; i <= n; ++i) x[i + n] = x[i] = Read(), sx += x[i], sqx += x[i] * x[i];

    for(RG int i = 1; i <= n; ++i) y[i] = Read(), sy += y[i], sqy += y[i] * y[i];

    for(RG int i = 0; i < n; ++i){

        RG ll cnt = 0;

        for(RG int j = 1; j <= n; ++j) cnt += x[j + i] * y[j];

        ans = max(ans, cnt);

    }

    for(RG int c = -m; c <= m; ++c) mn = min(mn, 1LL * n * c * c + 1LL * 2 * c * (sx - sy) - 2 * ans);

    printf("%lld\n", mn + sqx + sqy);

    return 0;

}

\[\Sigma^{n}_{i=1} x_{i+k}y_i，很套路，就往FFT上靠，把y反转不就变成\Sigma^{n}_{i=1} x_{i+k}y_{n-i+1}
\]

\[这不就是卷积，就是多项式相乘后第n+k+1项的系数，这就可以FFT了
\]

把y反转，再倍长，跑一遍FFT，取有用的中间一段的最大值

再枚举c求解即可

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int _(4e5 + 10);

const double Pi(acos(-1));

IL ll Read(){

	char c = '%'; ll x = 0, z = 1;

	for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1;

	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';

	return x * z;

}

struct Complex{

	double real, image;

	IL Complex(){  real = image = 0;  }

	IL Complex(RG double a, RG double b){  real = a; image = b;  }

	IL Complex operator +(RG Complex B){  return Complex(real + B.real, image + B.image);  }

	IL Complex operator -(RG Complex B){  return Complex(real - B.real, image - B.image);  }

	IL Complex operator *(RG Complex B){  return Complex(real * B.real - image * B.image, real * B.image + image * B.real);  }

} A[_], B[_];

int n, m, N, M, l, r[_];

ll sx, sy, sqx, sqy, mx = -1e18, ans = 1e18;

IL void FFT(RG Complex *P, RG int opt){

	for(RG int i = 0; i < N; i++) if(i < r[i]) swap(P[i], P[r[i]]);

	for(RG int i = 1; i < N; i <<= 1){

		RG Complex W(cos(Pi / i), opt * sin(Pi / i));

		for(RG int p = i << 1, j = 0; j < N; j += p){

			RG Complex w(1, 0);

			for(RG int k = 0; k < i; ++k, w = w * W){

				RG Complex X = P[k + j], Y = w * P[k + j + i];

				P[k + j] = X + Y; P[k + j + i] = X - Y;

			}

		}

	}

}

int main(RG int argc, RG char *argv[]){

	n = Read() - 1; m = Read();

	for(RG int i = 0; i <= n; ++i) A[i].real = Read(), sx += A[i].real, sqx += A[i].real * A[i].real;

	for(RG int i = n; i >= 0; --i) B[i + n + 1].real = B[i].real = Read(), sy += B[i].real, sqy += B[i].real * B[i].real;

	for(M = 3 * n, N = 1; N <= M; N <<= 1) ++l;

	for(RG int i = 0; i < N; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));

	FFT(A, 1); FFT(B, 1);

	for(RG int i = 0; i < N; ++i) A[i] = A[i] * B[i];

	FFT(A, -1);

	for(RG int i = n; i <= 2 * n; ++i) mx = max(mx, (ll)(A[i].real / N + 0.5));

	for(RG int c = -m; c <= m; ++c) ans = min(ans, 1LL * (n + 1) * c * c + 1LL * 2 * c * (sx - sy));

	printf("%lld\n", ans + sqx + sqy - 2 * mx);

	return 0;

}

巴特西

[AH/HNOI2017]礼物

最新文章

热门文章