E. Drinking

观察一下不难发现，任意一端区间$g(l,r)=\sum\limits_{i=1}^nx_{(i)}\frac{1}{2^i},x(i)$表示区间内第$i$大的值，由于误差要求$<10^{-6}$，所以估一下只要取区间最大的T=50个数

自然想到单独计算每个数对答案的贡献。设第$i$个数左边比它大的数从右到左为$l_1,l_2,\cdots,l_T$，右边比它大的数从左往右为$r_1,r_2,\cdots,r_T$，那么每个数的贡献为

$val_i=w_i\sum\limits_{u=1}^T\sum\limits_{v=1}^T(l_{u-1}-l_u)(r_v-r_{v-1})\frac{1}{2^{u+v-1}}$

然后发现可以把u、v分离出来

$val_i=2w_i\sum\limits_{u=1}^T\frac{l_{u-1}-l_u}{2^u}\sum\limits_{v=1}^T\frac{r_v-r_{v-1}}{2^v}$

从小到大用链表维护一下，可以找到每个数左边和右边比它大的、最近的T个数，计算完之后从链表里删掉，复杂度$O(n)$，常数<=100

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << '\n'

using namespace std;

const int N = 1e6 + 5;

int n, w[N], pre[N], nxt[N], ord[N];

double ans;

void Remove(int x) {
    nxt[pre[x]] = nxt[x];
    pre[nxt[x]] = pre[x];
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i++) ord[i] = i;
    sort(ord + 1, ord + 1 + n, [&](int u, int v) {
        return w[u] < w[v];
    });
    for (int i = 1; i <= n; i++) pre[i] = i - 1, nxt[i] = i + 1;
    nxt[0] = 1, pre[n + 1] = n;
    pre[0] = nxt[n + 1] = -1;
    for (int i = 1; i <= n; i++) {
        double fct1, fct2, rat;
        fct1 = fct2 = 0;
        rat = 0.5;
        for (int j = 1, now = pre[ord[i]]; j <= 50 && now != -1; j++, now = pre[now]) {
            fct1 += (nxt[now] - now) * rat;
            rat /= 2;
        }
        rat = 0.5;
        for (int j = 1, now = nxt[ord[i]]; j <= 50 && now != -1; j++, now = nxt[now]) {
            fct2 += (now - pre[now]) * rat;
            rat /= 2;
        }
        ans += w[ord[i]] * 2 * fct1 * fct2;
        Remove(ord[i]);
    }
    printf("%.6f\n", ans / n / n);
    return 0;
}

F.Mathematics

递推式$f_n=1-nf_{n-1}$

正着递推误差会不断放大，然后很快就爆炸了

但是反着推$f_{n-1}=\frac{1-f_n}{n}$误差会不断缩小，所以可以假设$f_{20000}=0$（这个误差本身就非常小），然后反着推出$f_n$

#include <bits/stdc++.h>

using namespace std;

double ans;

int n;

int main() {
    cin >> n;
    for (int i = 20000; i >= n + 1; i--) {
        ans = (1 - ans) / i;
    }
    printf("%.4f\n", ans);
    return 0;
}