2023-08-27 22:10 中山大学 C++
关注
8.27米哈游笔试 300/300
T1
枚举一下先打哪个怪，计算一下答案即可。
T2
考虑博弈dp
f[i]表示当前位置为i是否必胜。
f[i]=1当且仅当存在j满足j
暴力实现这个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
暴力实现这个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)
全部评论
🍁Myosin
华为_华为云_通软开发
第三题，对于每个为h的根节点，根节点所有m和y的子节点，都需要dfs求每个子节点的子树大小吗？
喝咖啡的孙兴敏
西安电子科技大学 Java
第二题不用dp，遍历一遍即可，记录一个最小值，出现更小的值就loseCount+1,winCount = n-loseCount
破防了的大老虎很讲道理
中国科学院大学 C++
第三题dfs算子树大小，爆栈了是为什么啊
当然是young啦
门头沟学院 Java
第二题必胜有什么例子吗
相关推荐
点赞 评论 收藏
分享
投递米哈游等公司10个岗位