美团4.16笔试

第三题 类似于直方图  在区间内的对应直方图自增 最后找出直方图高度大于2的 第四题双向bfs  第五题bfs  第四题我过了50 因为不会双向bfs  第五题过了82 超时了

第三题我把涵盖在区间的数都加到字典中了，最后求了count >= 2的个数

校友

为啥我是4道编程题加3道选择题

可以用本地IDE吗？

第四题，动态规划，在a>b时，dp(a,b)=1+min(dp(a,b-1),dp(a/2,b))。小的数乘以二这个操作可以不要，因为可以用大的数除以二，因为除以二有向下取整，采用大数除以二，操作次数比小数乘以二要小，或者相等，比方，6和13。动态规划的边界，dp(1,n)=x，x为n不断除以二直到等于1的次数。 第五题，由于题目可以用数组来保存节点的父亲，每次找节点编号在后面的节点的父亲，直到其中节点编号小的是大的父节点，就找到了公共祖先。

请问各位收到面试邀请了吗，我过了3.8道现在没收到消息😭

第5题并查集 vector<int> meituan5() {   int n, m;   cin >> n;   vector<int> tree(n + 1, 0);   vector<int> weights(n + 1, 0);   for (int i = 2; i <= n; ++i) {     cin >> tree[i];   }   for (int i = 1; i <= n; ++i) {     cin >> weights[i];   }   cin >> m;   vector<vector<int>> requests(m, vector<int>(2));   for (int i = 0; i < m; ++i)     cin >> requests[i][0];   for (int i = 0; i < m; ++i)     cin >> requests[i][1];   vector<int> res(m);   int beg, end, currNode, val;   for (int i = 0; i < m; ++i) {     beg = requests[i][0];     end = requests[i][1];     currNode = beg;     val = 0;     while (currNode != 1 && currNode != end) {       val ^= weights[currNode];       currNode = tree[currNode];     }     if (currNode == 1) {       currNode = end;       while (currNode != 1) {         val ^= weights[currNode];         currNode = tree[currNode];       }       val ^= weights[1];     } else {       val ^= weights[end];     }     res[i] = val;   }   return res; }

有大佬康康dp酱紫对吗

想问一下第一题不久求空格吗？正则匹配一下为啥90%。。。离谱，现在也没想明白。优惠券那个直接查一下就能过了，我一开判定条件写错了也是36

第四题用dp很简单，代码量很少，时间复杂度，空间复杂度都不高

100,100,100,86,18

第三题 LR双排序O(nlogn) 第四题 bfs分别计算a,b到[1，4000]内每个数字需要的次数，然后依次遍历这4000个数，求最小距离之和 第五题 记录从根结点到每个结点的异或和，然后找a,b的最近公共根结点为c，a^b^c即为最终答案，测试样例比较简单，暴力能过

第三题双指针

三题差分数组可以秒

老哥，你第三题36是忘了把L和R排序了吧，我当时忘了排序就是36

第三题哨兵变量，第4题dfs+兼职，第5题有点像昨晚的阿里题，遍历并记录下路径，xors[i] ^ xors[j] ^ val[i,j最近的共同祖先]