Chlience

【题解】LOJ 2020 「AHOI / HNOI2017」礼物
Problem给定两个环 $a,b$ ,每个位置有一个权值可以对某个环权值全部加上任意值,可以旋转环,不可以翻转,...
扫描右侧二维码阅读全文
01
2019/02

【题解】LOJ 2020 「AHOI / HNOI2017」礼物

Problem

给定两个环 $a,b$ ,每个位置有一个权值
可以对某个环权值全部加上任意值,可以旋转环,不可以翻转,最小化

$$ \sum_{i=1}^n(a_i-b_i+c)^2 $$

Thought

$$ \sum_{i=1}^n(a_i-b_i+c)^2\\ \sum_{i=1}^na_i^2+b_i^2-2a_ib_i+c^2+2c(a_i-b_i)\\ \sum_{i=1}^n(a_i^2+b_i^2)-2\sum_{i=1}^na_ib_i+2c\sum_{i=1}^n(a_i-b_i)+nc^2 $$

$c$ 只与 $\sum (a_i-b_i)$ 和 $n$ 有关,是个二次函数的形式,可以直接求最值,$\sum_{i=1}^n(a_i^2+b_i^2)$ 可以直接计算

那么只需要求 $\sum_{i=1}^na_ib_i$ ,只需要翻转一个数组,倍长另外一个,然后卷积即可

Code

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const int N = 50010;
struct Complex {
    double x, y;
    Complex operator + (const Complex a) {return {x + a.x, y + a.y};}
    Complex operator - (const Complex a) {return {x - a.x, y - a.y};}
    Complex operator * (const Complex a) {return {x * a.x - y * a.y, x * a.y + y * a.x};}
};
Complex a[N << 2], b[N << 2];
int rev[N << 2], n, m;
int X[N], Y[N];
double suma, suma2, sumb, sumb2, C;
long long ans;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
void DFT(Complex* now, int f) {
    for(int i = 0; i < m; ++ i)
        if(rev[i] > i)
            swap(now[i], now[rev[i]]);
    for(int i = 1; i < m; i <<= 1) {
        Complex wn = {cos(pi / i), f * sin(pi / i)};
        for(int j = 0; j < m; j += (i << 1)) {
            Complex w = {1, 0}, a, b;
            for(int k = 0; k < i; ++ k, w = w * wn) {
                a = now[j + k];
                b = w * now[i + j + k];
                now[j + k] = a + b;
                now[i + j + k] = a - b;
            }
        }
    }
    if(f == - 1)
        for(int i = 0 ; i < m; ++ i)
            now[i].x /= m;
}
long long getC(int c) {return 1ll * (suma - sumb) * c + 1ll * n * c * c;}
int main() {
    n = read(); m = read();
    for(int i = 0; i < n; ++ i) {X[i] = read(); suma += X[i];}
    for(int i = 0; i < n; ++ i) {Y[i] = read(); sumb += Y[i];}
    C = round((sumb - suma) / n);
    for(int i = 0; i < n; ++ i) {
        X[i] += C;
        a[i].x = a[n + i].x = X[i];
        b[i].x = Y[n - i - 1];
        suma2 += X[i] * X[i];
        sumb2 += Y[n - i - 1] * Y[n - i - 1];
    }
    int l = 0;
    for(m = 1; m < 2 * n; m <<= 1) ++ l;
    for(int i = 0; i < m; ++ i)
        rev[i] = ((rev[i >> 1] >> 1) | (i & 1) << (l - 1));
    DFT(a, 1); DFT(b, 1);
    for(int i = 0; i < m; ++ i)
        a[i] = a[i] * b[i];
    DFT(a, - 1);
    for(int i = n; i < 2 * n; ++ i)
        ans = max(ans, (long long)round(a[i].x));
    ans = suma2 + sumb2 - 2 * ans;
    printf("%lld\n", ans);
    return 0;
}
Last modification:February 2nd, 2019 at 09:58 am

Leave a Comment