【笔试】美团2023年秋招第1场笔试（后端数开软件方向）

2024-03-26 12:12
文章标签 笔试 2023 软件 方向 后端 美团 年秋招 数开

本文主要是介绍【笔试】美团2023年秋招第1场笔试（后端数开软件方向），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

      • T1 小美玩排列
      • T2 小美走公路
      • T3 小美切蛋糕
      • T4 小美将字符串平铺成矩阵
      • T5 小美染色

23秋招，美团笔试1（技术）

美团2024届秋招笔试第一场编程真题

时间：2023.08，牛客补题

美团是少有的整份卷子5题都是算法题的，20*5=100分，其他家一般会有408选择题再配2个编程题。

所以美团的T4、T5有时候会稍微有点卡点，我也没法保证每次都ak，有时候会有只能拿个九十几的情况，不过好在笔试可以做两次（虽然好像AK也不给面）

T1 小美玩排列

有一个排列，一共有n个数，还有特殊的两个数x和y，请你帮助小美判断x和y在排列中是否相邻，是则输出”Yes”，不是则输出”No”

数据范围：

1 ≤ n ≤ 1e5

//AC
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int p[maxn];
int main() {int n;  cin>>n;for(int i = 1; i <= n; i++){int x;  cin>>x;p[x] = i;}int x, y;cin>>x>>y;if(abs(p[x]-p[y])==1){cout<<"Yes\n";}else{cout<<"No\n";}
}

T2 小美走公路

现有一条环形公路，总共有n个站点，a[i]代表第i个站点与第i+1个站点之间的距离，特殊的，a[n]表示第n个站点与第一个站点之间的距离。小美的出发地为x，目的地为y，请你求出x到y的最短距离

1 ≤ n ≤ 1e5

1 ≤ a[i] ≤ 1e9

//AC
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 200010;
LL a[maxn], s[maxn];
int main() {LL n;  cin>>n;LL sum = 0;for(LL i = 1; i <= n; i++){cin>>a[i];sum += a[i];}LL x,y ;  cin>>x>>y;if(x > y)swap(x,y);LL res = 0;for(LL i = x; i < y; i++){res += a[i];}res = min(res, sum-res);cout<<res<<"\n";
}

T3 小美切蛋糕

现有一个n*m的蛋糕矩阵a，a[i][j]代表一小块蛋糕的美味度，现在小美要和一个好朋友分享蛋糕，因此需要把这个蛋糕矩阵切成两半，并且要求分成两半后的两块蛋糕的美味度尽可能相等，即求出分成两半后的两块蛋糕的abs(s1 - s2)的最小值，s1代表第一块蛋糕的美味度，s2代表第二块蛋糕的美味度。要求：必须保证每一小块蛋糕的完整性（即不能斜着切，如果把整个大蛋糕正着放）

1 ≤ n , m≤ 1e3

1 ≤ a[i][j] ≤ 1e5

//AC
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[1010][1010];
// LL b[1010][1010], c[1010][1010];
LL b[1010], c[1010];
int main() {LL n, m;  cin>>n>>m;LL sum = 0;for(LL i = 1; i <= n; i++){for(LL j = 1; j <= m; j++){cin>>a[i][j];b[i] += a[i][j];c[j] += a[i][j];sum += a[i][j];// b[i][j] += a[i][j-1];// c[i][j] += a[i-1][j];}}LL res = 1e9+10, tmp = 0;for(LL i = 0; i <= n; i++){tmp += b[i];res = min(res, abs((sum-tmp)-tmp));}tmp = 0;for(LL j = 0; j <= m; j++){tmp += c[j];res = min(res, abs((sum-tmp)-tmp));}cout<<res<<"\n";
}

T4 小美将字符串平铺成矩阵

现有一个长度为n的且仅包含小写字母的字符串s，小美想把这个字符串s平铺成一个xy的矩阵，要求xy == n，平铺的方法为：将字符串前y个字符按顺序放到第一行，将字符串第y+1到第2*y个字符按顺序放到第二行，以此类推。现规定矩阵的权值为连通量的数目，连通量代表的是从一个点出发，上下左右若存在相同字符则可以继续扩展该连通量（类似于一个岛屿，上下左右若存在相同的字符则可以扩展这个岛屿，或者可以理解为上下左右如果是相同字符则可以合并成一个连通量），求矩阵的最小权值

1 ≤ n ≤ 1e4

//WA-最开始想直接set乱来，最后还是被迫换成dfs写
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int dx[] = {-1, 1, 0 ,0 };
int dy[] = {0, 0, -1, 1};
int main() {int n;  cin>>n;string s;  cin>>s;set<char>se;for(char ch : s){se.insert(ch);}// cout<<s[5]<<"\n";n = s.size();int res = 1e9+10;for(int i = 2; i < n; i++){if(n%i!=0)continue;int ts = 0;for(int j = 0; j < n; j++){set<char>tmp;int z = 0;int x = j/i, y = j%i;// tmp.insert(s[j]);int ok = 0;// z++;for(int k = 0; k < 4; k++){int nx = x+dx[k], ny = y+dy[k];if(nx<0||nx>=n/i || ny<0||ny>=i)continue;if(s[nx*i+ny]==s[j]){// cout<<j<<" "<<nx<<" "<<ny<<" "<<s[nx*i+ny]<<" "<<s[j]<<"\n";ok = 1;}// tmp.insert(s[nx*i+ny]);// z++;if(i==3 && j==2){// cout<<nx<<" "<<ny<<" "<<s[nx*i+ny]<<" "<<s[j]<<"\n";// cout<<x<<" "<<y<<" ";// cout<<nx<<' '<<ny<<" asd\n";}}// if(j>=0){tmp.insert(s[j-1]); z++; }// if(j<n){tmp.insert(s[j+1]); z++; }// if(j-i>=0){tmp.insert(s[j-i]); z++; }// if(j+i<n){tmp.insert(s[j+i]); z++; }// cout<<i<<","<<j<<","<<tmp.size()<<" "<<z<<"\n";// for(char ch : tmp)cout<<ch; cout<<"\n";// if(tmp.size()==z){//     ts++;//     // cout<<i<<", "<<j<<"\n";// }if(ok!=1){ts++;// cout<<i<<", "<<j<<"\n";}}if(ts<res){// cout<<i<<" "<<ts<<"\n";}res = min(res, ts);}// cout<<se.size()<<"\n";cout<<(int)(res+se.size())<<"\n";
}
//AC
//T4-AC
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int dx[] = {-1, 1, 0 ,0 };
int dy[] = {0, 0, -1, 1};
string s;
int n; 
int vis[10010];
// int ts = 0;
int ttt;
void dfs(int x, int y,int d){// cout<<x<<" "<<y<<"\n";for(int i = 0; i < 4; i++){int nx = x+dx[i], ny = y+dy[i];int nj = nx*d+ny;if(nx<0||nx>=n/d || ny<0||ny>=d || vis[nj])continue;if(s[nj] != s[ttt])continue;if(!vis[nj]){vis[nj] = 1;dfs(nx,ny,d);}}
}
int main() {cin>>n;cin>>s;int res = 1e9+10;for(int i = 1; i <= n; i++){if(n%i!=0)continue;int ts = 0;for(int j = 0; j < n; j++)vis[j] = 0;for(int j = 0; j < n; j++){int x = j/i, y = j%i;if(!vis[j]){// cout<<x<<' '<<y<<" asfd\n";ttt = j;dfs(x, y, i);ts++;}}// cout<<i<<" "<<ts<<"\n";res = min(res, ts);}// cout<<se.size()<<"\n";cout<<(int)(res)<<"\n";
}

T5 小美染色

现有一颗包含n个节点的树，节点i的权值为w[i]，d[i]代表节点i相邻的节点集合。一开始所有节点均为白色，若两个相邻节点均为白色且权值的乘积为完全平方数则可以将两个节点都染成红色，问最多可以将多少个节点染成红色

1 ≤ n ≤ 1e5

1 ≤ w[i] ≤ 1e9

// 输出0有10%（数据3/30），暴力+剪枝可以再多骗一部分
// AC 
//1、给出n个点和n-1条边的一棵树
//2、每次操作，相邻且白色且权值的乘积是完全平方数的，改成红色。求最多可以染多少个红。
//3、每个点有两个状态，选和不选，那么就是0/1DP了，又给了个树，也就是树上01DP
// u是根节点 ，i是子节点。不选根时，子节点的最大方案数统计上来就行，dp[u][0] += max(dp[i][0],dp[i][1])
// 选根，需要符合条件（is_sqrt(a[u]*a[i])==1）的子节点同时不被选中，那么dp[u][1]=dp[u][0]-max(dp[i][0],dp[i][1])+dp[i][0]+2，即回退这个点的记录，并更新成同时选中这个子节点和根节点的状态。
// 最后答案就是 max(dp[0][0],dp[0][1])
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1e5 + 10;
LL a[maxn], c[maxn];
vector<LL>G[maxn];
LL dp[maxn][2];
LL res = 0;
int checksqrt(int x) { int d = sqrtl(x)+1e-7; return d*d == x; };
void dfs(LL u, LL f) {for (LL i : G[u]) {if (i == f)continue;dfs(i, u);dp[u][0] += max(dp[i][0], dp[i][1]);// if(checksqrt(a[i]*a[u])){  //需要先把所有子节点的dp状态都更新完了，确保dp[i][0/1]都是最优的，才能更新这里，不然只有7%，别问我怎么知道的//     dp[u][1] = max(dp[u][1], dp[u][0] - max(dp[i][0], dp[i][1]) + dp[i][0] + 2);// }}for (LL i : G[u]) { if (i == f)continue;if(checksqrt(a[i]*a[u])){ dp[u][1] = max(dp[u][1], dp[u][0] - max(dp[i][0], dp[i][1]) + dp[i][0] + 2);}}
}
int main() {LL n;cin >> n;for (LL i = 1; i <= n; i++) {cin >> a[i];}for (LL i = 1; i < n; i++) {LL u, v;  cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs(1, -1);cout << max(dp[1][0], dp[1][1]) << "\n";
}

这篇关于【笔试】美团2023年秋招第1场笔试（后端数开软件方向）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/848482。

相关文章

软件设计师备考——计算机系统

软件设计师备考——计算机系统

学习内容源自「软件设计师」 上午题 #1 计算机系统_哔哩哔哩_bilibili 目录 1.1.1 计算机系统硬件基本组成 1.1.2 中央处理单元 1.CPU 的功能 1)运算器 2)控制器 RISC && CISC 流水线控制 存储器  Cache 中断 输入输出IO控制方式 程序查询方式 中断驱动方式 直接存储器方式（DMA)  ​编辑 总线 ​编辑
阅读更多...
【STM32】SPI通信-软件与硬件读写SPI

【STM32】SPI通信-软件与硬件读写SPI

SPI通信-软件与硬件读写SPI 软件SPI一、SPI通信协议1、SPI通信2、硬件电路3、移位示意图4、SPI时序基本单元(1)开始通信和结束通信(2)模式0---用的最多(3)模式1(4)模式2(5)模式3 5、SPI时序(1)写使能(2)指定地址写(3)指定地址读 二、W25Q64模块介绍１、W25Q64简介２、硬件电路３、W25Q64框图４、Flash操作注意事项软件SPI读写W2
阅读更多...
CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 （最大值之和）给定整数序列 a0,⋯,an−1，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr（其中0≤l≤r<n0≤l≤r<n）表示，对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同，当且仅当下标不同。 例如，当原序列为 [1,2,1,2] 时，要计算子序列 [
阅读更多...
免费也能高质量！2024年免费录屏软件深度对比评测

免费也能高质量！2024年免费录屏软件深度对比评测

我公司因为客户覆盖面广的原因经常会开远程会议，有时候说的内容比较广需要引用多份的数据，我记录起来有一定难度，所以一般都用录屏工具来记录会议内容。这次我们来一起探索有什么免费录屏工具可以提高我们的工作效率吧。 1.福晰录屏大师 链接直达：https://www.foxitsoftware.cn/REC/  录屏软件录屏功能就是本职，这款录屏工具在录屏模式上提供了多种选项，可以选择屏幕录制、窗口
阅读更多...
HomeBank：开源免费的个人财务管理软件

HomeBank：开源免费的个人财务管理软件

在个人财务管理领域，找到一个既免费又开源的解决方案并非易事。HomeBank&nbsp;正是这样一个项目，它不仅提供了强大的功能，还拥有一个活跃的社区，不断推动其发展和完善。 开源免费：HomeBank 是一个完全开源的项目，用户可以自由地使用、修改和分发。用户友好的界面：提供直观的图形用户界面，使得非技术用户也能轻松上手。数据导入支持：支持从 Quicken、Microsoft Money
阅读更多...
嵌入式方向的毕业生，找工作很迷茫

嵌入式方向的毕业生，找工作很迷茫

一个应届硕士生的问题： 虽然我明白想成为技术大牛需要日积月累的磨练，但我总感觉自己学习方法或者哪些方面有问题，时间一天天过去，自己也每天不停学习，但总感觉自己没有想象中那样进步，总感觉找不到一个很清晰的学习规划……眼看 9 月份就要参加秋招了，我想毕业了去大城市磨练几年，涨涨见识，拓开眼界多学点东西。但是感觉自己的实力还是很不够，内心慌得不行，总怕浪费了这人生唯一的校招机会，当然我也明白，毕业
阅读更多...
PDF 软件如何帮助您编辑、转换和保护文件。

PDF 软件如何帮助您编辑、转换和保护文件。

如何找到最好的 PDF 编辑器。 无论您是在为您的企业寻找更高效的 PDF 解决方案，还是尝试组织和编辑主文档，PDF 编辑器都可以在一个地方提供您需要的所有工具。市面上有很多 PDF 编辑器 — 在决定哪个最适合您时，请考虑这些因素。 1. 确定您的 PDF 文档软件需求。 不同的 PDF 文档软件程序可以具有不同的功能，因此在决定哪个是最适合您的 PDF 软件之前，请花点时间评估您的
阅读更多...
理解分类器（linear）为什么可以做语义方向的指导？（解纠缠）

理解分类器（linear）为什么可以做语义方向的指导？（解纠缠）

Attribute Manipulation（属性编辑）、disentanglement（解纠缠）常用的两种做法：线性探针和PCA_disentanglement和alignment-CSDN博客 在解纠缠的过程中，有一种非常简单的方法来引导G向某个方向进行生成，然后我们通过向不同的方向进行行走，那么就会得到这个属性上的图像。那么你利用多个方向进行生成，便得到了各种方向的图像，每个方向对应了很多
阅读更多...
梳理2024年，螺丝钉们爱用的3款剪辑软件

梳理2024年，螺丝钉们爱用的3款剪辑软件

这年头，视频到处都是，就跟天上的星星一样数不清。不管你是公司里的新面孔，还是职场上的老狐狸，学会怎么剪视频，就好比找到了赢的秘诀。不管是给上司汇报工作，展示你的产品，还是自己搞点小视频记录生活，只要是剪辑得漂亮，肯定能一下子吸引大家的目光，让人记得你。咱们今天就来侃侃现在超火的三款视频剪辑工具，尤其是PR剪辑，你肯定听说过，这货在剪辑界可是大名鼎鼎，用它剪视频，既专业又麻利。 NO1. 福昕轻松
阅读更多...
秒变高手：玩转CentOS 7软件更换的方法大全

秒变高手：玩转CentOS 7软件更换的方法大全

在 CentOS 7 中更换软件源可以通过以下步骤完成。更换源可以加快软件包的下载速度，特别是当默认源速度较慢时。以下是详细步骤： 前言 为了帮助您解决在使用CentOS 7安装不了软件速度慢的问题，我们推出了这份由浪浪云赞助的教程——“CentOS7如何更换软件源加快下载速度”。 浪浪云，以他们卓越的弹性计算、云存储和网络服务受到广泛好评，他们的支持和帮助使得我们可以将最前沿的技术知识分
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2