。。。201911032258977:将方案数和距离和分开计算,方案数用容斥算,距离和就枚举树上的每条边,讨论将3个人分成两边的3种情况分别计算方案数,这条边对距离和的贡献为这条边的长度乘以总方案数,最后期望为距离和除以方案数,时空复杂度O(n)。
投递阿里巴巴等公司10个岗位 >
0 点赞 评论 收藏
分享
tiany7:第三题我用二分套二分过了90,排序,去重,然后枚举a,二分b,再套一层二分c,nlognlogn,正解貌似是先二分c再二分b,具体的证明过程就不太会了
第四题是容斥 + 组合数,后50分的输入范围是1e5,n方铁定是过不去的,跟开二维还是一维数组没什么关系。
投递字节跳动等公司10个岗位 >
0 点赞 评论 收藏
分享
关注他的用户也关注了: