美团2024年春招第一场笔试[测开方向]，编程题+选择题详解，ACM式C++解法

编程题

小美的平衡矩阵

小美拿到一个n * n 的矩阵，其中每个元素是0或者1，小美认为0的个数恰好等于1的个数时矩阵就是完美的，现在，小美希望你回答有多少个i * i 的完美矩形区域。你需要回答 1≤ i ≤ n 的所有答案。

思路

涉及到的知识点是前缀和，说实话看见矩阵就想到前缀和了，但是忘记怎么写了o(╥﹏╥)o

复习了一下我胡汉三又回来了，复习时写了超级详细的笔记前缀和大总结！！

okok，回到这道题
仔细阅读题目可以得到的信息：

• 问有多少个i * i的矩阵，说明矩阵必须是正方形，那么边长为奇数的不可能成为平衡矩阵
• 每一个矩阵里面都是0或者1，如果是平衡矩阵的话，矩阵和 == 矩阵元素数量 / 2

很显然的前缀和思路了，得到任意前缀和的1个数并不难，难在如何统计所有i * i的矩阵
嵌套for循环就可以
首先，左上角起始节点的(i，j)的范围因为右边还有留下i的长度，所以左上角起始节点：
假设边长为len

for(int i = 1; i <= n - len + 1; i ++)
	for(int j = 1; j <= n - len + 1; j ++)
1
2

留下了至少一个len边长矩阵的空间
以起始节点为基础，右下角节点：

l = i + len - 1
r = j + len - 1
1
2

所以现在左上角节点(i，j)，右下角节点(l，r)
判断平衡矩阵加加的条件是

if(sum[l][r] - sum[i - 1][j] - sump[i][j - 1] + sum[i - 1][j - 1] == (len * len) / 2)
1

200 OK

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int s[N][N];
int a[N][N];

int main(){
    int n;
    cin >> n;  // 必须首先读取 n
    char c;

    // 接收输入数组
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            cin >> c;  // 先用 c 接收，再将其转为整数类型
            a[i][j] = c - '0'; 
        }
    }

    // 构建前缀和数组
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    // 遍历每一个长度为 len 的矩阵
    for(int len = 1; len <= n; len ++){
        int count = 0;  // 计数应该在这里初始化，每次len变化便重新计数
        if(len % 2 == 0){  // 只考虑偶数长度
            for(int i = 1; i <= n - len + 1; i ++){
                for(int j = 1; j <= n - len + 1; j ++){
                    int l = i + len - 1;
                    int r = j + len - 1;
                    if((s[l][r] - s[i - 1][r] - s[l][j - 1] + s[i - 1][j - 1]) * 2 == len * len) count ++;
                }
            }
            cout << count << endl;
        }
        else{
            cout << 0 << endl;
        }
    }
}

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

小美的数组询问

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间 [l,r] 范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？共有q次询问。

思路

不难，一点也不难
首先题目的意思是，将a[i] == 0的元素替换掉，替换范围是[l，r]，在这个区间内替换处最小值和最大值，最后将替换后的a[]数组输出
只需要记录0的个数，最后个数*最大值/最小值输出即可

但是要注意数据范围

a[i]最大可以达到10⁹，n最大是10⁵，所以和sum完全可以超过int类型，应该用long long，在存和

代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
typedef long long ll ;
int n, m;
int main() {
    cin >> n >> m;
    ll sum = 0;
    int cnt = 0;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        sum += a[i];
        if(a[i] == 0){
            cnt ++;
        }
    }
    while(m --){
        int l, r;
        cin >> l >> r;
        printf("%lld %lld\n",cnt * l + sum, cnt * r + sum);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

验证工号

假设美团的工号是由18位数字组成的，由以下规则组成：

• 前面6位代表是哪个部门
• 7-14位代表是出生日期，范围是1900.01.01-2023.12.31
• 15-17位代表是哪个组，不能是完全一样的3位数字
• 18位是一位的校验和，假设是 x ，则需要满足(声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】