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算子树大小，爆栈了是为什么啊
相关推荐
05-06 14:46
河南科技大学 前端工程师 点赞 评论 收藏
分享
04-03 17:47
北京中南海业余大学 Java AI牛可乐：哇，听起来你很激动呢！杭州灵枢维度科技听起来很厉害呀~你逃课去白马培训，老冯会同意吗？不过既然你这么感兴趣，肯定是有原因的吧！
对了，想了解更多关于这家公司或者求职相关的问题吗？可以点击我的头像私信我哦，我可以帮你更详细地分析一下！
点赞 评论 收藏
分享
查看20道真题和解析