字节跳动2023秋招研发第四场笔试【后端方向】

T1 金字塔

模拟 O(mlogm)

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
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

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

    int n;
    std::cin >> n;
    std::vector<std::vector<int> > a(n);
    std::vector<std::vector<bool>> flag(n);
    for (int i = 0; i < n; i++) {
        int m;
        std::cin >> m;
        for (int j = 0; j < m; j++) {
            int x;
            std::cin >> x;
            a[i].push_back(x);
            flag[i].push_back(false);
        }
    }
    for (int i = 0; i < flag[0].size(); i++) flag[0][i] = true;
    for (int i = 1; i < n; i++) {
        // a[i][j] + 50 in a[i - 1]
        // a[i][j] + 1 in a[i - 1] a[i][j] + 99 in a[i - 1]
        for (int j = 0; j < a[i].size(); j++) {
            int p1 = std::lower_bound(a[i - 1].begin(), a[i - 1].end(), a[i][j]) - a[i - 1].begin();
            // pre one
            if (p1 >= 1 && flag[i - 1][p1 - 1] && a[i - 1][p1 - 1] + 100 > a[i][j] + 50) {
                flag[i][j] = true;
            }
            // next one
            if (p1 < a[i - 1].size() && flag[i - 1][p1] && a[i - 1][p1] < a[i][j] + 50) {
                flag[i][j] = true;
            }
            if (p1 >= 1 && p1 < a[i - 1].size() && flag[i - 1][p1 - 1] && flag[i - 1][p1] && a[i - 1][p1 - 1] + 100 > a[i][j] && a[i - 1][p1] < a[i][j] + 100) {
                flag[i][j] = true;
            }

        }
    }

T2 最长01序列

尺取 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
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

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

    std::string s;
    std::cin >> s;
    int n = s.size();
    int ans = 0;
    int cnt = 1;
    int r = 1;
    while (r < n) {
        if (s[r] != s[r - 1]) cnt++;
        else {
            ans = std::max(ans, cnt);
            cnt = 1;
        }
        r++;
    }
    std::cout << ans << std::endl;

T3 修改最短子串使得整串词频相同

前缀和 + 二分 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

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

T4 最长区间的最大值和最小值的绝对值差小于等于k，并求区间个数和起点和终点

ST表维护区间最值，把i设为起始点并二分求出终点 O(nlognlogn)

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
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

template <typename T, class F = std::function<T(const T&, const T&)>>
class SparseTable {
public:
    int n;
    std::vector<std::vector<T>> mat;
    F func;

    SparseTable(const std::vector<T>& a, const F& f) : func(f) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        mat.resize(max_log);
        mat[0] = a;
        for (int j = 1; j < max_log; j++) {
            mat[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); i++) {
                mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    T get(int from, int to) const {
        assert(0 <= from && from <= to && to <= n - 1);
        int lg = 32 - __builtin_clz(to - from + 1) - 1;
        return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
    }
};

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

    int n;
    std::cin >> n;
    int k;
    std::cin >> k;
    std::vector<int> h(n);
    for (int i = 0; i < n; i++) {
        std::cin >> h[i];
    }
    SparseTable<int> mx(h, [](const int& i, const int& j) { return std::max(i, j); });
    SparseTable<int> mn(h, [](const int& i, const int& j) { return std::min(i, j); });

    std::vector<std::pair<int, int>> ans;
    for (int i = 0; i < n; i++) {
        int l = i, r = n - 1;
        int j = r - l + 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (mx.get(i, mid) - mn.get(i, mid) <= k) {
                j = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        // i - j
        if (ans.empty()) {
            ans.push_back({i, j});
        }
        else {
            if (ans.front().second - ans.front().first + 1 < j - i + 1) {
                ans.clear();
                ans.push_back({i, j});
            } else if (ans.front().second - ans.front().first + 1 == j - i + 1) {
                ans.push_back({i, j});
            }
        }
    }

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2022/09/18/bytedance2023fourwrittenexan/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！