美团2025年春招第一场笔试【技术方向】个人题解
题目：10 道单选 + 3 道算法题
结果：只做出前两道题，第三题暴力0分
题图在网上找的
第一题：字符串解密
按规则模拟即可，为了防止可能出现的问题我取了下模，按理来说 p 每次乘法都可能溢出的，但是貌似没有设置这种坑
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while(T--){
string s;
cin >> s;
string t;
int p = 0;
for(auto c : s){
if(isalpha(c)){
int len = t.size();
if(len){
p %= len;
t = t.substr(p, len - p) + t.substr(0, p);
}
if(c == 'R') reverse(t.begin(), t.end());
else t += c;
p = 0;
}else{
p = p * 10 + c - '0';
}
}
cout << t << endl;
}
return 0;
}
第二题：小美架炮
我的做法是排序一下，把相同横坐标或者纵坐标的点一块计算。
以相同横坐标为例，假设有5个点 a, b, c, d, e 横坐标相同，纵坐标递增，则 a,b,d,e 都能打到 1 个炮，c 能打到 2 个炮
纵坐标同理这样统计答案即可
复杂度还是排序的 O(nlogn) 吧
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
struct node{
int x, y, id;
};
int ans[N];
vector<node>a;
int main() {
int n;
cin >> n;
for(int x, y, i = 1;i <= n;i++){
cin >> x >> y;
a.push_back({x, y, i}); // 记录答案 id
}
// 按横坐标排序，相同横坐标一块计算往纵坐标方向打的数量
sort(a.begin(), a.end(), [](const node& u, const node& v)->bool{
return u.x == v.x ? u.y < v.y : u.x < v.x;
});
for(int i = 0;i < n;i++){
int j = i;
while(j < n && a[i].x == a[j].x) j++;
j--;
// [i, j] 区间内横坐标相等
for(int k = i;k <= j;k++){
if(k - 2 >= i) ans[a[k].id]++; // 往下打
if(k + 2 <= j) ans[a[k].id]++; // 往上打
}
i = j;
}
// 同理的，按纵坐标排序
sort(a.begin(), a.end(), [](const node& u, const node& v)->bool{
return u.y == v.y ? u.x < v.x : u.y < v.y;
});
for(int i = 0;i < n;i++){
int j = i;
while(j < n && a[i].y == a[j].y) j++;
j--;
for(int k = i;k <= j;k++){
if(k - 2 >= i) ans[a[k].id]++;
if(k + 2 <= j) ans[a[k].id]++;
}
i = j;
}
for(int i = 1;i <= n;i++)
cout << ans[i] << endl;
return 0;
}
第三题：有根树
当场感觉是 LCA 最近公共祖先，但是忘记了板子，就想着暴力能得多少是多少吧，结果通过 0%
看了其他大佬的简略题解，自己写了下代码，可以通过样例，不知道能过吗。。。如果题目开放了测一下看看
前置知识：倍增，最近公共祖先
时间复杂度 O(nlogn)
假设 u，v 的最近公共祖先是 x，u 到 x 的 B U G 覆盖状态分别映射为 1 2 4（代码中的 bug 数组）
v 到 x 的 B U G 覆盖状态分别映射为 4 2 1 (代码中的 gub 数组）
比较难处理的是 B U G 的顺序问题，这里我也不确定对不对，有大佬的话可以指正，只做过 LCA 板子题，倍增的时候带状态的也是第一次做。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 6;
vector<int> a[N];
int n, m, d[N], fa[N][20], lg2[N], bug[N][20], gub[N][20];
char s[N];
int ok;
// y 比 x 离根近
int update(int x, int y){
int ans = x;
if((y & 1))
ans |= 1;
// 左边是先有 B 才填 U，右边是先有 G 才填 U
if((y & 2) && (ans & 1))
ans |= 2;
if((y & 4) && (ans & 2))
ans |= 4;
return ans;
}
void dfs(int now, int f) {
d[now] = d[f] + 1;
fa[now][0] = f;
bug[now][0] |= (s[now] == 'B'); // B -> 1
bug[now][0] |= ((s[now] == 'U') << 1); // U -> 2
bug[now][0] |= ((s[now] == 'G') << 2); // G -> 4
gub[now][0] |= (s[now] == 'G');
gub[now][0] |= ((s[now] == 'U') << 1);
gub[now][0] |= ((s[now] == 'B') << 2);
int range = lg2[d[now]];
for(int i = 1;i <= range;i++) {
fa[now][i] = fa[fa[now][i - 1]][i - 1];
bug[now][i] = update(bug[now][i - 1], bug[fa[now][i - 1]][i - 1]);
gub[now][i] = update(gub[now][i - 1], gub[fa[now][i - 1]][i - 1]);
}
for(auto nxt : a[now])
dfs(nxt, now);
}
int LCA(int x, int y) {
int lok = 0, rok = 0;
while (d[x] > d[y]) {
lok = update(lok, bug[x][lg2[d[x] - d[y]]]);
x = fa[x][lg2[d[x] - d[y]]];
}
while (d[y] > d[x]) {
rok = update(rok, gub[y][lg2[d[y] - d[x]]]);
y = fa[y][lg2[d[y] - d[x]]];
}
lok = update(lok, bug[x][0]);
rok = update(rok, gub[y][0]);
if (x == y){
// 左边 BUG 或者 右边 GUB，或者 左边 B 和 右边 UG ...
if(lok == 7 || rok == 7 || (lok == 1 && rok == 3) || (lok == 3 && rok == 1) || (lok == 3 && rok == 3))
return 1;
else return 0;
}
for (int i = lg2[d[x]]; i >= 0; i--) {
if (fa[x][i] != fa[y][i]){
lok = update(lok, bug[x][i]);
rok = update(rok, gub[x][i]);
x = fa[x][i], y = fa[y][i];
}
}
lok = update(lok, bug[x][0]);
rok = update(rok, gub[x][0]);
lok = update(lok, bug[fa[x][0]][0]);
if(lok == 7 || rok == 7 || (lok == 1 && rok == 3) || (lok == 3 && rok == 1) || (lok == 3 && rok == 3))
return 1;
else return 0;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; i++)
lg2[i] = lg2[i - 1] + ((1 << (lg2[i - 1] + 1)) == i);
for (int i = 1, fa; i <= n; i++) {
scanf("%d", &fa);
a[fa].push_back(i);
}
scanf("%s", s + 1);
dfs(1, 0);
while (m--) {
int x, y;
scanf("%d%d", &x, &y);
ok = LCA(x, y);
if(ok) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}
/*
5 3
0 1 1 2 2
AUGBC
4 3
4 5
4 1
9 3
0 1 1 2 2 3 3 4 8
CDBUGGCGB
7 8
8 6
9 6
*/
投递美团等公司10个岗位 >
