2023-08-27 22:10 中山大学 C++
关注
8.27米哈游笔试 300/300
T1
枚举一下先打哪个怪，计算一下答案即可。
T2
考虑博弈dp
f[i]表示当前位置为i是否必胜。
f[i]=1当且仅当存在j满足j<i,a[j]<a[i]并且f[j]=0
（前面有一个可以转移到的必败态）
暴力实现这个dp是O(n^2)的
显然可以通过维护i之前的a[j]最小的必败态优化为O(1)转移
总复杂度O(n)
T3
考虑去计算每一个“mhy”对答案的贡献
考虑枚举h字符所在的节点
则该字符会和它的一个字符为m的相邻节点a和另外一个字符为y的相邻节点b构成一个mhy
考虑有多少条链会包含这个mhy
显然是sz[a]*sz[b] （sz[x]表示子树x的大小）
因此这个节点的贡献就是
∑ ∑sz[a]*sz[b] = ∑sz[a] * ∑sz[b]
因此只需要计算出每个h节点的所有相邻的m节点的sz之和 和 所有相邻的y节点的sz之和
然后乘起来加到答案中就可了
总复杂度O(n)
枚举一下先打哪个怪，计算一下答案即可。
T2
考虑博弈dp
f[i]表示当前位置为i是否必胜。
f[i]=1当且仅当存在j满足j<i,a[j]<a[i]并且f[j]=0
（前面有一个可以转移到的必败态）
暴力实现这个dp是O(n^2)的
显然可以通过维护i之前的a[j]最小的必败态优化为O(1)转移
总复杂度O(n)
T3
考虑去计算每一个“mhy”对答案的贡献
考虑枚举h字符所在的节点
则该字符会和它的一个字符为m的相邻节点a和另外一个字符为y的相邻节点b构成一个mhy
考虑有多少条链会包含这个mhy
显然是sz[a]*sz[b] （sz[x]表示子树x的大小）
因此这个节点的贡献就是
∑ ∑sz[a]*sz[b] = ∑sz[a] * ∑sz[b]
因此只需要计算出每个h节点的所有相邻的m节点的sz之和 和 所有相邻的y节点的sz之和
然后乘起来加到答案中就可了
总复杂度O(n)
全部评论
喝咖啡的孙兴敏
西安电子科技大学 Java
第二题不用dp，遍历一遍即可，记录一个最小值，出现更小的值就loseCount+1,winCount = n-loseCount
🍁Myosin
华为_华为云_通软开发
第三题，对于每个为h的根节点，根节点所有m和y的子节点，都需要dfs求每个子节点的子树大小吗？
当然是young啦
门头沟学院 Java
第二题必胜有什么例子吗
破防了的大老虎很讲道理
中国科学院大学 C++
第三题dfs算子树大小，爆栈了是为什么啊
相关推荐
查看32道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享
书海为家：我来给一点点小建议，因为毕竟还在学校不像工作几年的老鸟有丰富的项目经验，面试官在面试在校生的时候更关注咱们同学的做事逻辑和思路，所以最好在简历中描述下自己做过项目的完整过程，比如需求怎么来的，你对需求的解读，你想到的解决办法，遇到困难如何找人求助，最终项目做成了什么程度，你从中收获了哪些技能，你有什么感悟。 点赞 评论 收藏
分享
03-07 15:01
重庆邮电大学 前端工程师 点赞 评论 收藏
分享