美团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个整数。

【代码】

#include <iostream>
#include <vector>
using namespace std;const int N = 205;
int arr[N][N], s[N][N];
//s为前缀和数组
//统计矩形(1,1)到(n,n)中1的数量int main()
{int n = 0;cin >> n;for(int  i=1;i<=n;i++)for (int j = 1; j <= n; j++){scanf("%1d", &arr[i][j]);s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j];}cout << 0 << endl;for (int k = 2; k <= n; k++){if (k & 1){cout << 0 << endl;continue;}int ans = 0;for(int i=1;i+k-1<=n;i++)for (int j = 1; j+k-1 <= n; j++){//(i,j)是左上角，需要我们计算出k*k这个区域右下角的坐标int x = i + k - 1;int y = j + k - 1;if (s[x][y] - s[i - 1][y] - s[x][j - 1] + s[i - 1][j - 1] == k * k / 2)ans++;}cout << ans << endl;}return 0;
}

2，小美的数组询问

 直接遍历即可 

#include <iostream>
using namespace std;const int N=1e5+10;
int arr[N];
int main()
{int n=0,q=0;cin>>n>>q;long long sum=0,count=0;for(int i=1;i<=n;i++){cin>>arr[i];sum+=arr[i];if(arr[i]==0)count++;}int l,r;while(q--){cin>>l>>r;cout<<sum+count*l<<" "<<sum+count*r<<endl;}return 0;
}

3，小美的MT

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

//小美的MT
#include <iostream>
#include <string>
using namespace std;int main()
{int n = 0, k = 0;cin >> n >> k;string str;cin >> str;int ans = 0;for (int i = 0; i < n; i++){if (str[i] == 'M' || str[i] == 'T')ans++;}if (k > n - ans)cout << n << endl;elsecout << ans + k << endl;return 0;
}

 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时，就查询朋友关系，判断父节点是否相等即可。

 【代码】

//小美的朋友关系
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 1e5;//总人数，初始的朋友关系数，事件数量
int n, m, q;
vector<int> parent;//并查集
set<pair<int, int>> st;//存储初始的朋友关系
//存储事件
struct node
{int op, u, v;
}arr[N+5];
//找父节点,路径压缩
int find(int x)
{if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];
}
//合并
void unite(int x, int y)
{int rootX = find(x);int rootY = find(y);if (rootX == rootY)return;parent[rootX] = rootY;
}
int main()
{cin >> n >> m >> q;//初始化并查集parent.resize(n + 1);for (int i = 1; i <= n; i++)parent[i] = i;//存储关系int op,u, v;while (m--){cin >> u >> v;st.insert({ u,v });}int num = 0;while (q--){cin >> op >> u >> v;//处理删除操作if (op == 1){if (st.find({ u,v }) != st.end())st.erase({ u,v });else if (st.find({ v,u }) != st.end())st.erase({ v,u });elsecontinue;//说明u和v表示朋友关系，此次删除操作无意义，不需要存储下来}//记录操作arr[num++] = { op,u,v };}//删除关系完成后，剩余的元素是没有进行操作的//构建并查集for (auto [u, v] : st)unite(u, v);vector<bool> ans;//记录最终结果//逆序遍历操作//如果是删除就进行合并//如果是查询就进行判断是否在同一个集合for (int i = num - 1; i >= 0; i--){op = arr[i].op, u = arr[i].u, v = arr[i].v;if (op == 1){//合并unite(u, v);}else{//判断ans.emplace_back(find(u) == find(v));}}for (int i = ans.size() - 1; i >= 0; i--)if (ans[i])cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}

上述代码是使用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[u]=0，或者mp[v]=0，就把这两个值做一下初始化mp[u]=u或者mp[v]=v，这样在判断的时候就不会出错了。

---

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

 【代码】

//小美的朋友关系
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N = 1e5;//总人数，初始的朋友关系数，事件数量
int n, m, q;
map<int,int> parent;//并查集
set<pair<int, int>> st;//存储初始的朋友关系//存储事件
struct node
{int op, u, v;
}arr[N + 5];
//找父节点,路径压缩
int find(int x)
{if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];
}
//合并
void unite(int x, int y)
{int rootX = find(x);int rootY = find(y);if (rootX == rootY)return;parent[rootX] = rootY;
}
int main()
{cin >> n >> m >> q;//初始化并查集和关系集合int op, u, v;for (int i = 0; i < m; i++){cin >> u >> v;parent[u] = u;parent[v] = v;st.insert({ u,v });}int num = 0;while (q--){cin >> op >> u >> v;//处理删除操作if (op == 1){if (st.find({ u,v }) != st.end())st.erase({ u,v });else if (st.find({ v,u }) != st.end())st.erase({ v,u });elsecontinue;//说明u和v表示朋友关系，此次删除操作无意义，不需要存储下来}//记录操作arr[num++] = { op,u,v };}//删除关系完成后，剩余的元素是没有进行操作的//构建并查集for (auto [u, v] : st)unite(u, v);vector<bool> ans;//记录最终结果//逆序遍历操作//如果是删除就进行合并//如果是查询就进行判断是否在同一个集合for (int i = num - 1; i >= 0; i--){op = arr[i].op, u = arr[i].u, v = arr[i].v;if (op == 1){//合并unite(u, v);}else{//parent[u]==0，说明该节点第一次出现，初始化为uif (parent[u] == 0)parent[u] = u;if (parent[v] == 0)parent[v] = v;//判断ans.emplace_back(find(u) == find(v));}}for (int i = ans.size() - 1; i >= 0; i--)if (ans[i])cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}