I. Slow Leak

题意

$n$ 个节点的带权无向图中有 $m$ 条边，有一个汽车从 $1$ 出发要到 $n$，汽车有油箱，油箱一开始是满的，最多可以装 $d$ 升油。

每走 $1$ 单位距离就要消耗 $1$ 升油，图中有 $t$ 个节点是加油站，分别为 $a_1,a_2,…,a_t$。

求 $1$ 到 $n$ 的最短路径？如果不可能，输出 “stuck”。

其中，$n \in [2, 500], m \in (0, \frac{n(n-1)}{2}], t \in (0, n), d \in (0, 2^{31})$

题解

经典套路题：两次最短路。

加油站是关键，如果把 $1,n$ 也视作加油站，那么最后求出的路径一定是以加油站作为关键节点，从 $1$ 到 $n$ 的。

不妨考虑建立一个只有加油站的图，怎么建立呢？

首先，跑一个 floyd 最短路求出每两点之间的最短距离。

然后，只保留加油站进行建图，如果两个加油站之间的距离 $\leq d$，就连一条边。

再跑一次最短路即可。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;

int n, m, t, d;
bool gas[maxn];
ll dp[maxn][maxn];
ll dp2[maxn][maxn];
int main() {
    fastio;
    cin >> n >> m >> t >> d;
    for (int i = 1; i <= t; i++) {
        int x; cin >> x;
        gas[x] = 1;
    }
    gas[1] = 1;
    gas[n] = 1;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++) dp[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        int u,v,w; cin >> u >> v >> w;
        if (w <= d) {
            dp[u][v] = dp[v][u] = w;
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if ((dp[i][k] >= 0 && dp[k][j] >= 0)) {
                    if (dp[i][j] < 0) dp[i][j] = dp[i][k] + dp[k][j];
                    else if (dp[i][k] + dp[k][j] < dp[i][j]) dp[i][j] = dp[i][k] + dp[k][j];
                }
            }
        }
    }

    memset(dp2, -1, sizeof(dp2));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (gas[i] && gas[j] && dp[i][j] <= d) {
                dp2[i][j] = dp[i][j];
            }
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (gas[i] && gas[j] && gas[k]) {
                    if ((dp2[i][k] >= 0 && dp2[k][j] >= 0)) {
                        if (dp2[i][j] < 0) dp2[i][j] = dp2[i][k] + dp2[k][j];
                        else if (dp2[i][k] + dp2[k][j] < dp2[i][j]) dp2[i][j] = dp2[i][k] + dp2[k][j];
                    }
                }
            }
        }
    }

    if (dp2[1][n] >= 0) cout << dp2[1][n] << endl;
    else cout << "stuck\n";
}

J. Stop Counting!

题意

给定一个 $n$ 个元素的整数数组 $a_1,…,a_n$，求：

$$\max\limits_{L \in [0,n], R \in [L+1, n]} \frac{(a_1+a_2+…a_L) + (a_R + a_{R+1} + a_n)}{L + (n-R+1)}$$

即：求左边一段加右边一段，使得平均值最大。

其中，$n \in [1, 10^6], a_i \in [-10^9, 10^9]$，要求答案的绝对误差在 $10^{-6}$ 以内或者相对误差在 $10^{-9}$ 以内。

题解

经典套路题，看见 最大/最小平均值 就想到 二分答案。

即二分答案，然后给所有元素减去这个值，判断是否存在左边一段加上右边一段的和 $\geq 0$ 即可，也就转变成求最小和的 subarray。

这题主要的坑在于不能用绝对误差，得用相对误差！因为绝对误差在数字较大的时候精度不够！

long double low = 0.0, high = 1e9;  // 应该用 long double！
while (high - low > 1e-7) {  // 这样写是错误的！
    double mid = (low + high) * 0.5;
    if (check(mid)) {
        low = mid;
        ans = mid;
    } else {
        high = mid;
    }
}

如上是不行的，注意到相对误差的定义是：如果答案为 $x$，相对误差为 $10^{-9}$，意味着答案在 $(x (1-10^{-9}), x (1+10^{-9}))$ 之间。

所以在答案可能较大时，应该限制二分次数 $T$，如下：

long double low = 0.0, high = 1e9;  // long double 是正确的
int T = 100;
while (high - low > 1e-7 && T--) {  // 当相对误差 <= 1e-7 或者 次数超过 100次就停下来
    long double mid = (low + high) * 0.5;
    if (check(mid)) {
        low = mid;
        ans = mid;
    } else {
        high = mid;
    }
}
代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;
int n;
int a[maxn];
// 是否存在大于0的subarray (左右两边)
double sm[maxn];
bool check(double x) {
    double mn = 0;
    double res = 1e18;
    for (int i = 1; i <= n-1; i++) {
        sm[i] = sm[i-1] - x + (double)a[i];
        mn = max(mn, sm[i]);
        res = min(res, sm[i] - mn);
    }
    sm[n] = sm[n-1] - x + (double)a[n];
    for (int j = 1; j <= n; j++) {
        res = min(res, sm[n] - sm[j]);
    }

    return sm[n] - res >= 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    long double ans = 0.0;
    long double low = 0.0, high = 1e9;
    int T = 100;
    while (high - low > 1e-7 && T--) {  // 当相对误差 <= 1e-7 或者 次数超过 100次就停下来
        long double mid = (low + high) * 0.5;
        if (check(mid)) {
            low = mid;
            ans = mid;
        } else {
            high = mid;
        }
    }
    printf("%.15lf\n", ans);
}