米哈游2024/3/10线上笔试编程题

T1 没什么说的，模拟史莱姆跳动即可，为了写着方便，可以用两个桶记录有编号为i（向左/向右跳的史莱姆是否存在），但是笨蛋作者题面读错了三遍，导致T1花了三十多分钟才出来
T2 拿三个map模拟题目过程即可 但是由于码力退步 花了20多分钟才写出来
T3 当时写T3的时候只剩十分钟了 还好当时思路比较清晰 大约五六分钟就写出来了 最后还是写完了 考虑用一个栈去记录树的DFS过程 不难发现 当某个数字出栈时 栈中的剩余节点都是该数字的父亲或者祖先节点 因此当某个节点出栈时 去考虑栈中有哪些节点他们的权值会被该节点的权值整除 并时它们的答案+1 显然 当该树退化成一个链表时 该过程的时间复杂度为O(n^2)
考虑到可以用一个桶去维护栈中的哪些数字出现过 然后当i出栈时 考虑枚举i,2i,3i...哪些数字在栈中出现，并更新出现过的数字的答案，该过程的枚举次数为(n/1+n/2+..n/n)=n*(1/1+1/2+..1/n)，由于当n较大时，(1/1+1/2+..1/n)接近于ln(n)，因而该算法的时间复杂度为O(n*log(n)),这题就出来了