第 9 场 小白入门赛

发表于 更新于 分类于 阅读次数： 本文字数： 394 阅读时长 ≈ 1 分钟
Experience is the best teacher.

B. 盖印章

思路：

  • 仔细分析一下，可以的得到一个方程组 \(\begin{cases} x+y=K \\ 3x + 2y = cnt_0 \end{cases}\) ，然后利用初中知识求解方程组即可

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

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

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        std::string S;
        std::cin >> S;
        for (auto x : S) {
            cnt += x == '1';
        }
    }

    std::cout << cnt - 2 * K << " " << 3 * K - cnt << "\n";

    return 0;
}

C. 字符迁移

思路：

  • 利用差分技巧，进行 \(O(n)\) 的区间求和

时间复杂度：\(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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, Q;
    std::cin >> N >> Q;

    std::string S;
    std::cin >> S;

    std::vector<i64> b(N + 2);
    while (Q--) {
        int l, r, v;
        std::cin >> l >> r >> v;

        auto add = [&](int l, int r, int v) {
            b[l] += v;
            b[r + 1] -= v;
        };
        add(l, r, v % 26);
    }

    for (int i = 1; i <= N; i++) {
        b[i] += b[i - 1];
    }

    for (int i = 0; i < N; i++) {
        i64 t = b[i + 1] + S[i] - 'a';
        t %= 26;
        std::cout << char('a' + t);
    }

    return 0;
}

D. 字典树考试

思路：

  • 可以发现，只需统计 1 的个数即可，因为只要出现了两个数的二进制表示下的任意两位相等，那么他们就一定会被加上，所以最后个数一定是 \(\Sigma^{31}_{i=1}C_{cnt_i}^{2} \Rightarrow \Sigma^{31}_{i=1}\frac{cnt_i \times (cnt_i - 1)}{2}\)​
  • 注意爆 int

时间复杂度：\(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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<int> bit(32);
    for (int i = 0; i < N; i++) {
        int x;
        std::cin >> x;
        for (int j = 31; j >= 0; j--) {
            if (x >> j & 1) {
                bit[j]++;
            }
        }
    }

    i64 ans = 0;
    for (int i = 0; i < 32; i++) {
        if (bit[i] > 1) {
            ans += 1LL * (bit[i] - 1) * bit[i] / 2;
        }
    }
    std::cout << ans << "\n";

    return 0;
}