美团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
*/