Codeforces Round 923 (Div. 3)

发表于 更新于 分类于 阅读次数： 本文字数： 975 阅读时长 ≈ 4 分钟
Life has no limitations, except the ones you make.

A. Make it White

思路：

  • 找字符B的第一个位置和最后一个位置就行

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    int cnt = 0;
    int l = -1, r = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'B') {
            r = i;
            if (cnt == 0) {
                l = i;
            }
            cnt++;
        }
    }
    std::cout << r - l + 1 << "\n";
}

B. Following the String

思路：

  • 每一位从字符a开始累加即可

时间复杂度：\(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
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    int mx = 0;
    std::vector<std::vector<int>> p(n + 1);
    for (int i = 0; i < n; i++) {
        p[a[i]].push_back(i);
        mx = std::max(mx, a[i]);
    }

    std::vector<char> ans(n);
    for (int i = 0; i <= mx; i++) {
        char c = 'a';
        for (auto x : p[i]) {
            ans[x] = char(c);
            c++;
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << ans[i];
    }
    std::cout << "\n";
}

C. Choose the Different Ones!

思路：

  • 容斥原理

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

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
void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    
    std::set<int> u, v;
    std::vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        u.insert(a[i]);
    }
    for (int i = 0; i < m; i++) {
        std::cin >> b[i];
        v.insert(b[i]);
    }

    int x = 0, y = 0, z = 0;
    for (int i = 1; i <= k; i++) {
        if (u.count(i) && v.count(i)) {
            z++;
        } else if (u.count(i)) {
            x++;
        } else if (v.count(i)) {
            y++;
        } else {
            std::cout << "NO\n";
            return ;
        }
    }
    if (x <= k / 2 && y <= k / 2) {
        if (x + y + z == k) {
            std::cout << "YES\n";
            return ;
        }
    }
    std::cout << "NO\n";
}

D. Find the Different Ones!

思路：

  • 用set每次找不等的分割点，然后upper_bound左端点即可

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

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
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    std::set<int> S;
    for (int i = 2; i <= n; i++) {
        if (a[i] != a[i - 1]) {
            S.insert(i);
        }
    }

    int q;
    std::cin >> q;

    while (q--) {
        int l, r;
        std::cin >> l >> r;

        auto it = S.upper_bound(l);
        if (*it > r || it == S.end()) {
            std::cout << "-1 -1\n";
        } else {
            std::cout << l << " " << *it << "\n";
        }
    }
    std::cout << "\n";
}

E. Klever Permutation

思路：

  • 用滑动窗口的思想，每次向后推进一个位置就要丢掉前面一个数，偶数位递增，奇数位递减

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    int n, k;
    std::cin >> n >> k;

    int l = 1, r = n;
    std::vector<int> ans(n + 1);
    for (int i = 1; i <= k; i++) {
        for (int j = i; j <= n; j += k) {
            if (i & 1) {
                ans[j] = r;
                r--;
            } else {
                ans[j] = l;
                l++;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        std::cout << ans[i] << " \n"[i == n];
    }
}

F. Microcycle

思路：

  • 可以用kruskal来求出最小生成树，首先我们把所有的点按照边权来从大到小排序，然后选取一个点集的起始点和终点，当两个点已经在一个集合中，就在这个集合中开始建边，然后跑dfs进行寻找路径，而由于最初已经把边权值按从大到小的顺序排列，所以当最后合并两个点的集合时，最小权值就是最后一个进入集合的边权

时间复杂度：\(O(mlogm+m\alpha(n))\)

附：\(\alpha(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
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
108
109
110
111
112
113
114
115
116
117
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

constexpr int inf = 2E9;

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::array<int, 3>> a(m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        u--, v--;

        a[i] = {u, v, w};
    }

    std::sort(a.begin(), a.end(), [&](auto i, auto j) {
        return i[2] > j[2];
    });

    DSU f(n);

    int U, V;
    int cnt = 1, ans = inf;
    std::vector<std::vector<int>> g(n);
    auto kruskal = [&]() {
        for (auto [u, v, w] : a) {
            if (!f.merge(u, v)) {
                ans = w;
                U = u, V = v;
            } else {
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
    };

    kruskal();

    std::vector<int> path;
    auto dfs = [&](auto self, int u, int fa) -> bool {
        if (u == V) {
            path.push_back(u);
            return true;
        }
        for (auto f : g[u]) {
            if (f == fa) continue ;
            if (self(self, f, u)) {
                path.push_back(u);
                return true;
            }
        }
        return false;
    };

    dfs(dfs, U, -1);

    std::cout << ans << " " << path.size() << "\n";
    for (auto x : path) {
        std::cout << x + 1 << " ";
    }
    std::cout << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }    

    return 0;
}