测试文章

域名备案终于过审了²

测试一下代码与 latex

第二题手抖把 r 写成 l 了 orz

70 + 40 + 100，rk 7

A 赛艇表演

给出一个边权，点权无向连通图，对于每个 u 求 \displaystyle\min_{i = 1}^n \text{dis}(u, v) * 2 + w_v

n \leq 2*10^5

图论建模，最短路

考虑建模

先将所有边权乘 2，建出超级源点 s，从 s 向每个点连一条边权为其点权的边，s 到该点的最短路即为其答案

时间复杂度 O((n + m) \log n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
const int maxn = 4e5 + 10, maxm = 4e5 + 10;
int n, m, s;

int cnt, head[maxn];
struct edge { int nxt, to; ll w; } e[maxm << 2];
void add(int u, int v, int w) { e[++cnt].to = v, e[cnt].w = w, e[cnt].nxt = head[u], head[u] = cnt; }

ll w[maxn], dis[maxn];
bool vis[maxn];
void dij() {
    priority_queue<pii, vector<pii>, greater<pii> > f;
    for (int i = 1; i <= n + 1; ++i) dis[i] = LONG_LONG_MAX;
    dis[s] = 0, f.push(make_pair(0, s));
    while (!f.empty()) {
        int now = f.top().second; f.pop();
        if (vis[now]) continue;
        vis[now] = true;
        for (int i = head[now]; i; i = e[i].nxt) { int v = e[i].to;
            if (dis[v] > dis[now] + e[i].w) dis[v] = dis[now] + e[i].w, f.push(make_pair(dis[v], v));
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, u, v; i <= m; ++i) { ll w;
        scanf("%d %d %lld", &u, &v, &w);
        add(u, v, w << 1), add(v, u, w << 1);
    }
    for (int i = 1; i <= n; ++i) scanf("%lld", &w[i]);
    for (int i = 1; i <= n; ++i) add(n + 1, i, w[i]), add(i, n + 1, w[i]);
    s = n + 1;
    dij();
    for (int i = 1; i <= n; ++i) printf("%lld ", dis[i]);
    return 0;
}

如果多次最短路会导致错误的复杂度，就考虑建模

B 逮虾户

求解关于 x 的方程

二分答案

单调性显然

二分即可

时间复杂度 O(n \log 10^9)

#include <bits/stdc++.h>
using namespace std;
typedef long double db;
const int maxn = 1000 + 10;
const db eps = 1e-9;
const db inf = 1e17;
int n;
db f, s[maxn], t[maxn], mx = -0x7fffffff, ans;

db check(db x) {
    db res = 0;
    for (int i = 1; i <= n; ++i) res += s[i] / (t[i] + x);
    return res;
}

int main() {
    scanf("%d %llf", &n, &f);
    db l = -1e9, r = 1e9;
    for (int i = 1; i <= n; ++i) scanf("%llf %llf", &s[i], &t[i]), l = max(l, -t[i]);
    l += eps;
    while (r - l > eps) {
        db mid = (l + r) / 2;
        if (check(mid) > f) l = mid;
        else r = mid;
    }
    printf("%.10f", (double)l);
    return 0;
}

C 战略威慑

求树上两条不交链的长度乘积最大值

直径

一定可以通过断掉一条边，使得树分成两个部分，分别求出两个树的直径即可

时间复杂度 O(n ^ 2)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 10;
typedef long long ll;
int n;
ll ans;
int cnt, head[maxn];
struct edge { int nxt, fr, to, num; } e[maxn << 1];
void add(int u, int v) { e[++cnt].to = v, e[cnt].nxt = head[u], e[cnt].fr = u, head[u] = cnt; }

int mx, tmp;
void dfs(int u, int fa, int dep, int& num) {
    if (mx < dep) { mx = dep, tmp = u; }
    for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
        if (v == fa || (i + 1 == num || i == num)) continue;
        dfs(v, u, dep + 1, num);
    }
}

ll work(int num) {
    mx = -1;
    int u = e[num].fr, v = e[num].to;
    dfs(u, 0, 0, num);
    mx = -1;
    dfs(tmp, 0, 0, num);
    int len1 = mx;
    mx = -1;
    dfs(v, 0, 0, num);
    mx = -1;
    dfs(tmp, 0, 0, num);
    int len2 = mx;
    return 1ll * len1 * len2;
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        add(u, v), add(v, u);
    }
    for (int i = 2; i <= cnt; i += 2) {
        ll tmp = work(i);
        ans = max(ans, tmp);
    }
    printf("%lld\n", ans);
    return 0;
}

这种不相交的问题往往可以化为断边枚举

总结

做的好的地方

• 先写了暴力

做的不好的地方

• 二分写假了，熟练度不够

递推公式: \displaystyle F[i,\ v] = \max \Big\{F[i - 1, \ v - k C_i] + {k W_i} \ |\ 0 \leqslant k C_i \leqslant v\Big\}

求和公式: \displaystyle \sum_{i=1}^{n} i^3 = \left( {\sum_{i=1}^n i} \right)^2 = \frac{n^2(n+1)^2}{4}

彩色表达式: {\color{crimson}x^3} \pm {\color{blue}y^3} = ({\color{crimson}x} \pm {\color{blue}y})({\color{crimson}x^2} \mp {\color{crimson}x}{\color{blue}y} + {\color{blue}y^2})

\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}

计算: 1^2 + 2^2 + 3^2 + \cdots + n^2

计算: \displaystyle 1 + \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \cdots + \frac{1}{2^n}

f(x) = \frac{P(x)}{Q(x)}

\displaystyle f(x) = \frac{P(x)}{Q(x)}

\displaystyle \sum_{i=1}^n i = \frac{n(n+1)}{2}

\displaystyle \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}

算法表达示例:

for i \gets 1 to N \quad for v \gets V to C_{i}

颜色: {\color{crimson}{F = ma}} | {\color{darkred}{F = ma}} | {\color{deeppink}{F = ma}} | {\color{purple}{F = ma}} | {\color{green}{F = ma}}

集合：\Big\{\big(x_i, A(x_i)\big) \ | \ 0 \leqslant i \leqslant n, i \in \Bbb Z \Big\}

向量：\vec a

多行表达式:

test²