小马智行（pony.ai）9.26笔试AC情况

如果有大佬AC了请发布一下思路。。题目是小马智行第二套卷，我投递的是算法工程师，非常感谢

我至今不知道为啥我没笔试😅

题目难度为easy,medium,medium,hard AK了 10点贴个cpp代码

第三题自己怎么测都没问题 一交就是0

第一题直接排序；第二题二分答案，然后枚举a到z利用滑动窗口求解答案是否合法；第三题并查集裸题，第四题50%的数据应该爆搜可过，100%求大佬解答；不得不说小马的题出的确实不错，随便贴一下前三题代码:https://paste.ubuntu.com/p/75tYHvNRJS/

xdm 求个第二题哇

第三题并查集为啥0% 搞不懂啊明明

我真醉了，第一题就是排序啊？第三题就是并查集啊？？我本地测了好几个用例全是对的，提交就是百分之0啊？？？结果你告诉我int换long long ？？？我还以为我算法本身错了，但是我测了好几个用例都是对的 我擦，本来前三题直接秒了，结果一直0%，看半天不知道为什么，心态炸了都没做第四题

50min全a，希望能帮助到大家 我主页有全部代码 1 // 排个序 还用想？ 因为是平方呀 2 // 这题可能有点麻烦？ 首先求最小肯定可以二分 // 主要是看枚举每个字母看一段区间里面有没有 我直接用前缀和差的， 这样方便写 // 其实也可以直接记录一个最尾部的字母位置来判断 3 // 这个题比较明显，其实一开始想的是并查集，但一想不就是个联通分量吗，直接dfs即可 4 /* 这个题我喜欢 首先根据第二个样例就能发现难点在哪里 到底在哪里呢？ 1 1 1 1 前两个[1,1] 可以和后两个[1,1] 组合 也就是说前面如果有一段 合法组合 后面也有一段合法组合 ，那么就能合并 如何合并呢？ 我们先想不合并的： 如果以i为起点的话，后面的选择是不是c(n-i,a[i]) (组合数从i+1到n中选a[i]个 ) 加上合并不合法的就是 ： 从i开头选一个第一段的结束位置 ，假设这个位置是j ， 那么以i开头的方案数 就是(i到j)的方案数 *(后面以j+1,j+2,j+3.....开头的方案数+1) 组合数用的打表 加 乘法逆元，大家没acm基础的可以看这个： https://blog.csdn.net/weixin_43916298/article/details/103919099 当然这题目应该有直接计数dp的写法，我感觉我的思路比较明显就直接写了 */

求个第二题

前三题ac,第四题稍微难一些

1 0.6 1 0 最后一题暴力应该能拿0.5，但想完美解法没时间写了

第一题送分，第三题并查集也算送分吧，第二题和第四题暴力加一起也能过一百分吧。我感觉挺简单的

第一题很简单忘了是啥了，第三题并查集记得union的时候要把每个元素的父节点全部更新到根节点，第四题看完题放弃了，第二题搞了半天没做出来，看看大家的思路

为啥第四题样例过了自己造的样例也过了，但是最后仅仅过了30%，qwq

请教楼主，为什么我第一题也是先排序，然后算相邻两元素的优美值，通过率一直是0

今天的题就是正常leetcode周赛难度吧，easy medium medium hard。然而我还是做不出hard

第二题这种有个通用解法叫做“二分答案验证”，时间复杂度nlogn。

题目和LZ的一样 第一题排序 第二题算每个字母的最大间隔，然后取这些最大间隔的最小值。注意要假设在字符串头尾补上万能字符 第三题并查集 前三题AC了 第四题dp做的，30%

前三题很快解决，第四题开始想用dp，想不出来，想爆搜感觉也不太行，关键是他有分割的，求个思路