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

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

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

T2：有一个长度为n的a数组，里面的数互不相同且都<n，其实就是一个1-n的排列，现在问把这个a数组复制多少次，也就是变成k*n的数组，可以得到一个长度为n严格递增的子序列
长度为n的严格递增子序列意思就是必须是1-n，那么按照1-n的顺序去找，如果从i到i+1他要掉头，那么就说明需要多复制个新数组，那么就p[a[i]]=i 然后for (i=2;i<=n;i++) if(p[i]<p[i-1]) ans++;就行了；

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，感觉也问题不大
#秋招##笔试##蚂蚁#