蚂蚁24秋招笔试题解分享0907

怎么投个c++岗,选择题一堆java和mysql,寄
这选择题是做过最难的笔试

T1:给个3*3的二维码,可以90,180,270翻转,多次询问在不在里面
这个数据范围很小,就暴力匹配下就行了

T2:有一个长度为n的a数组,里面的数互不相同且都长度为n的严格递增子序列意思就是必须是1-n,那么按照1-n的顺序去找,如果从i到i+1他要掉头,那么就说明需要多复制个新数组,那么就p[a[i]]=i 然后for (i=2;i<=n;i++) if(p[i]
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,感觉也问题不大
#秋招##笔试##蚂蚁#
全部评论
if(p[i]<p[i-1]) ans++ ,怎么把我写的T2吞了一段
点赞 回复 分享
发布于 2023-09-07 20:47 广东
我是c++但大佬内推成java,点开一看选择一堆c++,我以为题是一样的,无语了。
点赞 回复 分享
发布于 2023-09-11 10:36 北京

相关推荐

不愿透露姓名的神秘牛友
10-05 10:13
已编辑
HHHHaos:让这些老登来现在秋招一下,简历都过不去
点赞 评论 收藏
分享
5 收藏 评论
分享
牛客网
牛客企业服务