美团2024年春招第一场笔试 C++

目录

1，小美的均衡矩阵
2，小美的数组询问
3，小美的MT
 4，小美的朋侪关系

---

1，小美的均衡矩阵

 【题目描述】
给定一个n*n的矩阵，该矩阵只包含数字0和1。对于 每个i(1<=i<=n)，求在该矩阵中，有多少个i*i的区域满足0的个数等于1的个数？？？
【题目解析】
示例演示：

 如上图，1*1的区域效果为0，2*2的区域效果为7。
算法：前缀和+遍历
   题目中给的数据范围是n<=200，以是可以直接遍历数组。
  维护 一个前缀和数组统计以（x，y）这个点为右下角，以（1，1）这个点为左上角，这个区域中所有元素的和，由于数组中的数要么是0，要么是1，所从前缀和就表示某个区域中1的个数。
  有了前缀和数组，就可以快速 求出某个区域中1的个数，如图：

    而这个区域的大小我们是知道的，假设是k，那么这个区域的元素个数就是k*k。如果满足这个区间中1的个数等于k*k/2，那么说明 这个区间中0和1的个数 相等。而1的个数我们可以通过前缀和来表示。
  同时另有一点，如果k为奇数，那么k*k的区域中元素个数一定为奇数 ，以是0和1的个数一定不相等。直接输出0即可。
   留意：在输入数据的时候，如果是以整数的形式担当，那么不建议利用cin，因为cin会把第一行的所有数据读成一个整数。就比如 上面的示例，第一行会被读成一个整数1010，而我们期望是读到4个整数的，这是可以利用scanf("%1d",&a），利用 %1d占位符可以确保读到的第一行是4个整数。
【代码】

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. const int N = 205;
6. int arr[N][N], s[N][N];
7. //s为前缀和数组
8. //统计矩形(1,1)到(n,n)中1的数量
10. int main()
11. {
12.         int n = 0;
13.         cin >> n;
14.         for(int  i=1;i<=n;i++)
15.                 for (int j = 1; j <= n; j++)
16.                 {
17.                         scanf("%1d", &arr[i][j]);
18.                         s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j];
19.                 }
20.         cout << 0 << endl;
21.         for (int k = 2; k <= n; k++)
22.         {
23.                 if (k & 1)
24.                 {
25.                         cout << 0 << endl;
26.                         continue;
27.                 }
28.                 int ans = 0;
29.                 for(int i=1;i+k-1<=n;i++)
30.                         for (int j = 1; j+k-1 <= n; j++)
31.                         {
32.                                 //(i,j)是左上角，需要我们计算出k*k这个区域右下角的坐标
33.                                 int x = i + k - 1;
34.                                 int y = j + k - 1;
35.                                 if (s[x][y] - s[i - 1][y] - s[x][j - 1] + s[i - 1][j - 1] == k * k / 2)
36.                                         ans++;
37.                         }
38.                 cout << ans << endl;
39.         }
40.         return 0;
41. }

复制代码

2，小美的数组询问

 直接遍历即可 

1. #include <iostream>
2. using namespace std;
4. const int N=1e5+10;
5. int arr[N];
6. int main()
7. {
8.     int n=0,q=0;
9.     cin>>n>>q;
10.     long long sum=0,count=0;
11.     for(int i=1;i<=n;i++)
12.     {
13.         cin>>arr[i];
14.         sum+=arr[i];
15.         if(arr[i]==0)
16.         count++;
17.     }
19.     int l,r;
20.     while(q--)
21.     {
22.         cin>>l>>r;
23.         cout<<sum+count*l<<" "<<sum+count*r<<endl;
24.     }
26.     return 0;
27. }

复制代码

3，小美的MT

统计元字符中 有多少个M和T，再加上最多可以修改 多少个即可。

1. //小美的MT
2. #include <iostream>
3. #include <string>
4. using namespace std;
6. int main()
7. {
8.         int n = 0, k = 0;
9.         cin >> n >> k;
10.         string str;
11.         cin >> str;
12.         int ans = 0;
13.         for (int i = 0; i < n; i++)
14.         {
15.                 if (str[i] == 'M' || str[i] == 'T')
16.                         ans++;
17.         }
18.         if (k > n - ans)
19.                 cout << n << endl;
20.         else
21.                 cout << ans + k << endl;
22.         return 0;
23. }

复制代码

 4，小美的朋侪关系

 【题目描述】
总人数为n，编号u和v的人之间存在朋侪关系，在这n个人中，存在m个朋侪关系。
对于这些关系，举行q次变乱，格式为【op，u，v】，其中u和v表示人的编号。op表示要举行哪种操作，当op==1时，u和v的朋侪关系淡忘，也就是断开u和v的朋侪关系。当op==2时，表示查询u和v是否可以创建朋侪关系，可以通过第三方大概原来就是朋侪关系。
针对每次的op==2操作，返回一个效果Yes or No，表示是否可以创建朋侪关系 。
【思路】
这n个人中存在许多的朋侪关系，比如编号1-5是朋侪，编号6-10是朋侪，这两个关系是独立的集合，以是可以想到的是利用并查集来记录朋侪关系。
   并查集传送门：
  【算法与数据结构】并查集详解+题目_并查集结构体-CSDN博客
   并查会集的每个集合可以看成是一棵树，独立多个集合，就是多个独立的树。每个树的根节点也就是每个集合的父节点。

---

   刚开始我的思路是将这m个朋侪关系，利用并查集来存储。
  但是在q次操作中，op=2是查询是否可以 创建朋侪关系的操作，这个简单，只需判断这两个人是否在同一个集合中，也就是这两个人的父节点是否相同。但是对于op=1删除朋侪关系操作，比力困难，因为并查集擅于举行 添加关系操作的，倒霉益理删除节点关系。以是在删除朋侪关系这里出现了问题。
    我们可以试着把删除朋侪关系酿成添加朋侪关系。这样并查集就可以做了。那么怎么实现呢？
  我们可以先将这m个朋侪关系用特定的容器存储下来，起首遍历q次操作，遇到删除操作（u，v)，在容器中删除（u，v)。
  留意：这里删除的时候，要删除的朋侪关系是（u，v），有大概存储的时候，朋侪关系是（u，v)，也有大概是（v，u），这些都是要删除的。
  遇到op=2时，不举行操作。一次操作完成后，将该次操作用数组记录下来【op，u，v】。
  

---

  次序遍历完后，此时将容器中剩余的朋侪关系，构建并查集。 然后逆序遍历记录操作的数组，遇到op=1时，就添加朋侪关系，遇到op=2时，就查询朋侪关系，判断父节点是否相等即可。
   【代码】

1. //小美的朋友关系
2. #include <iostream>
3. #include <vector>
4. #include <set>
5. using namespace std;
6. const int N = 1e5;
8. //总人数，初始的朋友关系数，事件数量
9. int n, m, q;
10. vector<int> parent;//并查集
11. set<pair<int, int>> st;//存储初始的朋友关系
12. //存储事件
13. struct node
14. {
15.         int op, u, v;
16. }arr[N+5];
17. //找父节点,路径压缩
18. int find(int x)
19. {
20.         if (parent[x] != x)
21.                 parent[x] = find(parent[x]);
22.         return parent[x];
23. }
24. //合并
25. void unite(int x, int y)
26. {
27.         int rootX = find(x);
28.         int rootY = find(y);
29.         if (rootX == rootY)
30.                 return;
31.         parent[rootX] = rootY;
32. }
33. int main()
34. {
35.         cin >> n >> m >> q;
36.         //初始化并查集
37.         parent.resize(n + 1);
38.         for (int i = 1; i <= n; i++)
39.                 parent[i] = i;
40.         //存储关系
41.         int op,u, v;
42.         while (m--)
43.         {
44.                 cin >> u >> v;
45.                 st.insert({ u,v });
46.         }
47.         int num = 0;
48.         while (q--)
49.         {
50.                 cin >> op >> u >> v;
51.                 //处理删除操作
52.                 if (op == 1)
53.                 {
54.                         if (st.find({ u,v }) != st.end())
55.                                 st.erase({ u,v });
56.                         else if (st.find({ v,u }) != st.end())
57.                                 st.erase({ v,u });
58.                         else
59.                                 continue;//说明u和v表示朋友关系，此次删除操作无意义，不需要存储下来
60.                 }
61.                 //记录操作
62.                 arr[num++] = { op,u,v };
63.         }
64.         //删除关系完成后，剩余的元素是没有进行操作的
65.         //构建并查集
66.         for (auto [u, v] : st)
67.                 unite(u, v);
68.         vector<bool> ans;//记录最终结果
70.         //逆序遍历操作
71.         //如果是删除就进行合并
72.         //如果是查询就进行判断是否在同一个集合
73.         for (int i = num - 1; i >= 0; i--)
74.         {
75.                 op = arr[i].op, u = arr[i].u, v = arr[i].v;
76.                 if (op == 1)
77.                 {
78.                         //合并
79.                         unite(u, v);
80.                 }
81.                 else
82.                 {
83.                         //判断
84.                         ans.emplace_back(find(u) == find(v));
85.                 }
86.         }
88.         for (int i = ans.size() - 1; i >= 0; i--)
89.                 if (ans[i])
90.                         cout << "Yes" << endl;
91.                 else
92.                         cout << "No" << endl;
94.         return 0;
95. }

复制代码

上述代码是利用vector来实现并查集的，题目中的数据范围n是1e9，如果利用vector，就需要开辟1e9个空间，会超出内存限定。以是这里实现并查集的时候，需要利用map来替换。存储当前节点和它的父节点。具体原因，看下方：

   初始时，每个节点的父节点就是本身本身。比如mp[1]=1。
  

---

  当我们逆序遍历时，当遇到op=2，查询朋侪关系时，给的两个朋侪编号u和v，之前大概没初始化。比如n=10，给了3个朋侪关系（1，3），（3，2），（4，6），当我们查询的时候，大概查询的是（5，7），这两个节点没有初始化，也就是mp[5]=0,mp[7]=0，可以发现这两个节点的父节点都是0，如果直接判断，得到的效果是可以构成朋侪关系，但本质是不能构成朋侪关系的。
  

---

  也可以看下方代码的初始化部分，我们只初始化了存在朋侪关系的节点，其他的节点没有初始化，他们的父节点默认就是0。如果我们开始将所有节点都初始化好，那么就会超出内存限定，那么就和利用vector一样了，甚至占用的内存比vector还要大，以是我们不能一次性就初始还所有节点。而是当遇到一个没初始化的节点，就初始化即可。
  

---

  以是在查询操作的时候，如果mp=0，大概mp[v]=0，就把这两个值做一下初始化mp=u大概mp[v]=v，这样在判断的时候就不会出错了。
  

---

  而如果利用的是vector来表示并查集，是不需要考虑这个问题的，因为vector会开辟n个空间，将所有人都初始化好，父节点就是本身。而利用map来存储，只会存储存在朋侪关系的节点，如果出现一个新的节点，需要我们本身再初始化。这也就是map不会超出内存限定而vector会超出内存限定的原因。
   【代码】

1. //小美的朋友关系
2. #include <iostream>
3. #include <vector>
4. #include <map>
5. #include <set>
6. using namespace std;
7. const int N = 1e5;
9. //总人数，初始的朋友关系数，事件数量
10. int n, m, q;
11. map<int,int> parent;//并查集
12. set<pair<int, int>> st;//存储初始的朋友关系
14. //存储事件
15. struct node
16. {
17.         int op, u, v;
18. }arr[N + 5];
19. //找父节点,路径压缩
20. int find(int x)
21. {
22.         if (parent[x] != x)
23.                 parent[x] = find(parent[x]);
24.         return parent[x];
25. }
26. //合并
27. void unite(int x, int y)
28. {
29.         int rootX = find(x);
30.         int rootY = find(y);
31.         if (rootX == rootY)
32.                 return;
33.         parent[rootX] = rootY;
34. }
35. int main()
36. {
37.         cin >> n >> m >> q;
38.         //初始化并查集和关系集合
39.         int op, u, v;
40.         for (int i = 0; i < m; i++)
41.         {
42.                 cin >> u >> v;
43.                 parent[u] = u;
44.                 parent[v] = v;
45.                 st.insert({ u,v });
46.         }
47.         int num = 0;
48.         while (q--)
49.         {
50.                 cin >> op >> u >> v;
51.                 //处理删除操作
52.                 if (op == 1)
53.                 {
54.                         if (st.find({ u,v }) != st.end())
55.                                 st.erase({ u,v });
56.                         else if (st.find({ v,u }) != st.end())
57.                                 st.erase({ v,u });
58.                         else
59.                                 continue;//说明u和v表示朋友关系，此次删除操作无意义，不需要存储下来
60.                 }
61.                 //记录操作
62.                 arr[num++] = { op,u,v };
63.         }
64.         //删除关系完成后，剩余的元素是没有进行操作的
65.         //构建并查集
66.         for (auto [u, v] : st)
67.                 unite(u, v);
68.         vector<bool> ans;//记录最终结果
70.         //逆序遍历操作
71.         //如果是删除就进行合并
72.         //如果是查询就进行判断是否在同一个集合
73.         for (int i = num - 1; i >= 0; i--)
74.         {
75.                 op = arr[i].op, u = arr[i].u, v = arr[i].v;
76.                 if (op == 1)
77.                 {
78.                         //合并
79.                         unite(u, v);
80.                 }
81.                 else
82.                 {
83.                         //parent[u]==0，说明该节点第一次出现，初始化为u
84.                         if (parent[u] == 0)
85.                                 parent[u] = u;
86.                         if (parent[v] == 0)
87.                                 parent[v] = v;
88.                         //判断
89.                         ans.emplace_back(find(u) == find(v));
90.                 }
91.         }
93.         for (int i = ans.size() - 1; i >= 0; i--)
94.                 if (ans[i])
95.                         cout << "Yes" << endl;
96.                 else
97.                         cout << "No" << endl;
99.         return 0;
100. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。