2020 字节跳动校园招聘后端和客户端方向第二场考试 Writeup

Q1

给定等长数组 $a_n, b_n$，判断是否能给 $a_n$ 的一个连续区间的元素加上非负整数 $k$，使得 $a_n$ 变成 $b_n$。

分析：

  1. 因为 $k \ge 0$, 那么显然有 $a_i \leq b_i$。
  2. 作用范围是连续的。
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
#include "bits/stdc++.h"

int a[100000];
int b[100000];

inline int getInt(){
    int t = 0;
    bool neg = false;

    char c = getchar();
    
    while (c == ' ' || c == '\n')
        c = getchar();

    if (c == '-') {
        neg = true;
        c = getchar();
    }
    
    while (c != ' ')
    {
        if (c == '\n')
            break;
        // printf("get %c", c);
        t = t * 10 + (c - '0');

        c = getchar();
    }
       
    return neg ? -t : t;
}

int main()
{
    int T;
    scanf("%d", &T);
    int n;
    for (int i = 0; i < T; ++i) {
        scanf("%d", &n);
        getchar();
        for (int j = 0; j < n; ++j)
            a[j] = getInt();
        for (int j = 0; j < n; ++j)
            b[j] = getInt();
        int d = 0;
        bool bad = false;
        bool had = false;
        for (int j = 0; j < n; ++j){
            if (a[j] != b[j]) {
                if (a[j] - b[j] > 0) {
                    bad = true;
                    break;
                }
                if (had) {
                    if (a[j-1] == b[j-1])
                    {
                        bad = true;
                        break;
                    }
                } else {
                    had = true;
                }
                if (d == 0)
                    d = a[j] - b[j];
                else {
                    if (d != a[j] - b[j]) {
                        bad = true;
                        break;
                    }
                }
            }
        }
        
        if (bad)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

Q2

给定 $n$ 根木棍，你需要依次掰断他们，使他们构成一个单调不递减的序列。

分析：

  1. 木棍的相对顺序不变。
  2. 木棍只能折断为整数。
  3. 单调不递减，即 $a_i \leq a_{i+1}$

WA 了。

Q3

这题是个背包题，给定 $n$ 张可以重复使用的优惠券，$m$ 个商品，问你最少要花多少钱。

不会写。

Q4

给定 $n$ 个数字的序列，求对于每个元素，从它自己开始，统计向两侧方向的连续范围内小于等于它的元素个数。

分析：这题逻辑很清晰，暴力可以过 71% 的测试点。但是剩下的测试点无论是从输入、输出，或是循环边界上优化都过不去，显然测试数据中肯定掺入了大量的连续重复数据段。我最后选择开一个数组统计当前元素的副本数，但是交上去 WA 了不少测试点。交卷后的那一刻才突然意识到还需要对每个副本都单独输出一次结果。

原版暴力

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

inline int getInt()
{
    int t = 0;
    bool neg = false;

    char c = getchar();

    while (c == ' ' || c == '\n')
        c = getchar();

    while (c != ' ')
    {
        if (c == '\n')
            break;
        // printf("get %c", c);
        t = t * 10 + (c - '0');

        c = getchar();
    }

    return t;
}
int crr[6];
inline void putInt(int t)
{
    // t == 0
    if (t == 0)
    {
        putchar('0');
        putchar(' ');
        return;
    }

    // t != 0

    int j = 0;
    while (t != 0)
    {
        crr[j] = '0' + t % 10;
        ++j;
        t /= 10;
    }

    --j;
    while (j != -1)
    {
        putchar(crr[j]);
        --j;
    }
    putchar(' ');
}

int arr[100010];
int brr[100010];
int main()
{
    int T;
    scanf("%d", &T);

    int n;
    int j;
    for (int c = 0; c < T; ++c)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            arr[i] = getInt();
        memset(brr, 0, n * 4);
        for (int i = 0; i < n; ++i)
        {
            j = i - 1;
            while (j != -1)
            {
                if (arr[j] == arr[j + 1] || arr[j] <= arr[i])
                {
                    ++brr[i];
                    --j;
                }
                else
                {
                    break;
                }
            }
            j = i + 1;
            while (j != n)
            {
                if (arr[j] == arr[j - 1] || arr[j] <= arr[i])
                {
                    ++brr[i];
                    ++j;
                }
                else
                {
                    break;
                }
            }
        }
        for (int i = 0; i < n - 1; ++i)
        {
            // printf("%d ", brr[i]);
            putInt(brr[i]);
        }
        printf("%d\n", brr[n - 1]);
    }
    return 0;
}
}

应该是正解

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include "bits/stdc++.h"

inline int getInt()
{
    int t = 0;
    bool neg = false;

    char c = getchar();

    while (c == ' ' || c == '\n')
        c = getchar();

    // if (c == '-')
    // {
    //     neg = true;
    //     c = getchar();
    // }

    while (c != ' ')
    {
        if (c == '\n')
            break;
        // printf("get %c", c);
        t = t * 10 + (c - '0');

        c = getchar();
    }

    return t;
}
int crr[6];
inline void putInt(int t)
{
    // t == 0
    if (t == 0)
    {
        putchar('0');
        putchar(' ');
        return;
    }

    // t != 0

    int j = 0;
    while (t != 0)
    {
        crr[j] = '0' + t % 10;
        ++j;
        t /= 10;
    }

    --j;
    while (j != -1)
    {
        putchar(crr[j]);
        --j;
    }
    putchar(' ');
}

int arr[100010];
int brr[100010];
int drr[100010];
int main()
{
    int T;
    scanf("%d", &T);

    int n;
    int j;
    for (int c = 0; c < T; ++c)
    {
        scanf("%d", &n);
        memset(drr, 0, sizeof(drr));
        for (int i = 0; i < n; ++i)
        {
            arr[i] = getInt();
            if (i != 0 && arr[i] == arr[i - 1])
            {
                ++drr[i - 1];
                --n;
                --i;
            }
            else
            {
                drr[i] = 1;
            }
        }
        memset(brr, 0, n * 4);
        for (int i = 0; i < n; ++i)
        {
            j = i - 1;
            while (j != -1)
            {
                if (arr[j] == arr[j + 1] || arr[j] <= arr[i])
                {
                    brr[i] += drr[j];
                    --j;
                }
                else
                {
                    break;
                }
            }
            j = i + 1;
            while (j != n)
            {
                if (arr[j] == arr[j - 1] || arr[j] <= arr[i])
                {
                    brr[i] += drr[j];
                    ++j;
                }
                else
                {
                    break;
                }
            }
            brr[i] += drr[i] - 1;
        }
        for (int i = 0; i < n - 1; ++i)
        {
            // printf("%d ", brr[i]);
            for (int j = 0; j < drr[i]; ++j)
            {
                putInt(brr[i]);
            }
        }

        for (int j = 0; j < drr[n - 1] - 1; ++j)
            putInt(brr[n - 1]);
        printf("%d\n", brr[n - 1]);
    }
    return 0;
}