AcWing 第142场周赛

发表于 更新于 分类于 阅读次数： 本文字数： 516 阅读时长 ≈ 2 分钟
Doing what you like is freedom. Liking what you do is happiness.

A. 倒序排列

思路：

  • 输出 \(n \sim 1\) 的所有数即可

时间复杂度：\(O(n)\)

1
2
3
n = int(input())
for i in range(n, 0, -1):
    print(i, end=" ")

B. 最有价值字符串

思路：

  • 只要最初的最大个数为字符串长度，那么只要 \(n\) 为 \(1\) ，就必须要执行减 \(1\) ，只有这一种情况需要特判，因为只要大于 \(1\)​ ，就可以先改变其他字符，来达到最终为字符串最大个数的情况，然后模拟即可

时间复杂度：\(O(n)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::string a, b, c;
    std::cin >> a >> b >> c;

    int p = a.size();

    int A = 0, B = 0, C = 0;
    std::map<int, int> mp;
    for (int i = 0; i < a.size(); i++) {
        mp[a[i]]++;
        A = std::max(A, mp[a[i]]);
    }

    mp.clear();
    for (int i = 0; i < b.size(); i++) {
        mp[b[i]]++;
        B = std::max(B, mp[b[i]]);
    }
     
    mp.clear();
    for (int i = 0; i < c.size(); i++) {
        mp[c[i]]++;
        C = std::max(C, mp[c[i]]);
    }
    if (A == p && n == 1) {
        A = p - 1;
    } else {
        A = std::min(p, A + n);
    }
    if (B == p && n == 1) {
        B = p - 1;
    } else {
        B = std::min(p, B + n);
    }
    if (C == p && n == 1) {
        C = p - 1;
    } else {
        C = std::min(p, C + n);
    }

    int mx = std::max({A, B, C});

    if ((A == mx && B == mx) || (C == mx && B == mx) || (A == mx && C == mx)) {
        std::cout << "D\n";
    } else if (A == mx) {
        std::cout << "A\n";
    } else if (B == mx) {
        std::cout << "B\n";
    } else if (C == mx) {
        std::cout << "C\n";
    }

    return 0;
}

C. 有效点对

思路：

  • 有效点数等于总点数减去无效点数 \(U_{有效}= S_{总}-B_{无效}\) ，然后只需要 \(dfs\) 遍历从 \(x\) 到 \(y\) 的所有点即可，只要这个点在路线中，就要算入结果

时间复杂度：\(O(n)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, x, y;
    std::cin >> n >> x >> y;
    x--, y--;

    std::vector<std::vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;

        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    std::vector<int> vis(n), cnt(n);
    auto dfs = [&](auto self, int u, int fa) -> void {
        vis[u] = (u == y);
        cnt[u] = 1;
        for (auto x : g[u]) {
            if (x == fa) continue ;
            self(self, x, u);
            cnt[u] += cnt[x];
            vis[u] |= vis[x];
        }
    };

    dfs(dfs, x, -1);

    i64 ans = 0;
    for (auto v : g[x]) {
        if (vis[v]) {
            ans += 1LL * (n - 1) * n - 1LL * (n - cnt[v]) * cnt[y];
        }
    }
    std::cout << ans << "\n";

    return 0;
}