不忘初心
时刻前行

第二题手抖把 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 的方程

m = \sum_{i = 1}^n \frac{s_i}{v_i + 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;
}

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

总结

做的好的地方

  • 先写了暴力

做的不好的地方

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

OI-二分答案 OI-图论-最短路 OI-图论-建模 OI-树的直径

None
上一篇 «
CSP 初赛复习笔记
» 下一篇
© 2019 - 2019 bwt's blog.
...... visits · ...... visitors