美团3.9笔试总结_小美的平衡矩阵c

美团3/9笔试总结(c++)

总结：

菜就多练！！！！！每个公司都有自己的称号真搞

第一题小美的MT

MT 是美团的缩写，因此小美很喜欢这两个字母。

现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作k次，每次可以修改任意一个字符。小美想知道，操作结束后最多共有多少个’M’和’T’字符？

输入描述

第一行输入两个正整数，代表字符串长度和操作次数。第二行输入一个长度为的、仅由大写字母组成的字符串。1<=k<=n<=10^5

输出描述

输出操作结束后最多共有多少个’M’和’T’字符。

题目分析：

很基础的字符串的处理，注意处理好输入和输出。先找到排除原本的“M”和“T”的的数量cnt，操作次数k，因此最多可以将min（k，cnt）个字符变为M和T，总的等于原来的（n - cnt）+ 变换的min（k,cnt)。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int main (void) {
    int cnt = 0;
    int k, n;
    string str;
    cin >> n >> k;
    cin >> str;
    for (char ch : str) {
        if (ch != 'M' && ch != 'T') {
            cnt++;
        }
    }
    int res = n - cnt + min(k, cnt);
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第二题小美的数组询问

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。

现在小美想知道，如果那些未知的元素在区间[l,r]范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？

共有q次询问。

输入描述

第一行输入两个正整数n,q，代表数组大小和询问次数。

第二行输入n个整数ai，其中如果输入ai的为 0，那么说明ai是未知的。

接下来的q行，每行输入两个正整数l,r，代表一次询问。

输出描述

输出q行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

题目分析：

人呐就得贪心。。。。。。。。

对于未知的数字，若想最大化数组和，则取r，若想最小化数组和，则取l

因此，统计数组中0的个数cnt，然后对数组剩余元素求和记结果为sum

注意一下：当时没想到数据的范围，导致第一次没过完，后面一思考，denger得用long long

#include <iostream>  //头文件
#include <vector>
using namespace std;

const int maxn=1e5+10;
int n,q;
vector<int> vec;

int main(){
 cin >> n >> q;
 long long cnt=0,sum=0;
 for(int i=1;i<=n;++i){
  cin >> vec[i];
  if(vec[i]==0){
   cnt++;
  }else{
   sum+=vec[i];
  }
 }
 long long l,r;
 while(q--){
  cin >> l >> r;
  cout << sum + l * cnt<< " " << sum + r * cnt;
 }
 
 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

第三题小美的平衡矩阵

小美拿到了一个n*n 的矩阵，其中每个元素是 0 或者 1。

小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。

现在，小美希望你回答有多少个i*i的完美矩形区域。你需要回答1<=i<=n的所有答案。

输入描述

第一行输入一个正整数n，代表矩阵大小。

接下来的n行，每行输入一个长度为n的01 串，用来表示矩阵。

输出描述

输出n行，第i行输出的I*I 完美矩形区域的数量。

题目分析:

用前缀和可以做

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n));
    // 读取矩阵数据，将字符'0'和'1'转换为整数0和1存储
    for(int i = 0; i < n; ++i) {
        string line;
        cin >> line;
        for(int j = 0; j < n; ++j) {
            matrix[i][j] = line[j] - '0';
        }
    }

    // 构建两个前缀和数组，分别存储0和1的前缀和
    vector<vector<int>> prefix0(n + 1, vector<int>(n + 1, 0)), prefix1(n + 1, vector<int>(n + 1, 0));
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            // 更新前缀和
            prefix0[i][j] = prefix0[i-1][j] + prefix0[i][j-1] - prefix0[i-1][j-1] + (matrix[i-1][j-1] == 0);
            prefix1[i][j] = prefix1[i-1][j] + prefix1[i][j-1] - prefix1[i-1][j-1] + (matrix[i-1][j-1] == 1);
        }
    }

    // 遍历所有可能的子矩阵大小
    for(int size = 1; size <= n; ++size) {
        int count = 0; // 完美矩形的数量
        for(int i = size; i <= n; ++i) {
            for(int j = size; j <= n; ++j) {
                // 计算子矩阵中0和1的数量
                int zeros = prefix0[i][j] - prefix0[i-size][j] - prefix0[i][j-size] + prefix0[i-size][j-size];
                int ones = prefix1[i][j] - prefix1[i-size][j] - prefix1[i][j-size] + prefix1[i-size][j-size];
                // 判断是否为完美矩形
                if(zeros == ones) count++;
            }
        }
        cout << count << 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43

第四题小美的区间删除

小美拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。小美想知道，一共有多少种不同的删除方案？

输入描述

第一行输入两个正整数n，k。第二行输入n个正整数ai，代表小美拿到的数组。

输出描述

一个整数，代表删除的方案数。

题目分析:

首先读取n和k的值，然后输入数组a的各个元素。对于数组中的每个元素，计算其含有的2和5的因子数量，并存储在a2和a5数组中。随后，计算数组a2和a5的元素和，得到总的2和5的因子数量cnt2和cnt5。

接着，代码使用双指针技术遍历数组。对于每个右指针right指向的元素，从总的因子数量中减去该元素的因子数量，并检查剩余的因子数量是否满足条件（即min(cnt2, cnt5) < k）。如果不满足条件，移动左指针left直到条件满足或左指针超过右指针。

最后，计算并输出所有符合条件的子区间数目ans

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), a2(n, 0), a5(n, 0);

    // 输入数组元素并计算每个元素的2和5的因子数量
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        while (a[i] % 2 == 0) {
            a[i] /= 2;
            a2[i]++;
        }
        while (a[i] % 5 == 0) {
            a[i] /= 5;
            a5[i]++;
        }
    }

    // 计算数组中2和5因子的总数
    int cnt2 = 0, cnt5 = 0;
    for (int i = 0; i < n; ++i) {
        cnt2 += a2[i];
        cnt5 += a5[i];
    }

    int left = 0, ans = 0;
    // 使用双指针方法找出所有符合条件的子区间
    for (int right = 0; right < n; ++right) {
        cnt2 -= a2[right];
        cnt5 -= a5[right];
        while (left <= right && min(cnt2, cnt5) < k) {
            cnt2 += a2[left];
            cnt5 += a5[left];
            left++;
        }
        ans += right - left + 1;
    }

    cout << ans << 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

第五题小美的朋友关系

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。

现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？

事件共有 2 种：

1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。

2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。

注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。

输入描述

第一行输入三个正整数n,m,q，代表总人数，初始的朋友关系数量，发生的事件数量。接下来的m行，每行输入两个正整数u,v，代表初始编号u的人和编号v的人是朋友关系。接下来的q行，每行输入三个正整数op,u,v，含义如题目描述所述。

输出描述

对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。

题目分析:

#include<iostream>
#include<string>
using namespace std;
const int N=1E5+10;
unordered_map<int,int>p;
int n,m;
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;
    while(m--)
    {
        char ch;
        int a,b;
        cin>>ch>>a>>b;
        if(ch=='M')
        {
            int pa=find(a),pb=find(b);
            p[pa]=pb;
        }
        else
        {
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<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
30
31
32
33