美团2024年春招第一场笔试 C++
目录1，小美的均衡矩阵
2，小美的数组询问
3，小美的MT
4，小美的朋侪关系
1，小美的均衡矩阵
https://i-blog.csdnimg.cn/direct/39c3442b96f94070a91a42560310b5f6.png
【题目描述】
给定一个n*n的矩阵，该矩阵只包含数字0和1。对于 每个i(1<=i<=n)，求在该矩阵中，有多少个i*i的区域满足0的个数等于1的个数？？？
【题目解析】
示例演示：
https://i-blog.csdnimg.cn/direct/6c8bdea3c4564c9e8de3aa857e69bc8d.png
如上图，1*1的区域效果为0，2*2的区域效果为7。
算法：前缀和+遍历
题目中给的数据范围是n<=200，以是可以直接遍历数组。
维护 一个前缀和数组统计以（x，y）这个点为右下角，以（1，1）这个点为左上角，这个区域中所有元素的和，由于数组中的数要么是0，要么是1，所从前缀和就表示某个区域中1的个数。
有了前缀和数组，就可以快速 求出某个区域中1的个数，如图：https://i-blog.csdnimg.cn/direct/f3e1e30d4a7240efaf2377e78ff4c862.png
而这个区域的大小我们是知道的，假设是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, s;
//s为前缀和数组
//统计矩形(1,1)到(n,n)中1的数量
int main()
{
int n = 0;
cin >> n;
for(inti=1;i<=n;i++)
for (int j = 1; j <= n; j++)
{
scanf("%1d", &arr);
s = s + s - s + arr;
}
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 - s - s + s == k * k / 2)
ans++;
}
cout << ans << endl;
}
return 0;
} 2，小美的数组询问
https://i-blog.csdnimg.cn/direct/fce34b71d37f4411adf3aac4626b6714.png
直接遍历即可
#include <iostream>
using namespace std;
const int N=1e5+10;
int arr;
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;
sum+=arr;
if(arr==0)
count++;
}
int l,r;
while(q--)
{
cin>>l>>r;
cout<<sum+count*l<<" "<<sum+count*r<<endl;
}
return 0;
} 3，小美的MT
https://i-blog.csdnimg.cn/direct/846434a2b68e495493cce84c5e47505a.png
统计元字符中 有多少个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 == 'M' || str == 'T')
ans++;
}
if (k > n - ans)
cout << n << endl;
else
cout << ans + k << endl;
return 0;
} 4，小美的朋侪关系
https://i-blog.csdnimg.cn/direct/42b4311909f64ab2b6c792186d90bd4c.png
https://i-blog.csdnimg.cn/direct/77b48dd9b21b44dd921e0b285a60e9cf.png
【题目描述】
总人数为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;
//找父节点,路径压缩
int find(int x)
{
if (parent != x)
parent = find(parent);
return parent;
}
//合并
void unite(int x, int y)
{
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY)
return;
parent = rootY;
}
int main()
{
cin >> n >> m >> q;
//初始化并查集
parent.resize(n + 1);
for (int i = 1; i <= n; i++)
parent = 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 });
else
continue;//说明u和v表示朋友关系，此次删除操作无意义，不需要存储下来
}
//记录操作
arr = { op,u,v };
}
//删除关系完成后，剩余的元素是没有进行操作的
//构建并查集
for (auto : st)
unite(u, v);
vector<bool> ans;//记录最终结果
//逆序遍历操作
//如果是删除就进行合并
//如果是查询就进行判断是否在同一个集合
for (int i = num - 1; i >= 0; i--)
{
op = arr.op, u = arr.u, v = arr.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)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
上述代码是利用vector来实现并查集的，题目中的数据范围n是1e9，如果利用vector，就需要开辟1e9个空间，会超出内存限定。以是这里实现并查集的时候，需要利用map来替换。存储当前节点和它的父节点。具体原因，看下方：
https://i-blog.csdnimg.cn/direct/e50811b1feb9459fbb76ee115d8b9d53.png
初始时，每个节点的父节点就是本身本身。比如mp=1。
当我们逆序遍历时，当遇到op=2，查询朋侪关系时，给的两个朋侪编号u和v，之前大概没初始化。比如n=10，给了3个朋侪关系（1，3），（3，2），（4，6），当我们查询的时候，大概查询的是（5，7），这两个节点没有初始化，也就是mp=0,mp=0，可以发现这两个节点的父节点都是0，如果直接判断，得到的效果是可以构成朋侪关系，但本质是不能构成朋侪关系的。
也可以看下方代码的初始化部分，我们只初始化了存在朋侪关系的节点，其他的节点没有初始化，他们的父节点默认就是0。如果我们开始将所有节点都初始化好，那么就会超出内存限定，那么就和利用vector一样了，甚至占用的内存比vector还要大，以是我们不能一次性就初始还所有节点。而是当遇到一个没初始化的节点，就初始化即可。
以是在查询操作的时候，如果mp=0，大概mp=0，就把这两个值做一下初始化mp=u大概mp=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;
//找父节点,路径压缩
int find(int x)
{
if (parent != x)
parent = find(parent);
return parent;
}
//合并
void unite(int x, int y)
{
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY)
return;
parent = rootY;
}
int main()
{
cin >> n >> m >> q;
//初始化并查集和关系集合
int op, u, v;
for (int i = 0; i < m; i++)
{
cin >> u >> v;
parent = u;
parent = 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 });
else
continue;//说明u和v表示朋友关系，此次删除操作无意义，不需要存储下来
}
//记录操作
arr = { op,u,v };
}
//删除关系完成后，剩余的元素是没有进行操作的
//构建并查集
for (auto : st)
unite(u, v);
vector<bool> ans;//记录最终结果
//逆序遍历操作
//如果是删除就进行合并
//如果是查询就进行判断是否在同一个集合
for (int i = num - 1; i >= 0; i--)
{
op = arr.op, u = arr.u, v = arr.v;
if (op == 1)
{
//合并
unite(u, v);
}
else
{
//parent==0，说明该节点第一次出现，初始化为u
if (parent == 0)
parent = u;
if (parent == 0)
parent = v;
//判断
ans.emplace_back(find(u) == find(v));
}
}
for (int i = ans.size() - 1; i >= 0; i--)
if (ans)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]