题解：P12225 [蓝桥杯 2023 国 Java B] 游戏

· · 题解

P12225 [蓝桥杯 2023 国 Java B] 游戏

看没有 ST 表的，写一个。

首先，是 ST 表板子求区间最大最小值，然后对于每个长度为 k 的区间，最大值记为 P_i, 最小值记为 Q_i，题目要求的期望就是这玩意：

\sum_{i = 1}^{n - k + 1} \sum_{j = 1}^{n - k + 1} \frac{1}{(n - k + 1) ^ 2}(P_i - Q_j)

然后就稍微化简一下就好了：

\begin{aligned} & \sum_{i = 1}^{n - k + 1} \sum_{j = 1}^{n - k + 1} \frac{1}{(n - k + 1) ^ 2}(P_i - Q_j) \\ = & \frac{1}{(n - k + 1) ^ 2} \sum_{i = 1}^{n - k + 1} \sum_{j = 1}^{n - k + 1} (P_i - Q_j) \\ = & \frac{1}{(n - k + 1) ^ 2}[(n - k + 1)\sum_{i = 1}^{n - k + 1}P_i - (n - k + 1)\sum_{i = 1}^{n - k + 1}Q_i] \\ = & \frac{1}{n - k + 1}(\sum_{i = 1}^{n - k + 1}P_i - \sum_{i = 1}^{n - k + 1}Q_i) \end{aligned}

所以最后只需要记录 \sum_{i = 1}^{n - k + 1}P_i 和 \sum_{i = 1}^{n - k + 1}Q_i 即最大值和以及最小值和就行了。

时间复杂度 \mathcal{O}(n \log n)，能过的。

当然，不开那个什么还是会见祖宗的。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; i++) 
#define rrep(i, r, l) for (int i = r; i >= l; i--)
#define lrep(i, from, nxt) for (int i = from; i; i = nxt)
#define arep(x, s) for (auto &x : s)
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define pqueue priority_queue
#define umap unordered_map
using ll = long long;

int rd() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0', ch = getchar();
    }
    return x * f;
}

constexpr int N = 1e5 + 10;
ll n, k, mx[N][25], mn[N][25], lg[N], sp, sq;

int main() {
    n = rd(), k = rd();
    lg[0] = -1;
    rep(i, 1, n) {
        mx[i][0] = mn[i][0] = rd();
        lg[i] = lg[i / 2] + 1;
    }
    rep(j, 1, 20) {
        rep(i, 1, n - (1 << j) + 1) {
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
        }
    }
    rep(i, 1, n - k + 1) {
        int l = i, r = i + k - 1, s = lg[k];
        sp += max(mx[l][s], mx[r - (1 << s) + 1][s]);
        sq += min(mn[l][s], mn[r - (1 << s) + 1][s]);
    }
    printf("%.2lf\n", 1.0 * (sp - sq) / (n - k + 1));
    return 0;
}

Java 的：

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 100010;
    static long n, k, sp, sq;
    static long[][] mx = new long[N][25];
    static long[][] mn = new long[N][25];
    static int[] lg = new int[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        lg[0] = -1;
        for (int i = 1; i <= n; i++) {
            mx[i][0] = mn[i][0] = scanner.nextInt();
            lg[i] = lg[i / 2] + 1;
        }
        for (int j = 1; j <= 20; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                mx[i][j] = Math.max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
                mn[i][j] = Math.min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
            }
        }
        for (int i = 1; i <= n - k + 1; i++) {
            int l = i, r = i + (int) k - 1, s = lg[(int) k];
            sp += Math.max(mx[l][s], mx[r - (1 << s) + 1][s]);
            sq += Math.min(mn[l][s], mn[r - (1 << s) + 1][s]);
        }
        System.out.printf("%.2f\n", 1.0 * (sp - sq) / (n - k + 1));
        scanner.close();
    }
}

对了，一开始我写单调队列不小心卡了一个最优解。