Tsr and Variance

题目描述

Tsr is a cute boy with handsome moustache.

You are given a sequence with length $n$. Tsr wants you to calculate the sum of variance of each successive subsequence. Note: The variance in this problem should’t be divided by length.

Recall $\overline{a}_{l, r}=\frac{1}{r-l+1} \sum_{i=l}^r a_i$. Then you are supposed to calculate $\sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j (a_k-\overline{a}_{i, j})^2$.

题意概述

给定一个长度为$n$的序列,求$\sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j (a_k-\overline{a}_{i, j})^2$。有$T$组数据。

数据范围:$1 \le T \le 20, \; 1 \le n \le 10000, \; 1 \le a_i \le 10$。

算法分析

$$\begin{align} \sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j (a_k-\overline{a}_{i, j})^2 &= \sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j (a_k^2-2a_k \overline{a}_{i, j}+\overline{a}_{i, j}^2) \\ &= \sum_{k=1}^n \sum_{i=1}^k \sum_{j=k}^n a_k^2-2\sum_{i=1}^n \sum_{j=i}^n \overline{a}_{i, j} \sum_{k=i}^j a_k+ \sum_{i=1}^n \sum_{j=i}^n (j-i+1) \overline{a}_{i, j}^2 \\ &= \sum_{k=1}^n k(n-k+1)a_k^2-\sum_{i=1}^n \sum_{j=i}^n (j-i+1) \overline{a}_{i, j}^2 \end{align}$$

前一项可以在$O(n)$时间内求出,只需考虑如何求后一项。令$s_i=\sum_{j=1}^i a_j$。

$$\begin{align} \sum_{i=1}^n \sum_{j=i}^n (j-i+1) \overline{a}_{i, j}^2 &= \sum_{j=1}^n \sum_{i=1}^j \frac{(s_j-s_{i-1})^2}{j-i+1} \\ &= \sum_{j=1}^n \sum_{i=1}^j \frac{s_j^2-2s_js_{i-1}+s_{i-1}^2}{j-i+1} \\ &= \sum_{j=1}^n s_j^2 \sum_{i=1}^j \frac{1}{i}-2\sum_{j=1}^n s_j \sum_{i=1}^j \frac{s_{i-1}}{j-(i-1)}+\sum_{j=1}^n \sum_{i=1}^j \frac{s_{i-1}^2}{j-(i-1)} \end{align}$$

第一项也可以在$O(n)$时间内求出,而后面两项都是卷积的形式,可以用FFT在$O(n\log n)$时间内求出。

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 10005, T = 400005;
double const PI = acos(-1);

int a[N], rev[T];

struct Point {
    double x, y;
    Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
    friend Point const operator + (Point const &a, Point const &b) {
        return Point(a.x + b.x, a.y + b.y);
    }
    friend Point const operator - (Point const &a, Point const &b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    friend Point const operator * (Point const &a, Point const &b) {
        return Point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
    }
    friend Point const operator / (Point const &a, double const &n) {
        return Point(a.x / n, a.y / n);
    }
} wn[T], A[T], B[T], C[T];

int init(int n) {
    int m = n, l = 0;
    for (n = 1; n <= m; n <<= 1, ++l) ;
    for (int i = 1; i < n; ++i) {
        rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
    }
    for (int i = 0; i < n >> 1; ++i) {
        wn[i] = Point(cos(2 * PI / n * i), sin(2 * PI / n * i));
    }
    return n;
}

void fft(Point *a, int n, int inv = 0) {
    for (int i = 0; i < n; ++i) {
        if (i < rev[i]) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = 0; k < i; ++k) {
                Point x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
                a[j + k] = x + y;
                a[j + k + i] = x - y;
            }
        }
    }
    if (inv) {
        std::reverse(a + 1, a + n);
        for (int i = 0; i < n; ++i) {
            a[i] = a[i] / n;
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    for (; T--;) {
        int n;
        scanf("%d", &n);
        double ans = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            ans += 1. * a[i] * a[i] * i * (n - i + 1);
            a[i] += a[i - 1];
        }
        double sum = 0;
        for (int i = 1; i <= n; ++i) {
            sum += 1. / i;
            ans -= sum * a[i] * a[i];
        }
        int len = init(n << 1);
        for (int i = 0; i < n; ++i) {
            A[i] = Point(a[i]);
            B[i] = Point(1. * a[i] * a[i]);
            C[i] = Point(1. / (i + 1));
        }
        for (int i = n; i < len; ++i) {
            A[i] = B[i] = C[i] = Point(0);
        }
        fft(A, len);
        fft(B, len);
        fft(C, len);
        for (int i = 0; i < len; ++i) {
            A[i] = A[i] * C[i];
            B[i] = B[i] * C[i];
        }
        fft(A, len, 1);
        fft(B, len, 1);
        for (int i = 0; i < n; ++i) {
            ans += 2 * a[i + 1] * A[i].x - B[i].x;
        }
        printf("%.10f\n", ans);
    }
    return 0;
}

Fence

题目描述

A team of $K$ workers should paint a fence which contains $N$ planks numbered from $1$ to $N$ from left to right. Each worker $i$ should sit in front of the plank $S_i$ and he may paint only a compact interval (this means that the planks from the interval should be consecutive). This interval should contain the $S_i$ plank. Also a worker should not paint more than $L_i$ planks and for each painted plank he should receive $P_i$\$. A plank should be painted by no more than one worker. All the numbers $S_i$ should be distinct.

Being the team’s leader you want to determine for each worker the interval that he should paint, knowing that the total income should be maximal. The total income represents the sum of the workers personal income.

Write a program that determines the total maximal income obtained by the $K$ workers.

题意概述

$K$个工人要粉刷一面长度为$N$的篱笆,第$i$个工人要么不粉刷,要么粉刷一段连续且长度不超过$L_i$的包含第$S_i$块木板的篱笆,他每粉刷一块木板可以获得$P_i$的报酬。每一块木板要么不被粉刷,要么仅被一个工人粉刷。求所有工人获得的总报酬的最大值。

数据范围:$1 \le K \le 100, \; 1 \le N \le 16000$。

算法分析

令$f_{i, j}$表示前$i$个工人粉刷前$j$块木板(不一定全刷)的最大报酬,则可分三种情况讨论:

  • 第$i$个工人不粉刷,$f_{i, j}=f_{i-1, j}$;
  • 第$j$块木板不被粉刷,$f_{i, j}=f_{i, j-1}$;
  • 第$i$个工人粉刷第$(k+1)$到第$j$块木板,$f_{i, j}=f_{i-1, k}+(j-k) \times P_i$。

在第三种情况中,转移方程变形后得$f_{i, j}=(f_{i-1, k}-k \times P_i)+j \times P_i$,$f_{i-1, k}-k \times P_i$与$j$无关,$j \times P_i$与$k$无关,因此对于确定的$i$和$j$,方程后半部分为常数,只要求前半部分的最大值。因为前半部分只与$k$有关,所以可以用单调队列维护其最大值。注意$k$要满足的条件是$k+1 \le S_i \le j$与$j-(k+1)+1 \le L_i$,即$j-L_i \le k \lt S_i$。算法的时间复杂度为$O(KN)$。

代码

#include <cstdio>
#include <algorithm>

int const K = 105, N = 16005;
int f[K][N];
struct Carpenter {
    int l, p, s;
    bool operator < (Carpenter const &t) const {
        return s < t.s;
    }
} c[K];
std::pair<int, int> que[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d%d", &c[i].l, &c[i].p, &c[i].s);
    }
    std::sort(c + 1, c + k + 1);
    for (int i = 1; i <= k; ++i) {
        int qb = 0, qe = 0;
        for (int j = 0; j < c[i].s; ++j) {
            for (; qb < qe && que[qe - 1].first <= f[i - 1][j] - c[i].p * j; --qe) ;
            que[qe++] = std::make_pair(f[i - 1][j] - c[i].p * j, j);
        }
        for (int j = 1; j <= n; ++j) {
            f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
            if (c[i].s <= j && j < c[i].s + c[i].l) {
                for (; qb < qe && que[qb].second < j - c[i].l; ++qb) ;
                f[i][j] = std::max(f[i][j], que[qb].first + c[i].p * j);
            }
        }
    }
    printf("%d\n", f[k][n]);
    return 0;
}