当前位置:   article > 正文

【刷题节】美团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+k1,y=j+k1
  • 则字符 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[i1][y]s[x][j1]+s[i1][j1],字符 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;
    }      
}
  • 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

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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

3. 小美的 MT

题目链接:小美的 MT —— 牛客网

3.1 解题思路

语法基础: 顺序结构
时间复杂度: O ( n ) O(n) O(n)

遍历一遍,找出字符串中 MT 的字符数量 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);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

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 uv 时,不能仅仅删除 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;
}
  • 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
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

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,l1],[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} TwonTwor+Twol1,同理 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} FivenFiver+Fivel1
  • 那么末尾 0 0 0 的个数就是两者中的最小值。

5.1.2 删除区间的计数问题分析:

  • 首先我们假设已知 下标为 [ l , r ] [l, r] [l,r],区间长度 l e n = r − l + 1 len = r - l + 1 len=rl+1 的区间 可以删除。
    那么我们可以删除这个区间中任意连续子区间。
    子区间长度为 1 1 1,有 l e n len len 种方案;长度为 2 2 2,有 l e n − 1 len-1 len1 方案; … \dots ,长度为 n n n,有 l e n − n + 1 len-n+1 lenn+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 103310 为例,保证剩余元素乘积至少有一个 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,r1] 就是以 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;
}
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/435466
推荐阅读
相关标签
  

闽ICP备14008679号