【刷题节】美团2024年春招第一场笔试【算法策略】题解 |
您所在的位置：网站首页 › 美团错过笔试 › 【刷题节】美团2024年春招第一场笔试【算法策略】题解 |
【刷题节】美团2024年春招第一场笔试【算法策略】题解
|
目录
前言 —— 瞎扯淡1. 小美的平衡矩阵1.1 解题思路1.2 AC代码
2. 小美的数组询问2.1 解题思路2.2 AC代码
3. 小美的 MT3.1 解题思路3.2 AC代码
4. 小美的朋友关系4.1 解题思路4.2 AC代码
5. 小美的区间删除5.1 解题思路5.2 AC代码
前言 —— 瞎扯淡
背景一 目前，我所搜索到的全网博文关于 小美的朋友关系 都没有通过的代码。思路是正确的，但是代码都是超时或答案错误。鉴于目前官方也没有发布题解，遂写此篇博客供大家交流学习 背景二 中午午休的时候，科科公主给我甩来一个链接，让我陪她一起做题。做了 80 80 80 分钟左右，把除了 小美朋友关系 其他题目写完，就去上课了。后面吃完晚饭，又补了 小美朋友关系 这道题。 整体评价 美团的算法笔试，没有我想象的那么难。 我之前看大厂招算法岗，都需要研究生学历。所以期望值很高，做了一下发现不是太难。大概就等同于中学OI的普及组难度。
题目链接：小美的平衡矩阵 —— 牛客网 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 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 if(k&1){// 当边长为奇数时，字符 1的数量不可能等于字符 0的数量 cout int n, q; cin >> n >> q; long long sum = 0; int cnt = 0; for(int i=0; i int l, r; cin >> l >> r; cout if(s[i] =='M' || s[i]=='T') cnt++; } cout // 路径压缩 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; setst;// 关系集合 for(int i=0, u, v; iu, v}); // u, v放进关系集合中 f[u] = u, f[v] = v;// 把出现的结点父节点设置为自己 } int num = 0;// 新的操作数组长度 for(int i=0; i // 可能是 {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); vectorans;// 存储答案 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 int k; cin >> n >> k; for(int i=1; i> a[i]; for(int i=1; i j = max(j, i);// 当 i右移超过j后，j不能比 i小，所以需要更新一下 while(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 |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |