牛客周赛 Round 32

发表于 更新于 分类于 阅读次数： 本文字数： 491 阅读时长 ≈ 2 分钟
Don't judge someone's past, when you haven't walked their journey!

A. 小红的 01 背包

思路：

  • 按题意模拟即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int V, v, w;
    std::cin >> V >> v >> w;

    std::cout << V / v * w << "\n";
    
    return 0;
}

B. 小红的 dfs

思路：

  • 由于n = 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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::vector g(3, std::vector<char>(3));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            std::cin >> g[i][j];
        }
    }

    int A = 0;
    if (g[0][0] != 'd') A++;
    if (g[0][1] != 'f') A++;
    if (g[0][2] != 's') A++;
    if (g[1][0] != 'f') A++;
    if (g[2][0] != 's') A++;

    int B = 0;
    if (g[0][1] != 'd') B++;
    if (g[1][1] != 'f') B++;
    if (g[2][1] != 's') B++;
    if (g[1][0] != 'd') B++;
    if (g[1][2] != 's') B++;

    int C = 0;
    if (g[0][2] != 'd') C++;
    if (g[1][2] != 'f') C++;
    if (g[2][2] != 's') C++;
    if (g[2][0] != 'd') C++;
    if (g[2][1] != 'f') C++;

    std::cout << std::min({A, B, C}) << "\n";

    return 0;
}
/*
dfs    *d*    **d
f**    dfs    **f
s**    *s*    dfs
*/

C. 小红的排列生成

思路：

  • 由于可以加1和-1，所以直接遍历相减即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

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

    std::sort(a.begin(), a.end());

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(a[i] - i - 1);
    }
    std::cout << ans << "\n";
    
    return 0;
}

D. 小红的二进制树

思路：

  • 从root(1)记忆化搜索一遍，只要遇到1，就说明最末尾为1，也就这个子段在十进制下为奇数，cnt[father] += cnt[son]即可

时间复杂度：

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

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

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

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

    std::vector<int> cnt(n);
    auto dfs = [&](auto self, int u, int fa) -> void {
        for (auto x : adj[u]) {
            if (x == fa) continue ;
            if (s[x] == '1') {
                cnt[u]++;
            }
            self(self, x, u);
            cnt[u] += cnt[x];
        }
    };
    dfs(dfs, 0, -1);

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

    return 0;
}