2023-09-07 20:44 门头沟学院 C++
关注
蚂蚁24秋招笔试题解分享0907
怎么投个c++岗，选择题一堆java和mysql，寄
这选择题是做过最难的笔试
T1：给个3*3的二维码，可以90,180,270翻转，多次询问在不在里面
这个数据范围很小，就暴力匹配下就行了
T2：有一个长度为n的a数组，里面的数互不相同且都
T3：给一棵大小为n的树，边带权值，给一个m，问有多少方案可以在原树的基础上(u,v,l)的边，是的l<=m且不会改变树上任意点对之间的距离，并求出按照字典序排序的(u,v,l)的中位数的那个方案
设dis(u,v)为原树上u,v两点的距离，且u，v之间原来没有边，如果要加一条边不改变点对的之间的距离，那么取值范围就是[dis(u,v),m]，因为这样他们就始终会走原来已有的边，而不是这条新加的边
n=3000
所以随便找个点建树，比如以1
那么dis(u,v)=sum[u]+sum[v]-2*sum[lca(u,v)]，lca(u,v)就是u和v在有根树中的最近公共祖先,sum[u]表示根到u的边权之和
然后由于n只有3000，这个lca可以在建树的时候暴力平方搞出来，所以复杂度为O(n^2)，把这n^2个lca查询挂在节点上用tarjan也是一样的复杂度
而枚举u,v的复杂度也是O(n^2)
当然搞个倍增或者树链剖分去带个log查询lca，感觉也问题不大
#秋招##笔试##蚂蚁#
这选择题是做过最难的笔试
T1：给个3*3的二维码，可以90,180,270翻转，多次询问在不在里面
这个数据范围很小，就暴力匹配下就行了
T2：有一个长度为n的a数组，里面的数互不相同且都
T3：给一棵大小为n的树，边带权值，给一个m，问有多少方案可以在原树的基础上(u,v,l)的边，是的l<=m且不会改变树上任意点对之间的距离，并求出按照字典序排序的(u,v,l)的中位数的那个方案
设dis(u,v)为原树上u,v两点的距离，且u，v之间原来没有边，如果要加一条边不改变点对的之间的距离，那么取值范围就是[dis(u,v),m]，因为这样他们就始终会走原来已有的边，而不是这条新加的边
n=3000
所以随便找个点建树，比如以1
那么dis(u,v)=sum[u]+sum[v]-2*sum[lca(u,v)]，lca(u,v)就是u和v在有根树中的最近公共祖先,sum[u]表示根到u的边权之和
然后由于n只有3000，这个lca可以在建树的时候暴力平方搞出来，所以复杂度为O(n^2)，把这n^2个lca查询挂在节点上用tarjan也是一样的复杂度
而枚举u,v的复杂度也是O(n^2)
当然搞个倍增或者树链剖分去带个log查询lca，感觉也问题不大
#秋招##笔试##蚂蚁#
全部评论
binarycopycode 楼主
楼主 门头沟学院 C++
if(p[i]<p[i-1]) ans++ ，怎么把我写的T2吞了一段
但是还有酒精
门头沟学院 无线通信工程师
我是c++但大佬内推成java，点开一看选择一堆c++,我以为题是一样的，无语了。
相关推荐
美团二面1680人在聊 点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享