
【刷题节】美团2024年春招第一场笔试【算法策略】题解
目录
前言 —— 瞎扯淡
背景一
目前,我所搜索到的全网博文关于小美的朋友关系
都没有通过的代码。思路是正确的,但是代码都是超时或答案错误。鉴于目前官方也没有发布题解,遂写此篇博客供大家交流学习
背景二
中午午休的时候,科科公主给我甩来一个链接,让我陪她一起做题。做了 80 80 80 分钟左右,把除了小美朋友关系
其他题目写完,就去上课了。后面吃完晚饭,又补了小美朋友关系
这道题。
整体评价
美团的算法笔试,没有我想象的那么难。
我之前看大厂招算法岗,都需要研究生学历。所以期望值很高,做了一下发现不是太难。大概就等同于中学OI的普及组难度。
1. 小美的平衡矩阵
题目链接:小美的平衡矩阵 —— 牛客网
1.1 解题思路
算法思想:
前缀和+遍历
时间复杂度:
O
(
n
3
)
O(n^3)
O(n3)
n n n 的数据量只有 200 200 200,依次遍历矩形边长 k ∈ [ 1 , n ] k \in [1, n] k∈[1,n]:
- 对于每个矩形,已知边长 k k k,只用每次遍历矩形的左上定点,就可以确定整个矩形范围。
- 然后统计该矩形中 01 的具体数量,判断是否相等。
而这一步可以使用前缀和,建立数组 S [ n ] [ m ] S[n][m] S[n][m],来统计矩形 ( 1 , 1 ) (1,1) (1,1) 到 ( n , m ) (n,m) (n,m) 中 1 1 1 的数量。 - 那么对于 左上顶点 ( i , j ) (i,j) (i,j) 的矩阵,右下顶点即为 ( x , y ) (x, y) (x,y),其中 x = i + k − 1 , y = j + k − 1 x=i+k-1, y=j+k-1 x=i+k−1,y=j+k−1 。
- 则字符 1 1 1 的数量即为 s [ x ] [ y ] − s [ i − 1 ] [ y ] − s [ x ] [ j − 1 ] + s [ i − 1 ] [ j − 1 ] s[x][y] - s[i-1][y] - s[x][j-1] + s[i-1][j-1] s[x][y]−s[i−1][y]−s[x][j−1]+s[i−1][j−1],字符 0 0 0 的数量为 k × k 2 \frac{k\times k}{2} 2k×k。
1.2 AC代码
#include <iostream>
using namespace std;
const int N = 200;
int a[N][N], s[N][N];// a为原数组,s为前缀和数组
int main() {
int n; cin >> n;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++){
scanf("%1d", &a[i][j]);
s[i][j] = s[i-1][j] + s[i][j-1] + a[i][j] - s[i-1][j-1];
}
for(int k=1; k<=n; k++){
if(k&1){// 当边长为奇数时,字符 1的数量不可能等于字符 0的数量
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++){
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;
}
}
2. 小美的数组询问
题目链接:小美的数组询问 —— 牛客网
2.1 解题思路
语法基础:
循环结构
时间复杂度:
O
(
n
+
q
)
O(n+q)
O(n+q)
- 统计数组中 0 0 0 的个数 c n t cnt cnt,以及数组的累加总和 s u m sum sum。
- 对于每一个 [ l , r ] [l,r] [l,r] 区间,最小值为 s u m + c n t × l sum+cnt\times l sum+cnt×l,最大值为 s u m + c n t × r sum + cnt\times r sum+cnt×r。
2.2 AC代码
#include <iostream>
using namespace std;
const int N = 1e5;
long long a[N+5];
int main() {
int n, q; cin >> n >> q;
long long sum = 0;
int cnt = 0;
for(int i=0; i<n; i++) {
cin >> a[i], sum += a[i];
if(!a[i]) cnt++;
}
while(q--){
int l, r; cin >> l >> r;
cout << sum + cnt * l <<" "<<sum + cnt * r << endl;
}
}
3. 小美的 MT
题目链接:小美的 MT —— 牛客网
3.1 解题思路
语法基础:
顺序结构
时间复杂度:
O
(
n
)
O(n)
O(n)
遍历一遍,找出字符串中 M
和 T
的字符数量
c
n
t
cnt
cnt,答案即为
c
n
t
+
k
cnt + k
cnt+k 和
n
n
n 的最小值。
3.2 AC代码
#include <iostream>
using namespace std;
int main() {
int n, q; cin >> n >> q;
string s; cin >> s;
int cnt = 0;
for(int i=0; i<s.length(); i++){
if(s[i] =='M' || s[i]=='T') cnt++;
}
cout << min(n, cnt+q);
}
4. 小美的朋友关系
题目链接:小美的朋友关系 —— 牛客网
4.1 解题思路
算法思想:
逆向构建并查集
时间复杂度:
O
(
m
log
m
)
O(m\log m)
O(mlogm)
该题与一个并查集的经典题目 P1197 [JSOI2008] 星球大战 相似,都是用逆向思维维护并查集。
删除结点关系并不好处理,但是如果我们逆向进行 q q q 次操作,先构建出操作之后最终的关系网,然后倒着重新进行操作。那么此时删除关系,就变为了添加关系。而并查集就是处理关系的一把好手。
- 所以,第一步得到最终的关系网。我们先用 s t st st 集合,记录下结点之间的关系。然后,遍历一遍 q q q 次操作,当操作为删除关系的时候,我们就删去集合中的关系。我们根据删除后的结点建立一个并查集。
- 然后,我们倒着对 q q q 次操作进行遍历。当询问结点 u , v u, v u,v 的时候,我们就判断 u u u 和 v v v 的父节点是否相同。当遇到删除 u , v u, v u,v 操作的时候,我们就添加 u , v u, v u,v 的关系。
易错点提示:
- 结点范围为
1
e
9
1e9
1e9,所以要父节点数组要用
map
存储; - 因为数据量很大,所以需要路径压缩,降低时限。所以需要初始化
f
[
i
]
=
i
f[i] = i
f[i]=i。
但是,不能按照并查集模板中init()
操作一样,从 1 1 1 到 1 e 9 1e9 1e9 循环 f [ i ] = i f[i] = i f[i]=i。只有当出现的结点,我们才需要 f [ i ] = i f[i] = i f[i]=i,所以不用全部赋值,会超时! - 当正着从关系集合中,删除 u , v u,v u,v 时,不能仅仅删除 u , v u, v u,v,还要考虑关系集合中是以 v , u v, u v,u 的形式存储;
- 倒着遍历的时候,如果遇到删除结点 u , v u, v u,v 的操作,如果 u , v u, v u,v 原本就没有关系,是不可以添加的;所以不妨新建一个操作数组 o r d ord ord,将查询操作和删除关系集合中存在结点的命令单独存储,把删除关系集合中不存在的这种干扰操作舍掉;
4.2 AC代码
#include <iostream>
#include <set>
#include <vector>
#include <map>
using namespace std;
const int N = 1e5;
using PII = pair<int,int>;
int n, m, q;
map<int,int>f;// 并查集父亲数组
struct node{
int op, u, v;
}ord[N+5];// 新的操作数组
int find(int x){// 路径压缩
while(f[x] != x) x = f[x] = f[f[x]];
return x;
}
void merge(int u,int v){// 并查集合并
int fa = find(u);
int fb = find(v);
f[fb] = fa;
}
int main() {
cin >> n >> m >> q;
set<PII>st;// 关系集合
for(int i=0, u, v; i<m; i++){
cin >> u >> v;
st.insert({u, v}); // u, v放进关系集合中
f[u] = u, f[v] = v;// 把出现的结点父节点设置为自己
}
int num = 0;// 新的操作数组长度
for(int i=0; i<q; i++){
int op, u, v; cin >> op >> u >> v;
//如果是查询操作,可以直接存入
// 如果是删除操作,需要判断原关系集合中是否存在
if(op == 1){
// 可能是 {u,v} 形式存储
if(st.find({u, v}) != st.end()) st.erase({u, v});
// 可能是 {v,u} 形式存储
else if(st.find({v, u}) != st.end()) st.erase({v, u});
// 如果不存在直接跳过,不储存此次删除操作
else continue;
}
// 存入新的操作数组中
ord[num++] = {op, u, v};
}
// 删除之后,剩余关系集合就是没有涉及到的,也是最终的并查集
for(auto [u,v]:st) merge(u, v);
vector<bool>ans;// 存储答案
for(int i=num-1; i>=0; i--){// 倒着重新进行操作
int op = ord[i].op, u = ord[i].u, v = ord[i].v;
if(op == 1) merge(u, v);// 如果是删除操作,反过来进行合并
else{
// 当 f[u] = 0时,就是第一次出现该节点,需要初始化f[i]=i,方便进行路径压缩
if(!f[u]) f[u] = u;
if(!f[v]) f[v] = v;
ans.emplace_back(find(u) == find(v));// 查询操作,就储存答案
}
}
//因为是倒着遍历操作的,所以答案是倒着存储的
for(int i=ans.size()-1; i>=0; i--)
if(ans[i]) cout << "Yes" << endl;
else cout << "No" << endl;
}
5. 小美的区间删除
题目链接:小美的区间删除 —— 牛客网
5.1 解题思路
算法思想:
双指针、前缀和、容斥定理、一点点数论小知识
时间复杂度:
最坏时间复杂度:
O
(
w
×
n
)
,
w
=
log
(
1
e
9
)
O(w\times n),w=\log(1e9)
O(w×n),w=log(1e9)
5. 1. 1 乘积末尾 0 0 0 的个数问题分析:
- 对于乘积会产生 0 0 0 的,本质上都是由 2 2 2 与 5 5 5 的乘积产生。如 5 × 6 = 30 5\times 6 = 30 5×6=30,这个10的产生过程为 5 × 2 = 10 , 10 × 3 = 30 5 \times 2 = 10, 10 \times 3 = 30 5×2=10,10×3=30 。所以要求末尾 0 0 0 的个数,只用知道乘数中有多少 5 5 5 和 2 2 2 的数量,乘积 0 0 0 的数量就是两者取最小值。
- 所以我们只需用前缀和预处理出数组中 2 2 2 和 5 5 5 的个数 T w o , F i v e Two, Five Two,Five。
- 当去掉区间
[
l
,
r
]
[l,r]
[l,r], 则剩下区间
[
1
,
l
−
1
]
,
[
r
+
1
,
n
]
[1,l-1], [r+1,n]
[1,l−1],[r+1,n]。
那么 2 2 2 的个数即为两个区间内个数之和 T w o n − T w o r + T w o l − 1 Two_n - Two_r + Two_{l-1} Twon−Twor+Twol−1,同理 5 5 5 的个数为 F i v e n − F i v e r + F i v e l − 1 Five_n - Five_r+Five_{l-1} Fiven−Fiver+Fivel−1。 - 那么末尾 0 0 0 的个数就是两者中的最小值。
5.1.2 删除区间的计数问题分析:
- 首先我们假设已知 下标为
[
l
,
r
]
[l, r]
[l,r],区间长度
l
e
n
=
r
−
l
+
1
len = r - l + 1
len=r−l+1 的区间 可以删除。
那么我们可以删除这个区间中任意连续子区间。
子区间长度为 1 1 1,有 l e n len len 种方案;长度为 2 2 2,有 l e n − 1 len-1 len−1 方案; … \dots …,长度为 n n n,有 l e n − n + 1 len-n+1 len−n+1种方案。即这个区间内总删除方案数有 ( 1 + l e n ) × l e n 2 \frac{(1+len)\times len}{2} 2(1+len)×len。 - 有上面分析之后,我们统计所有删除方案,只需要找到可以删除的最长区间,然后利用上面公式,就可以求出该区间的所有删除方案。
所以现在问题转化为求解可删除的最长区间。
以数组 10 , 3 , 3 , 10 10, 3,3,10 10,3,3,10 为例,保证剩余元素乘积至少有一个 0 0 0。
-
我们可以利用双指针,固定区间左边界 l l l,不断移动区间右边界 r r r,利用5.1.1 方法判断末尾 0 0 0 的个数,直至使得删除 [ l , r ] [l,r] [l,r] 后,末尾 0 0 0 的个数小于 k k k, r r r 停止右移动。那么此时, [ l , r − 1 ] [l,r-1] [l,r−1] 就是以 l l l 为左边界,最长的连续区间范围。
按上述例子,即 l = 1 , r = 4 l = 1, r = 4 l=1,r=4时停止移动,此时最大删除区间为 [ 1 , 3 ] [1, 3] [1,3]。 -
统计完一个区间之后,要移动 l l l 的值,找到新的可以删除区间。
也就是右移动 l l l 直到剩余区间的 0 0 0 的个数再次不小于 k k k时停止;或者 l l l 与 r r r 重合时停止。此时就可以再次固定 l l l 的位置,不断探测找到最大 r r r 值。
按上述例子, l l l 移动到下标 2 2 2 时,剩余元素乘积末尾的 0 0 0 再次不小于 1 1 1。然后以 l = 2 l = 2 l=2 再次探测最长区间。即 l = 2 , r = 5 l = 2, r = 5 l=2,r=5时停止移动,此时最大删除区间为 [ 2 , 4 ] [2, 4] [2,4]。 -
根据上述的例子,我们不难看出两次最长区间 [ 1 , 3 ] , [ 2 , 4 ] [1,3] , [2,4] [1,3],[2,4] 中有一段重叠区间。这个区间在第一次时已经被统计进删除方案了,第二次又被统计了一次。根据容斥定理,我们要把这一段重复的方案数再减掉。
至此,这个题目的解题思路就结束了。
5.2 AC代码
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e5;
int n, a[N+5];
// two为前i个数中2的个数,five为前i个数中5的个数
int two[N+5], five[N+5];
int get(int i, int j){
// 即2.1.1方案,求出去掉区间[i,j]后乘积末尾 0的个数
return min(two[n]-two[j]+two[i-1], five[i-1]+five[n]-five[j]);
}
int main() {
int k; cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++){
// 求因子2,5的个数
while(a[i]%2==0) two[i]++, a[i]/=2;
while(a[i]%5==0) five[i]++, a[i]/=5;
// 维护前缀和
two[i] += two[i-1];
five[i] += five[i-1];
}
int l = 0, r = 0;// 记录上一次删除区间,防止重复相加
long long ans = 0;
for(int i=1, j=1; i<=n && j<=n; ){
j = max(j, i);// 当 i右移超过j后,j不能比 i小,所以需要更新一下
while(j <=n && get(i, j) >= k) j++;//当剩余区间值不小于k,就不断向右移
ans += 1LL*(j-i)*(j-i+1)/2;// 删除方案即该区间的等差数列公式
if(r >= i) ans -= 1LL*(r-i)*(r-i+1)/2;
//如果上一个区间[l,r]的右端点不小于本次区间[i,j]的左端点,则产生重复需要删去 [i, r]方案数
l = i, r = j;//上次删除区间更新为[i,j]
while(i <= j && get(i, j)<k) i++;//右移i,直到再次可以删除 或 左右边界重合 停止
}
cout << ans;
}
更多推荐








所有评论(0)