美团算法方向笔试

技不如人甘拜下风
5道题
1.签到题
两辆火车车尾对齐出发，长的长度为d1，短的长度为d2，长的慢，速度为v1，短的快，速度为v2，求什么时候车头对齐
就是（d1 - d2) / (v2 -v1）
只需要调整输出的格式，不过只记住了cout.setprecision()，知道还需要一个东西（fixed）但忘了是啥😅

死活想不起来后灵机一动，用牛客自动补全，在cout后面所有跟的东西里找到了fixed，成功ac；

2.签到题
输入一些字符串，大写字母开头则数字加一
很简单，就如题意，没坑

3.二分查找
种树，给定n个工人的位置（整数）和一个目标整数k，给定一个数x后，每个工人会从自己的位置向右依次种x棵树，现求最小的的数字x，使得所有工人种了k棵树以上
二分查找，最多k，最少k/n，主要就是注意工人位置并不是有序的，而且有可能已经被种过，稍微调整一下即可

4.red子序列
给定一个字符串s，当一个字符串从左往右依次含有'r ' 'e' 'd'说明它有red子序列，比如rred有两个red子序列
求这个字符串s的所有连续子串含有的red子序列的数量之和，比如rred，子串rred含有两个red序列，子串red含有一个red序列，它的总和为3。

一眼DP，心里暗喜，感觉很简单的样子，从头到尾 DP了一遍，什么re += r, red += re，再全加一遍，一提交5%，事实证明我是小丑😅，因为只算出来从头到尾的red子序列，仔细一看是所有连续子串；

后面DP了一个小时，没想出来。

5.怎么感觉又是线段树，
给一个数组，给一个整数q，意味着q轮游戏，每轮游戏给区间[l,r]，A挑出这个区间里最大的数，B从[L,R]区间里挑数，[L,R]范围大于等于[l,r]，但注意B不能和A挑一样的数，B的数大则win，相等为draw，小则lose，求能确定本局输赢的最小的[L,R]区间的长度和本局游戏结果

一看这种区间题就不怎么会，看了一眼别的帖子似乎用单调栈。

想了想还有平局之类，感觉就算暴力做起来也很难麻烦，而且考虑到感觉第四道DP似乎差一点能做出来，后面就放弃这道题专攻第四道了，结果没专攻出来😅

前面三道轻松a完后，想着这次这么着不得再干一道？结果是我太菜了，这个DP一个多小时都没想明白。事实证明水平就到这了，上次也是就会三道，虽然没a3道，这次好歹是正常a出来了，感谢美团没埋坑。

不过其实志愿直接就挂了，笔不笔的图一乐😅

#美团求职进展汇总#