2022-8-24 华为秋招笔试

2022-8-24 华为秋招笔试

这次主要简单讲一下前两题，具体题目记不清了，大家可以在网上找到。

T1

思路：(我刚开始想的是排序完求排序差分数组的前缀和，不过其实原理差不多) 前缀和（感觉跟那个接雨水有点像），双指针（l,r, （如果超过n,））,题目中给了一个例子，如 10，3，1 分给 8个

为10，10，1 ，最后还剩余1。有同学可能要问，10，3 + 3，5+1,可否行，嗯–，理论上可以，但是题目给的例子好像就是为了避免这种情况。如果这样的话，或许可以转背包问题，但是题目n有点大超过1e6，做背包也不明智，那就双指针吧qvq。

#include 
using namespace std;
const int maxn = 1e4 + 10;
int arr[maxn];
int m,n;


int main(){
    ios::sync_with_stdio(false);
    cin >> m;
    for(int i = 0; i <m;i++) cin >>arr[i];
    sort(arr,arr+m); //方便形成从低到高，简化前缀计算难度
    cin >>n;
    int cost =0;
    int maxlen =0,ret = INT32_MAX;
    for(int l = 0,r = 0; r < m;r++){
       if(r==0) cost = 0;
       else cost += (arr[r] - arr[r-1])*(r-l); //
       while(l<=r && cost >= n){
         cost -= (arr[r] - arr[l++]); // 去掉l的贡献
       }
       if(r - l +1 >= maxlen && ret >= n - cost){ // 尽可能两个都满足吧
        maxlen = r - l + 1;
        ret = n - cost;
       }
    }
    cout << maxlen <<" " << ret << endl;
    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

T2

思路：二分图+网络流解决最大独立集问题，很显然，如果直接做是一个NP问题，如果转为二分图，奇数连奇数边，偶数连接偶数边，同时我们把产生矛盾的边addedge() 也就是加到网络流中，最后我们用满足条件的点-Dinic（）就可以得到最大独立集。嗯–，不过在加边之前，我们要以0 为出发点，判断周围是否有1，如果上下左右有1，那么直接continue;

因为题目中说1的上下左右不可放点。

#include 
using namespace std;
const int maxn = 25;
int n, m;
#define inf (1<<29)

int Arr[maxn][maxn],Brr[maxn][maxn];
int cnt;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

bool check(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        int X = x + dx[i], Y = y + dy[i];
        if (X < 0 || X >= n || Y < 0 || Y >= m)
        {
            continue;
        }
        if (Arr[X][Y])
            return false;
    }
    return true;
}

class Solution
{
    int tot, head[600];
    struct Edge
    {
        int to, net, v;
    } E[10010];
    void addedge(int x, int y, int v)
    {
        E[++tot].to = y;
        E[tot].net = head[x];
        head[x] = tot;
        E[tot].v = v;
        E[++tot].to = x;
        E[tot].net = head[y];
        head[y] = tot;
        E[tot].v = 0;
    }
    int S, T, Q[600], depth[600];
    int getp(int x, int y)
    {
        return x * m + y + 1;
    }
    bool bfs()
    {
        for (int i = S; i <= T; ++i)
            depth[i] = -1;
        int L = 0, R = 1;
        Q[1] = S;
        depth[S] = 0;
        while (L < R)
        {
            int x = Q[++L];
            for (int i = head[x]; i; i = E[i].net)
                if (E[i].v > 0 && depth[E[i].to] == -1)
                {
                    depth[E[i].to] = depth[x] + 1;
                    Q[++R] = E[i].to;
                }
        }
        return depth[T] != -1;
    }
    int dfs(int x, int flow)
    {
        if (x == T || !flow)
            return flow;
        int w = 0;
        for (int i = head[x]; i; i = E[i].net)
            if (E[i].v > 0 && depth[E[i].to] == depth[x] + 1)
            {
                int v = dfs(E[i].to, min(flow - w, E[i].v));
                E[i].v -= v;
                E[i ^ 1].v += v;
                w += v;
            }
        if (!w)
            depth[x] = -1;
        return w;
    }
    int Dinic()
    {
        int sum = 0;
        while (bfs())
            sum += dfs(S, inf);
        return sum;
    }

public:
    // void add(int x, int y)
    // {
    //     // Solution t;
    //     for (int i = 0; i < 4; i++)
    //     {
    //         int xx = x + dx[i];
    //         int yy = y + dy[i];

    //         if (xx >= 0 && xx < n && yy < m && yy >= 0 && Arr[x][y] == 1)
    //         {
    //             addedge((x - 1) * n + y, (xx - 1) * n + yy, inf);
    //         }
    //     }
    // }

    int maxStudents()
    {
        tot = 1;
        S = 0;
        T = n * m + 1;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (Arr[i][j] == 0) // 相当于提前把 1 盘走了
                {
                    // 接着再判断四周有没有障碍物，相当于根据0来选择1
                    if (!check(i, j))
                    {
                        continue;
                    }
                    ++cnt;
                    int x = i * m + j + 1;
                    if (j & 1)
                        addedge(S, x, 1);
                    else
                        addedge(x, T, 1);
                    if (j && Arr[i][j - 1] == 0)
                    {
                        if (j & 1)
                            addedge(x, getp(i, j - 1), 1);
                        else
                            addedge(getp(i, j - 1), x, 1);
                    }
     
                    if (i && Arr[i - 1][j] == 1)
                    {
                        if (j & 1)
                            addedge(x, getp(i - 1, j), 1);
                        else
                            addedge(getp(i - 1, j), x, 1);
                    }
                }
            }
        }
        // int sum = Dinic();
        // cout << cnt << " " << sum << endl;
        return cnt - Dinic();
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    memset(Arr, 0, sizeof Arr);
    // vector> vec(n, vector(m, 0));
    cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> Arr[i][j];
        }
    }

    Solution S;
    int res = S.maxStudents();

    cout << res << endl;
    return 0;
}

/*
2 4
1 0 0 0
0 0 0 1

4 6
1 0 0 0 0 1
0 0 0 0 0 0
0 1 0 0 0 1
0 0 0 0 0 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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189