2020.8.1 猿辅导笔试算法题

第一题离散化+差分,比较正常
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int maxn = 200200;
int n;
int x[maxn], y[maxn];
int h[maxn << 1], hcnt;
int f[maxn << 1];

int id(int x) {
  return lower_bound(h, h + hcnt, x) - h + 1;
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%d", &n)) {
    hcnt = 0;
    memset(f, 0, sizeof f);
    for (int i = 1; i <= n; i++) {
      scanf("%d %d", &x[i], &y[i]);
      h[hcnt++] = x[i];
      h[hcnt++] = y[i];
    }
    sort(h, h + hcnt);
    hcnt = unique(h, h + hcnt) - h;
    for (int i = 1; i <= n; i++) {
      f[id(x[i])]++;
      f[id(y[i])]--;
    }
    int ret = 0;
    for (int i = 1; i <= hcnt; i++) {
      f[i] += f[i - 1];
      ret = max(ret, f[i]);
    }
    printf("%d\n", ret);
  }
  return 0;
}


第二题树DP,题干挺S·B的
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using pii = pair<LL, LL>;

const LL mod = 1E9 + 3;
const int maxn = 100100;
int n;
vector<int> G[maxn];
int root;
LL w[maxn];
double g[maxn];
LL f[maxn];

void dfs(int u, int p)  {
  f[u] = w[u];
  g[u] = double(w[u]);
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (v == p) continue;
    dfs(v, u);
    if (g[u] < g[u] + g[v]) {
      f[u] = (f[u] + f[v]) % mod;
      g[u] = g[u] + g[v];
    }
  }
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%d", &n)) {
    for (int i = 1; i <= n; i++) {
      G[i].clear();
    }
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    int u;
    for (int i = 1; i <= n; i++) {
      scanf("%lld %d", &w[i], &u);
      if (u == 0) {
        root = i;
        continue;
      }
      u--;
      G[i].emplace_back(u);
      G[u].emplace_back(i);
    }
    dfs(root, -1);
    LL ret = f[1];
    double tmp = g[1];
    for (int i = 2; i <= n; i++) {
      if (tmp < g[i]) {
        tmp = g[i];
        ret = f[i];
      }
    }
    printf("%lld\n", ret);
  }
  return 0;
}

第三题整挺好,让你写一个描述不清的parser,阴间题。
#猿辅导21秋招##笔试题目#
全部评论
卑微小阳来挖坟,感觉第三个题要是让我读懂题我还是写的了呢23333333
点赞 回复 分享
发布于 2020-08-10 22:19
可以问一下具体的笔试时间是几点到几点嘛?
点赞 回复 分享
发布于 2020-08-10 19:41
最后一题手写一个简易的前端框架 也不知道咋想的 这咋做得完
点赞 回复 分享
发布于 2020-08-01 23:55
老icpcer了
点赞 回复 分享
发布于 2020-08-01 22:37

相关推荐

05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
点赞 评论 收藏
分享
评论
11
5
分享

创作者周榜

更多
牛客网
牛客企业服务