2021-08-20 16:19 中国海洋大学 C++

关注

2021牛客暑期多校训练营4

B、Sample Game

题目大意

你有一个随机数生成器，他会随机生成 $1$ 到 $n(1\le n\le 100)$ 之间某个数，生成 $i$ 的概率为 $p_i$ 。

现在分为大体 $3$ 步操作：

随机生成一个 $x$ 。
如果这个 $x$ 是已经生成的数中最大的，返回步骤一继续生成新的数，否则进入步骤三
游戏结束，本局游戏的得分为生成序列的长度的平方 $y^2$ 。

现在要你求出这局游戏的得分期望 $E(y^2)$ 。

Solution

考点：期望dp

$E(y^2)$ 这个期望不是很好求，我们优先考虑求出 $E(y)$ 。

我们假设 $f_x$ 是随机到 $x$ 后还能进行的期望抽取次数，那么我们知道 $E(y)=f_y+1$ ，那么我们把之后的抽取分为 $(1\to (x-1)),x,((x+1)\to n)$ 这三类，可以知道，抽到 $1\to (x-1)$ 之后就无法进行了这时候的期望次数就是 $\sum\limits_{i=1}^{x-1}p_i*1$ ，如果抽到了相同的数 $x$ ，这时候他带来的期望次数就是 $p_x(1+f_x)$ ，如果抽到了 $((x+1)\to n)$ ，他们的期望次数是 $\sum\limits_{i=x+1}^n p_i(1+f_i)$ 。

我们总结上面三种情况就可以得到下面式子：

$f_x=\sum\limits_{i=1}^{x-1}p_i+p_x(1+f_x)+\sum\limits_{i=x+1}^np_i(1+f_i)$

进行移相化简，并且知道 $\sum\limits_{i=1}^np_i = 1$ 之后我们可以得到这样的最终式子。

$\displaystyle f_x=\frac{1+\sum\limits_{i=x+1}^np_if_i}{1-p_x}$

看出这个是一个倒序的递推式，倒序的处理即可求到 $f_x$ 的全部值，也就是 $E(y)$ 。

接下来题目要求的是 $E(y^2)$ 的期望，在概率论中，有这样的式子 $D(y)=E(y^2)-E(y)^2$ ，也就是方差等于平方的期望减掉期望的平方，所以我们不能把 $E(y^2)$ 和 $E(y)^2$ 划等号。

和求 $f_x$ 同理，我们假设 $g_x$ 代表随机到 $x$ 后游戏的期望得分也就是剩余回合数的平方，那么我们知道 $E(y^2)=(f_y+1)^2=f_y^2+2f_y+1=g_y+2f_y+1$ 。

和 $f_x$ 同样的对下次抽取的数字以 $x$ 分三类情况，可以得到 $g_x$ 的递推式。

$\displaystyle g_x=\sum\limits_{i=1}^{x-1}p_i+p_x(g_x+2f_x+1)+\sum\limits_{i=x+1}^np_i(g_i+2f_i+1)\\g_x=\frac{1+2p_xf_x+\sum\limits_{i=x+1}^np_i(g_i+2f_i)}{1-p_x}$

同样的倒序递推就可以得到 $g_x$ 全部的值。

下面套用我们求解 $ans =\sum\limits_{i=1}^n p_i* E(i^2)=\sum\limits_{i=1}^np_i(g_i+2f_i+1)=1+\sum\limits_{i=1}^np_i(g_i+2f_i)$

套用快速幂和费马小定理求解逆元就出来答案了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int MOD = 998244353;

const int N = 100 + 7;
ll n, m;
int w[N], p[N], inv[N];
int f[N], g[N];

inline int add(int a, int b) {
    if (a + b >= MOD)    return a + b - MOD;
    return a + b;
}

int solve() {
    n = read();
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        w[i] = read();
        sum += w[i];
    }
    int tmp = qpow(sum % MOD, MOD - 2, MOD);
    for (int i = 1; i <= n; ++i) {
        p[i] = w[i] * tmp % MOD;
        inv[i] = qpow((1 - p[i] + MOD) % MOD, MOD - 2, MOD);
    }
    sum = 0;
    for (int i = n; i >= 1; --i) {
        f[i] = add(1, sum) * inv[i] % MOD;
        sum = add(sum, p[i] * f[i] % MOD);
    }
    sum = 0;
    for (int i = n; i >= 1; --i) {
        g[i] = add(add(1, 2 * p[i] * f[i] % MOD), sum) * inv[i] % MOD;
        sum = add(sum, p[i] * add(g[i], 2 * f[i] % MOD) % MOD);
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        res = add(res, add(g[i], (2 * f[i] + 1) % MOD) * p[i] % MOD);
    }
    print(res);

    return 1;
}

signed main() {
    //int T = read(); for (int i = 1; i <= T; ++i)
    {
        solve();
        //cout << (solve() ? "YES" : "NO") << endl;
    }
    return 0;
}

C、LCS

题目大意

你需要构造 $3$ 个长度为 $n$ 的字符串 $s_1,s_2,s_3$ ，并且保证 $LCS(s_1,s_2)=a,LCS(s_2,s_3)=b,LCS(s_1,s_3)=c$ 。

$1\le n\le 10^3$

Solution

考点：模拟

我们先不考虑输出顺序，只考虑是否能够构建，我们把 $a,b,c$ 变成 $a\ge b\ge c$ 的形式进行一次排序。

那么我们可以想到下图这样的构建方式是最合理的：

图片说明

接下来就是找出最小的字母，然后确定这三个字符串的位置了。

int solve() {
    string s1, s2, s3;
    int a = read(), b = read(), c = read(), n = read();

    int maxi = max({ a,b,c });
    int mini = min({ a,b,c });
    int tmp = a ^ b ^ c ^ maxi ^ mini;

    if (maxi + tmp - mini > n) {
        return puts("NO"), 0;
    }

    if (mini == b) {
        for (int i = 1; i <= b; ++i) {
            s1 += 'a', s2 += 'a', s3 += 'a';
        }
        for (int i = 1; i <= a - b; ++i) {
            s1 += 'b', s2 += 'b';
        }
        for (int i = 1; i <= c - b; ++i) {
            s1 += 'c', s3 += 'c';
        }
        while (s1.size() < n)    s1 += 'd';
        while (s2.size() < n)    s2 += 'e';
        while (s3.size() < n)    s3 += 'f';
    }
    else if (mini == c) {
        for (int i = 1; i <= c; ++i) {
            s1 += 'a', s2 += 'a', s3 += 'a';
        }
        for (int i = 1; i <= a - c; ++i) {
            s1 += 'b', s2 += 'b';
        }
        for (int i = 1; i <= b - c; ++i) {
            s2 += 'c', s3 += 'c';
        }
        while (s1.size() < n)    s1 += 'd';
        while (s2.size() < n)    s2 += 'e';
        while (s3.size() < n)    s3 += 'f';
    }
    else if (mini == a) {
        for (int i = 1; i <= a; ++i) {
            s1 += 'a', s2 += 'a', s3 += 'a';
        }
        for (int i = 1; i <= b - a; ++i) {
            s2 += 'b', s3 += 'b';
        }
        for (int i = 1; i <= c - a; ++i) {
            s1 += 'c', s3 += 'c';
        }
        while (s1.size() < n)    s1 += 'd';
        while (s2.size() < n)    s2 += 'e';
        while (s3.size() < n)    s3 += 'f';
    }
    cout << s1 << endl;
    cout << s2 << endl;
    cout << s3 << endl;

    return 1;
}

E、Tree Xor

题目大意

你有一个一颗树节点数 $n(1\le n\le 10^5)$ ，树上的边有一个边权 $w$ ，点有一个点权 $a_i$ ，你要保证有直接父子关系的点之间 $a_u \oplus a_v = w$ ，并且树上每个点他的点权选取范围为 $[l_i,r_i]$ ，现在请问你能构造出多少颗不同的树，有任何一个 $a_i$ 不同就认为是一颗不同的树。

Solution

考点：线段树区间性质

首先树上边权关系给你了，所以当我们顶下 $a_1$ 后整棵树后续的 $a_i$ 都会被确定下来，问题就转化成 $a_i$ 有多少种取值可能。

好，下面我们假设 $a_1 = 0$ 求一遍 $dfs$ ，这样就可以预处理出每个点的 $b_i$ ，我们就可以把题目的区间变成下面的形式。

$l_1 \le a_1 \le r_1\\l_2\le b_2\oplus a_2\le r_2\\l_3\le b_3\oplus a_3\le r_3\\...$

那么 $l_i,r_i,b_i$ 全部已知，问题就变成了 $n$ 个区间求并集的问题，并集的大小就是答案了。

但是由于是异或操作，所以本身连续的 $[l_i,r_i]$ 在异或 $b_i$ 之后整个区间并不会保持连续，下面我们就要想办法处理出这些分散的区间来。

然后就要想到这个题目的难点了，用线段树的区间性质考虑新建区间，因为线段树最多会分成 $\log$ 段区间，并且每段区间都有很明显的前后一致的相关性，那么我们就在线段树上找到这些被 $[l_i,r_i]$ 包含的区间，然后把他们处理好之后塞进容器里面，最终求解有没有某些部分是 $n$ 个区间相同的并集，这个用一次扫描线即可。

[借用一下这位大佬(lalalzo)的图](2021牛客第四场-E Tree Xor-线段树区间异或_lalalzo的博客-CSDN博客)

图片说明

const int N = 1e5 + 7;
ll n, m;
pai p[N];
vector<pai> G[N];
int a[N];

void dfs(int u, int fa) {
    for (auto& [v, w] : G[u]) {
        if (v == fa)    continue;
        a[v] = a[u] ^ w;
        dfs(v, u);
    }
}

vector<pai> seg;
int bit[40];
#define mid (l + r >> 1)
void build(int l, int r, int cnt, int L, int R, int val) {
    if (L <= l && r <= R) {
        int ql = (l ^ val) & bit[cnt];
        int qr = ql + (1 << cnt) - 1;
        seg.push_back({ ql,qr });
        return;
    }
    if (L <= mid)    build(l, mid, cnt - 1, L, R, val);
    if (R > mid)    build(mid + 1, r, cnt - 1, L, R, val);
}

int solve() {
    bit[0] = (1 << 30) - 1;
    for (int i = 1; i <= 30; ++i) {
        bit[i] = bit[i - 1] ^ (1 << (i - 1));
    }
    n = read();
    for (int i = 1; i <= n; ++i)    p[i] = { read(), read() };
    int u, v, w;
    for (int i = 2; i <= n; ++i) {
        u = read(), v = read(), w = read();
        G[u].push_back({ v,w });
        G[v].push_back({ u,w });
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) {
        build(0, bit[0], 30, p[i].first, p[i].second, a[i]);
    }
    vector<pai> all;
    for (auto& [l, r] : seg) {
        all.push_back({ l,1 });
        all.push_back({ r + 1,-1 });
    }
    sort(all.begin(), all.end());
    int res = 0, tag = 0;
    for (int i = 0; i < all.size(); ++i) {
        tag += all[i].second;
        if (tag == n) {
            res += all[i + 1].first - all[i].first;
        }
    }
    print(res);


    return 1;
}

F、Just a joke

题目大意

$Alice$ 和 $Bob$ 两人在进行游戏，每轮游戏操作的玩家可以选择图中的一条边删去，或者找到图中的一棵树删去，最后无法进行操作的玩家就输掉了这局比赛，这张图是有 $n$ 个点 $m$ 条边的无向图。

Solution

我们分别考虑每个操作的势能函数。

删边： $G_1(n) = 0 + 1$ ， $0$ 是删掉的点数， $1$ 是删掉的边数， $G_1(n)$ 任何时候都为奇数。

删树： $G_2(n)=n + (n-1)=2n-1$ ，可以看出 $G_2(n)$ 任何时候也为奇数。

那么这局游戏双方轮流操作，每个人都只能选择 $G_1$ 或者 $G_2$ ，说明最终 $n+m$ 变成 $0$ 的操作次数是确定的，直接判断 $n+m$ 的奇偶性即可。

int solve() {
    n = read(), m = read();

    return ((n + m) & 1);
}

int main() {
    //int T = read();    rep(_, 1, T)
    {
        //solve();
        cout << (solve() ? "Alice" : "Bob") << endl;
    }
    return 0;
}

G、Product

题目大意

给出 $n,k,D$ ，你要构造的序列 $a_i\ge 0,\sum\limits_{i=1}^na_i = D$ ，对于其中一个序列 $a$ 来说他的贡献是 $\displaystyle\frac{D!}{\prod\limits_{i=1}^n(a_i+k)!}$ ，现在要你求出全部可能的 $a$ 序列贡献之和是多少？

$n,k\le50,D\le10^8$

Solution

考点：动态规划+容斥原理+组合数意义

我们首先要推出下面这样的一个式子，可以看出这是 $D$ 个球分成 $n$ 组的可能方案数，那么总的方案数就是 $n^D$ ，即每个球都可能在每一组。

$\sum\limits_{i=1}^na_i = D \ \ \ (a_i\ge 0)\\D!*\prod\limits_{i=1}^n\displaystyle\frac{1}{a_i} = n^D$

好，我们回来看题目给出的式子，我们如果把 $a_i+k$ 看成一个整体带入我们刚刚上面推出的公式我们就会得到这样的式子。

$\sum\limits_{i=1}^na_i = D+nk \ \ \ (a_i\ge 0)\\(D+nk)!*\prod\limits_{i=1}^n\displaystyle\frac{1}{a_i} = n^{D+nk}$

但是很容易发现一个问题就是题目给出的 $a_i$ 范围是 $\ge k$ 的但是我们公式的范围是 $\ge 0$ 的，这就会导致我们直接计算答案的话会出现很多非法的解，那么我们就要考虑把这些非法的解全部去掉，就要用到容斥原理了。

那么我们知道我们一共有 $n$ 组，那么起始 $0$ 组非法的答案减掉有 $1$ 组非法答案的解加上有 $2$ 组非法答案的解 $…$ 直到容斥系数被算完为止，好那么问题就转换为如何求解有 $i$ 组非法答案的解的数量呢？

这个求解就比较容易了，考虑动态规划 $f[i][j]$ 代表对于前 $i$ 组当前有 $j$ 个球要分配而言非法答案的方案数。

我们使用三重循环枚举就可以求道这个 $f$ 数组。

$f[0][0] = 1\\\\f_{i,j}=\sum\limits_{s=0}^{k-1}f_{i-1,j-s}*C_j^s$

接下来答案就会是下面这个式子，从前往后依次是计算答案的修正系数，容斥系数，有多少组非法，多少个球非法并且都要计算组合数，最后是剩余组剩余球合法的方案数。

$\displaystyle\frac{D!}{(D+nk)!}\sum\limits_{i=0}^n(-1)^i\sum\limits_{j=0}^{i*(k-1)}f_{i,j}*C_n^i*C_{D+nk}^j*(n-i)^{D+nk-j}$

ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int MOD = 998244353;
const int N = 55 + 7;
ll n, k, D;
int C[N * N][N * N];
int f[N][N * N];

inline int add(int a, int b) {
    if (a + b >= MOD)    return a + b - MOD;
    return a + b;
}

void init() {
    for (int i = 0; i < N * N; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
        }
    }
    f[0][0] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= i * (k - 1); ++j)
            for (int s = 0; s <= k - 1; ++s)
                f[i + 1][j + s] = add(f[i + 1][j + s], f[i][j] * C[j + s][s] % MOD);
}

inline int inv(int x) {
    return qpow(x, MOD - 2, MOD);
}

int solve() {
    n = read(), k = read(), D = read();
    init();

    int res = 0;
    for (int i = 0; i <= n; ++i) {
        int jc = 1;
        int sum = 0;
        int pre = (i & 1) ? MOD - C[n][i] : C[n][i];

        for (int j = 0; j <= i * (k - 1); ++j) {
            int tmp = f[i][j] * qpow(n - i, D + n * k - j, MOD) % MOD * jc % MOD;
            sum = add(sum, tmp);
            jc = jc * ((D + n * k - j) % MOD) % MOD * inv(j + 1) % MOD; // D太大了
        }

        res = add(res, sum * pre % MOD);
    }

    for (int i = D + 1; i <= D + n * k; ++i) {
        res = res * inv(i) % MOD;
    }
    print(res);



    return 1;
}

H、Convolution

题目大意

题目重新定义了 $\otimes$ 运算符： $\displaystyle x=\prod p_i^{a_i},y = \prod p_i^{b_i},x \otimes y = \prod p_i^{|a_i-b_i|}$

并且给出长度为 $n(1\le n\le 10^6)$ 的 $a_i$ ，以及常数 $c(1\le c\le10^9)$ ，定义 $\displaystyle b_i=\sum\limits_{1\le j,k\le n, j\otimes k=i}a_jk^c$

我们需要求解 $b_1...b_n$ 的异或和是多少？

Solution

参考题解

我们优先就要转换这个 $\otimes$ 符号的定义，不然这个题目就没办法下手了。

$\displaystyle x\otimes y=\prod p_i^{|a_i-b_i|}=\prod p_i^{max(a_i.b_i)-min(a_i,b_i)}=\frac{lcm(x,y)}{\gcd(x,y)}=\frac{xy}{\gcd(x,y)}$

从质因数幂次的关系转换到 $x,y$ 和他们对应 $\gcd$ 之间的关系就更加容易处理 $j\otimes k = i$ 这个关系式了。

那么我们重新写出 $b_i$ 的定义式

$b_i=\displaystyle \sum\limits_{j=1}^n\sum\limits_{k=1}^n\sum\limits_{\frac{jk}{\gcd(j,k)}=i}a_jk^c$

我们考虑枚举 $g=\gcd(j,k)$

$\displaystyle b_i = \sum\limits_{j=1}^n\sum\limits_{k=1}^n\sum\limits_{g=1}\sum\limits_{\frac{jk}{g^2}=i}a_jk^c$

这样由于最后一个求和条件还是涉及除法，我们再把这个除法消掉，我们设 $x=\frac{j}{g},y=\frac{k}{g}$

$\displaystyle b_i=\sum\limits_{x=1}^n\sum\limits_{y=1}^n\sum\limits_{g=1}^{\min(\frac{n}{x},\frac{n}{y})}\sum\limits_{xy=i}a_{xg}(yg)^c\\$

然后可以发现最后面的 $y^c$ 可以提到前面去，最终把式子写成这样

$\displaystyle b_i=\sum\limits_{xy=i}y^c\sum\limits_{g=1}^{\min(\frac{n}{x},\frac{n}{y})}a_{xg}g^c$

计算答案的时候我们枚举 $x$ ，对于 $x*y=n$ 来说，可能的 $y$ 选择长度是 $n+\frac{n}{2}+\frac{n}{3}...+\frac{n}{n}$ ，这个复杂度是 $n\log(n)$ ，然后根据选择的 $y$ ，又可以确定的更新 $i$ 所以全部的 $b_i$ 都可以在 $O(n\log(n))$ 的时间找到。

还需要注意的一点是，由于原先我们定义的是 $\frac{jk}{\gcd(jk)}=i$ ，现在我们改成了 $xy=i$ 那么在 $x,y$ 之间就不能有任何其他的公因子了，例如 $x=2,y=4,g=2$ ，这样的不能现在计算，因为这样的式子后续一定会枚举到 $x=1,y=2,g=4$ ，其实这样这些对应着都是 $j=4,k=8$ ，那么我们就要避免这样的重复计算，我们当且仅当 $\gcd(x,y)=1$ 的时候计算一下 $b_{xy}$ 的值就能保证不多算。

const int MOD = 998244353;
const int N = 1e6 + 7;
ll n, c, a[N];
int p[N], f[N], b[N];

inline int add(int a, int b) {
    if (a + b >= MOD)    return a + b - MOD;
    return a + b;
}

int solve() {
    n = read(), c = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        p[i] = qpow(i, c, MOD);
    }
    for (int x = 1; x <= n; ++x) {
        for (int g = 1; g * x <= n; ++g) {
            f[g] = add(f[g - 1], p[g] * a[x * g] % MOD);
        }
        for (int y = 1; x * y <= n; ++y) {
            if (gcd(x, y) == 1) {
                b[x * y] = add(b[x * y], p[y] * f[min(n / x, n / y)] % MOD);
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i)    res ^= b[i];
    print(res);

    return 1;
}

I、Inverse Pair

题目大意

给你一个初始的排列 $a_i$ ，你可以选择 $a_i$ 的任意多位置加上一个 $1$ ，输出最终这个 $a_i$ 的最小的逆序对数目。

Solution

考点：思维+求逆序对数量

我们考虑哪些位置加了 $1$ 之后他对答案的贡献会减少。

是不是需要一个 $x-1$ 存在，并且他在 $x$ 的后面，这时候我们把 $x-1$ 变成 $x$ 就可以减少逆序数。

所以我们从 $2$ 到 $n$ 遍历如果我们把某个 $i-1$ 变成了 $i$ ，那么我们就要打上标记让 $i$ 不能再变成 $i+1$ 不然就会套娃最终只会让逆序数 $-1$ ，然后求逆序数就用树状数组算一次就行了。

const int N = 2e5 + 7;
ll n;
int c[N];

inline int lowbit(int x) { return x & (-x); }
void add(int i, int x) {
    for (; i <= n; i += lowbit(i))    c[i] += x;
}
int query(int i) {
    int res = 0;
    for (; i; i -= lowbit(i)) {
        res += c[i];
    }
    return res;
}

int pos[N], a[N];
bool vis[N];

int solve() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        pos[a[i]] = i;
    }
    for (int i = 2; i <= n; ++i) {
        if (!vis[i - 1] && pos[i - 1] > pos[i]) {
            vis[i] = 1;
            ++a[pos[i - 1]];
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        res += i - 1 - query(a[i]);
        add(a[i], 1);
    }
    print(res);

    return 1;
}

J、Average

题目大意

你有一个 $n·m$ 的矩阵 $W$ ，这个矩阵的 $W_{i,j}=a_i+b_j$ ， $a,b$ 序列给出。

你要再这个矩阵中挑选一个纵向长度大于等于 $x$ ，横向长度大于等于 $y$ 的子矩阵，求子矩阵的最大平均值。

Solution

考点：二分+动态规划

我们假设我们就选择了一个大小为 $n·m$ 的子矩阵，重新编号之后可以发现这个子矩阵的平均数就等于下面。

$\displaystyle avg = \frac{m·\sum\limits_{i=1}^na_i+n·\sum\limits_{j=1}^{m}b_j}{n·m}$

那么再裂项之后我们可以知道

$avg = \displaystyle\frac{\sum\limits_{i=1}^na_i}{n}+\frac{\sum\limits_{j=1}^mb_j}{m}$

那么要 $\max$ 化平均数只需要前后都取最大值即可，那么题意就变成了要找到在序列里面选择长度大于 $L$ 的最大平均数。

典中典问题，二分平均数+动态规划判断答案是否存在即可。

稍微提一下动态规划如何判断，我们二分出之后，我们把序列中的数全部减掉 $mid$ 就变成了要在序列中找出一个大于等于 $L$ 的和大于等于 $0$ 的子区间。

那么我们维护一个 $i-L$ 的最小的前缀和，用 $sum[i]-mini$ 就可以线性找到区间最大值。

const int N = 1e6 + 7;
ll n, m, x, y;
int a[N], b[N];
double c[N];

const double eps = 1e-8;

bool check(int* a, int n, int L, double mid) {
    c[0] = 0;
    for (int i = 1; i <= n; ++i) {
        c[i] = c[i - 1] + a[i] - mid;
    }
    double ans = -INF64, mini = INF64;
    for (int i = L; i <= n; ++i) {
        mini = min(mini, c[i - L]);
        ans = max(ans, c[i] - mini);
    }
    return ans >= 0;
}

int solve() {
    n = read(), m = read(), x = read(), y = read();
    for (int i = 1; i <= n; ++i)    a[i] = read();
    for (int i = 1; i <= m; ++i)    b[i] = read();

    double l = -1, r = 1e5 + 7, res1 = 0, res2 = 0;

    for (int i = 0; i <= 100; ++i) {
        double mid = (l + r) / 2;
        if (check(a, n, x, mid)) {
            res1 = mid;
            l = mid;
        }
        else
            r = mid;
    }

    l = -1, r = 1e5 + 7;
    for (int i = 0; i <= 100; ++i) {
        double mid = (l + r) / 2;
        if (check(b, m, y, mid)) {
            res2 = mid;
            l = mid;
        }
        else
            r = mid;
    }

    printf("%.10f\n", res1 + res2);

    return 1;
}

2021牛客暑期多校训练营文章被收录于专栏

））补题-ing