2024牛客寒假算法基础集训营4

发表于 更新于 分类于 阅读次数： 本文字数： 826 阅读时长 ≈ 3 分钟
The journey is what brings us happiness, not the destination. — Peaceful Warrior

A. 柠檬可乐

思路：

  • 按题意写判断结构即可

时间复杂度：

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

     std::cout << (a >= b * k ? "good\n" : "bad\n");   
    
    return 0;
}

B. 左右互博

思路：

  • 每次会进行a[i] - 1次操作，所以我们只需要求和，判断奇偶即可

时间复杂度：

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

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

    std::cout << (sum & 1 ? "gui\n" : "sweet\n");

    return 0;
}

C. 冬眠

思路：

  • 按规则模拟即可

时间复杂度：

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

    std::vector g(n, std::vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> g[i][j];
        }
    }

    auto move = [&](int op, int z) {
        if (op == 1) {
            int p = 0;
            std::vector<char> tmp(m);
            for (int i = 1; i < m; i++) {
                tmp[i] = g[z][p++];
            }
            tmp[0] = g[z][m - 1];
            g[z] = tmp;
        } else {
            int p = 0;
            std::vector<int> tmp(n);
            for (int i = 1; i < n; i++) {
                tmp[i] = g[p++][z];
            }
            tmp[0] = g[n - 1][z];
            for (int i = 0; i < n; i++) {
                g[i][z] = tmp[i];
            }
        }
    };  

    int p, q;
    std::cin >> p >> q;

    std::vector<int> op(q), z(q);
    for (int i = 0; i < q; i++) {
        std::cin >> op[i] >> z[i];
        z[i] -= 1;
    }
    for (int i = 0; i < p; i++) {
        for (int j = 0; j < q; j++) {
            move(op[j], z[j]);
        }
    }

    std::cout << g[x - 1][y - 1] << "\n";

    return 0;
}

D. 守恒

思路：

  • 可以发现每次可以将一个数+1，另一个数-1的操作，最后所有数都可以取

  • 所以，我们求出sum的所有因子，然后求sum / p > n的个数

  • 记住n = 1需要特判

时间复杂度：

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
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];
    }

    if (n == 1) {
        std::cout << 1 << "\n";
        return 0;
    }

    i64 sum = std::accumulate(a.begin(), a.end(), 0LL);
    i64 t = sum;
    std::vector<int> p;
    for (int i = 1; i <= sum / i; i++) {
        if (sum % i == 0) {
            p.push_back(i);
            if (i != sum / i) p.push_back(sum / i);
        }
    }

    int ans = 0;
    for (auto x : p) {
        if (t / x >= n) {
            ans += 1;
        }
    }
    std::cout << ans << "\n";

    return 0;
}

G. 数三角形（easy）

思路：

  • 数据范围较小，直接模拟即可

时间复杂度：

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

    std::vector g(n + 1, std::vector<char>(m + 1));
    std::vector a(n + 1, std::vector<int>(m + 1));
    std::vector sum(n + 1, std::vector<int>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> g[i][j];
            if (g[i][j] == '.') a[i][j] = 1;
            else a[i][j] = 0;
            sum[i][j] = sum[i][j - 1] + a[i][j];
        }
    }

    int cnt = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 2; j < m; j++) {
            if (g[i][j] == '*') {
                for (int k = 1; i + k <= n && j + k <= m && j - k >= 1 && 
                    g[i + k][j - k] == '*' && g[i + k][j + k] == '*'; k++) {
                    if (sum[i + k][j - k] == sum[i + k][j + k]) {
                        cnt++;
                    }
                }
            }
        }
    }
    std::cout << cnt << "\n";

    return 0;
}

E. 漂亮数组

思路：

  • 用set模拟，因为都是k的倍数，所以只需要维护前i个数的和mod k的余数即可

时间复杂度：

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

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

    int ans = 0;
    std::set<i64> st;
    st.insert(0);
    std::vector<i64> s(n + 1);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
        s[i] %= k;
        if (st.count(s[i])) {
            ans++;
            st.clear();
            s[i] = 0;
            st.insert(0);
        } else {
            st.insert(s[i]);
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}