美团26暑期实习笔试

📍公司：美团26暑期实习

👜岗位：后端开发

📖问题：

一共三道编程题，两道水题，一道高级数据结构题。

字符串模拟

• 题目简介：初始一个空字符串。给一组操作，如果操作是数字就记录下来更新变量g（g初始为0）。否则先将字符串循环右移g位再判断操作，如果该操作是'R'，翻转字符串否则将该操作对应的字符加到字符串后面。
• 代码

#include <bits/stdc++.h>

using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        string s, res = "";
        int g = 0;
        cin >> s;
        for (char op : s) {
            if (isdigit(op)) {
                g = g * 10 + (op - '0');
                continue;
            }
            if (res.size()) g %= res.size();
            res = res.substr(g) + res.substr(0, g);
            if (op == 'R') reverse(res.begin(), res.end());
            else res += op;
        }
        cout << res << endl;
    }
    return 0;
}

炮能打到的敌人数

• 题目简介：在一个无限大的2D棋盘上有n个炮。每个炮有个坐标（x,y）。该炮的正上方如果有超过两个棋子，则他可以打该方向。正下方，正左边，正右边同理。问这n个炮每个能打到几个方向。
• 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

struct node {
    int x, y, id;
}g[N];

int cnt[N];

bool cmp_x(node a, node b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

bool cmp_y(node a, node b) {
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> g[i].x >> g[i].y;
        g[i].id = i;
    }

    sort(g + 1, g + n + 1, cmp_x);
    for (int i = 1; i <= n; ++i) {
        int L = i - 2, R = i + 2, idx = g[i].id;
        cnt[idx] += (L >= 1 && g[L].x == g[i].x);
        cnt[idx] += (R <= n && g[R].x == g[i].x);
    }

    sort(g + 1, g + n + 1, cmp_y);
    for (int i = 1; i <= n; ++i) {
        int L = i - 2, R = i + 2, idx = g[i].id;
        cnt[idx] += (L >= 1 && g[L].y == g[i].y);
        cnt[idx] += (R <= n && g[R].y == g[i].y);
    }

    for (int i = 1; i <= n; ++i) {
        cout << cnt[i] << endl;
    }
    
    return 0;
}

找BUG

• 题目简介：有一颗树，树上每个节点对应一个字母，问给定的u->v的简单路径上有没有"BUG"这个子序列。有输出"NO"，没有输出"YES"。
• 代码（树链剖分，暴力O(n^2)是0分）

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int h[N], e[N], ne[N], idx;
int n, q, siz[N], dep[N], fa[N], son[N], top[N], id[N], rid[N], cnt;
vector<int> nw[N][3];
char s[N];
string bug = "BUG";
unordered_map<char, int> ump = {
    {'B', 0}, {'U', 1}, {'G', 2}
};

void add(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void init_dfs(int u, int f) {
    siz[u] = 1;
    fa[u] = f;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == f) continue;
        dep[v] = dep[u] + 1; 
        init_dfs(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs(int u, int t) {
    id[u] = ++cnt; rid[cnt] = u; top[u] = t; nw[t][ump[s[u]]].push_back(cnt);
    if (!son[u]) return;
    dfs(son[u], t);
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa[u] || v == son[u]) continue;
        dfs(v, v);
    }
}

int find(int x, vector<int> &a) {
    int l = 0, r = a.size() - 1, res = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (a[mid] <= x) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    return res;
}

string query(int u, int v) {
    int ch = 0, ct = 2; // head and tail (head u->v tail v->u)
    while (top[u] != top[v]) {
        if (dep[top[u]] >= dep[top[v]]) { // find u->v
            int tu = top[u];
            int f = find(id[u], nw[tu][ch]);
            if (~f) u = rid[nw[tu][ch++][f]]; 
            else u = fa[top[u]];
        }
        else { // find v->u
            int tv = top[v];
            int f = find(id[v], nw[tv][ct]);
            if (~f) v = rid[nw[tv][ct--][f]]; 
            else v = fa[top[v]];
        }
        if (ch > ct) return "NO";
    }
    
    while (u != v) {
        if (dep[u] >= dep[v]) {
            int tu = top[u];
            int f = find(id[u], nw[tu][ch]);
            if (~f) {
                u = rid[nw[tu][ch++][f]];
                if (u < v) break;
            }
            else break;
        }
        else {
            int tv = top[v];
            int f = find(id[v], nw[tv][ct]);
            if (~f) {
                v = rid[nw[tv][ct--][f]];
                if (v < u) break;
            }
            else break;
        }
        if (ch > ct) return "NO";
    }
    if (u == v && ch == ct && s[u] == bug[ch]) return "NO";
    return "YES";
}

int main() {
    cin >> n >> q;
    memset(h, -1, sizeof h);
    cin >> s + 1;
    for (int i = 1; i <= n; i++) {
       int f;
       cin >> f;
       add(f, i); add(i, f); 
    }

    init_dfs(1, 0);
    dfs(1, 1);

    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << query(u, v) << endl;
    }
    return 0;
}
/*
14 4
UBGBUBGGBUGBGU
0 1 1 2 2 4 4 5 3 9 9 10 10 10
6 3
11 14
11 4
11 7
*/

以上代码均为参考代码。最后一题我赛时没掏上，后面口胡补的。