CF题解

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin ， Cool-breeze

G. Omg Graph

https://codeforces.com/contest/2117/problem/G

给定无向带权连通图，定义一条路径的花费为：路径经过的边中，边权最大值 + 最小值。求从 \(1\) 到 \(n\) 路径中的最小花费（注意不一定是简单路径）。

\(2≤n≤2⋅10^5,n−1≤m≤\min(2⋅10^5,n(n−1)/2),1≤u,v≤n,1≤w≤10^9\)

点击查看题解

最小生成树 考虑求 \(1\rightarrow n\) 的最小瓶颈路，其最大值部分一定是最小的，设为 \(\text{dmax}_n\)，并设最小值部分为 \(\text{dmin}_n\)；之后考虑枚举每条边，试图更新最小值部分。因此，需要求出 \(1\) 到每个点的最小瓶颈路，试图更新最小值部分时尽量使最大值不变或变化较少。

由于最小生成树是最小瓶颈树，所以需要求图的最小生成树。

设 \(1\rightarrow i\) 的瓶颈为 \(\text{dmax}_i\)，则边 \(j\) 的瓶颈为 \(\text{emax}_j=\max\{w_j,\min\{\text{dmax}_i\mid (i,j)\in E\}\}\)。则答案为： \[ \min\{w_i+\max\{\text{dmax}_n,\text{emax}_j\}\mid 1\le i\le m\} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 200000 + 50, inf = 1145141919810;

struct edge {
    ll u, v, len, id;
} g[N];

ll n, m, dmax[N], emax[N];
ll dad[N];
vector<PII > e[N];
vector<edge> ge[N];

bool cmp(edge x, edge y) {
    return x.len < y.len;
}

bool recmp(edge x, edge y) {
    return x.id < y.id;
}

void add(ll x, ll y, ll len) {
    e[x].push_back({y, len});
    e[y].push_back({x, len});
}

void gadd(ll x, ll y, ll len, ll id) {
    ge[x].push_back({x, y, len, id});
    ge[y].push_back({y, x, len, id});
}

ll find(ll x) {
    while (x != dad[x]) {
        x = dad[x] = dad[dad[x]];
    }
    return x;
}

void merge(ll x, ll y) {
    x = find(x), y = find(y);
    dad[x] = y;
}

ll check(ll x, ll y) {
    x = find(x), y = find(y);
    if (x == y)
        return 1;
    return 0;
}

void dfs(ll root, ll dad) {
    for (auto son: e[root]) {
        if (son.first != dad) {
            dmax[son.first] = max(dmax[root], son.second);
            dfs(son.first, root);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        ll u, v, len, ans = inf;
        cin >> n >> m;
        for (ll i = 1; i <= n; i++) {
            ge[i].clear();
            e[i].clear();
        }
        for (ll i = 1; i <= m; i++) {
            cin >> u >> v >> len;
            g[i] = (edge){u, v, len, i};
            gadd(u, v, len, i);
        }
        for (ll i = 1; i <= n; i++)
            dad[i] = i;
        for (ll i = 1; i <= m; i++)
            emax[i] = inf;
        sort(g + 1, g + 1 + m, cmp);
        for (ll i = 1; i <= m; i++) {
            if (check(g[i].u, g[i].v) == 0) {
                add(g[i].u, g[i].v, g[i].len);
                merge(g[i].u, g[i].v);
            }
        }
        dmax[1] = 0;
        dfs(1, 1);
        sort(g + 1, g + 1 + m, recmp);
        for (ll from = 1; from <= n; from++) {
            for (auto to: ge[from]) {
                emax[to.id] = min(emax[to.id], dmax[from]);
            }
        }
        for (ll i = 1; i <= m; i++)
            emax[i] = max(emax[i], g[i].len);
        for (ll i = 1; i <= m; i++) {
            ans = min(ans, g[i].len + max(dmax[n], emax[i]));
        }
        cout << ans << endl;
    }
    return 0;
}

D. From 1 to Infinity

https://codeforces.com/contest/2132/problem/D

写下一个无限长的数字：\(1234567891011121314151617...\)，求从最高位开始前 \(k\) 位数码的和。

多组数据，\(1≤t≤2⋅10^4,1≤k≤10^{15}\)。

点击查看题解

毒瘤题 考虑找到 \(k\) 位置填的是数字几，设这个数字为 \(x\)。首先判断 \(x\) 是几位数，设为 \(d\) 位。由于不同位数的数占有数位个数不同，可以均化成 \(d\) 位数，除以 \(d\) 即可得到 \(x\)。

先把不完整的尾巴算出来，之后考虑算 \(1\sim x\) 的数位和。

使用递归解决问题。例如算的是 \(1\sim546\)，可以先算出 \(1\sim499\)，之后再加上 \((46+1)\) 个 \(5\)，最后算 \(1\sim46\) 递归解决即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 150000 + 50;

ll k, st[100], tmp[100];

ll calc(ll num) {
    ll len = 0, tmp = num, full, res, ret = 0;
    if (num <= 0)
        return 0;
    while (tmp > 0) {
        tmp /= 10;
        len++;
    }
    full = (num + 1) / (ll) pow(10, len - 1);
    res = (num + 1) % (ll) pow(10, len - 1);
    ret += full * (full - 1) / 2 * pow(10, len - 1);
    ret += full * calc(pow(10, len - 1) - 1);
    ret += full * res;
    ret += calc(res - 1);
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T, b10 = 1, num, base, add, num2, res, len;
    cin >> T;
    for (ll i = 1; i <= 16; i++) {
        st[i] = i * 9 * b10 + st[i - 1];
        b10 *= 10;
    }
    while (T--) {
        cin >> k;
        for (ll i = 0; i <= 15; i++) {
            if (k <= st[i + 1] && k >= st[i]) {
                base = i;
                break;
            }
        }
        for (ll i = 1; i <= base; i++) {
            k += pow(10, i) - 1;
        }
        num = k / (base + 1);
        res = k % (base + 1);
        num2 = num + 1;
        add = len = 0;
        for (ll i = 1; i <= 16; i++)
            tmp[i] = 0;
        for (ll i = 1; num2 > 0; i++) {
            tmp[i] = num2 % 10;
            num2 /= 10, len++;
        }
        while (res > 0) {
            add += tmp[len];
            res--, len--;
        }
        cout << calc(num) + add << endl;
    }
    return 0;
}

D. Not Alone

https://codeforces.com/contest/2153/problem/D

如果环形数列中每个数存在至少一个与之相等的相邻数，称这个数列是好数列。

给一个长度为 \(n\) 的环形数列 \(a\)。可以进行任意次操作：对数列中任意一个数增加或减少一。求最少需要多少次操作，将 \(a\) 数列变为好数列。

\(3≤n≤2⋅10^5,1≤a_i≤10^9\)

点击查看题解

思维题 好数列 → 数列中的数形成一系列大小大于一的连通块（块内数字均相等）→ 连通块大小不需要超过 \(3\)，否则不优。

对于非环形数列，可以使用 DP 解决：设 \(f(i,2/3)\) 表示将 \(a[1:i]\) 变成好数列，且末尾连通块大小为 \(2/3\) 的最少操作。

对于题目要求环形数列，需要断环为链。考虑到连通块大小不超过 \(3\)，所以只需要取断点 \(1,2,3\) 号位即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 4e5 + 10, inf = 1145141919810999999;

ll n, d[N], f[N][4];

ll calc(ll a[]) {
    for (ll i = 1; i <= n; i++) {
        for (ll j = 2; j <= 3; j++) {
            f[i][j] = inf;
        }
    }
    f[0][2] = f[0][3] = 0;
    f[2][2] = abs(a[1] - a[2]);
    f[3][3] = max({a[1], a[2], a[3]}) - min({a[1], a[2], a[3]});
    for (ll i = 3; i <= n; i++) {
        ll p2 = abs(a[i] - a[i - 1]);
        ll p3 = max({a[i], a[i - 1], a[i - 2]}) - min({a[i], a[i - 1], a[i - 2]});
        f[i][2] = min(f[i - 2][2], f[i - 2][3]) + p2;
        f[i][3] = min(f[i - 3][2], f[i - 3][3]) + p3;
    }
    return min(f[n][2], f[n][3]);
}

void solve() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> d[i];
        d[i + n] = d[i];
    }
    ll ans = inf;
    for (ll i = 1; i <= 3; i++) {
        ans = min(ans, calc(d + i));
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}