美团第一次笔试

1、模拟即可，注意模一下

#include <bits/stdc++.h>
typedef long long ll;
const int MAXN = 1e3 + 10;
char s[MAXN], t[MAXN], x[MAXN];
int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%s", s + 1); int n = strlen(s + 1);
    int p = 0, r = 0;
    for (int i = 1; i <= n; ++i) {
      if (s[i] >= '0' && s[i] <= '9') {
        p = p * 10 + s[i] - '0';
      } else {
        if (r > 0) p %= r;
        int xx = 0;
        for (int j = p + 1; j <= r; ++j) {
          x[++xx] = t[j];
        }
        for (int j = 1; j <= p; ++j) {
          x[++xx] = t[j];
        }
        for (int j = 1; j <= r; ++j) {
          t[j] = x[j];
        }
        p = 0;
        if (s[i] == 'R') {
          std::reverse(t + 1, t + 1 + r);
        } else {
          t[++r] = s[i];
        }
      }
    }
    t[r + 1] = 0;
    printf("%s\n", t + 1);
  }
  return 0;
}

2、题面写得像史，一开始题读假了，好在代码改一下就能过。按xy分别排序后存起来二分即可

#include <bits/stdc++.h>
typedef long long ll;
const int MAXN = 1e5 + 10;
struct Node {
  int x, y, idx;
} a[MAXN];
int alls[MAXN];
int get(int x) {
  return x > 0;
}
int main() {
  int n; scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a[i].x, &a[i].y);
    a[i].idx = i;
  }


  std::unordered_map<int, std::vector<int>> xs, ys;


  std::sort(a + 1, a + 1 + n, [](Node a, Node b) {
    if (a.x == b.x) return a.y < b.y;
    else return a.x < b.x;
  });
  for (int i = 1; i <= n; ++i) {
    xs[a[i].x].push_back(a[i].y);
  }


  std::sort(a + 1, a + 1 + n, [](Node a, Node b) {
    if (a.y == b.y) return a.x < b.x;
    else return a.y < b.y;
  });
  for (int i = 1; i <= n; ++i) {
    ys[a[i].y].push_back(a[i].x);
  }


  for (int i = 1; i <= n; ++i) {
    int x = a[i].x, y = a[i].y;
    int posx = std::lower_bound(xs[x].begin(), xs[x].end(), y) - xs[x].begin();
    int posy = std::lower_bound(ys[y].begin(), ys[y].end(), x) - ys[y].begin();
    int ans = 0;


    ans += get(posx - 1);
    ans += get((int)xs[x].size() - 2 - posx);
    ans += get(posy - 1);
    ans += get((int)ys[y].size() - 2 - posy);
    
    alls[a[i].idx] = ans;
  }


  for (int i = 1; i <= n; ++i) {
    printf("%d\n", alls[i]);
  }
  return 0;
}

3、糊了一个裸LCA+暴力上去0分，没绷住。时间不太够了，讨论下来应该是每个点向下向上维护最近的BUG三个字母，然后LCA即可，不太好写。

*更：似乎有用树链剖分做的，没板子谁写得出来啊

最难绷的是选择题有一道做的时候感觉不太对，但是还是直接交了，结果糊LCA的时候发条消息过来说改题了，做题系统必须提交才能退出去改。

唉，AI面得像史，笔试还得二战