solution

牛牛xor牛妹

http://www.nowcoder.com/questionTerminal/8baf6f1291334c82a854c719c10272e9

朴素的dp状态为f[i][j][k],表示第1到i个数,牛牛集合的xor为j,牛妹集合的xor为k的方案数。发现很难优化。

以下设牛牛集合的xor为A,牛妹集合的xor为B。
换一种思路,因为题目要求A<B,那么A和B肯定存在一个二进制位使得比这高的位上A和B相等且这一位A为0,B为1。
我们枚举这一位,现在我们的任务变成了选一些数分进两个集合,使A和B比这位高的相等,且这一位A为0,B为1.

然后我们惊奇的发现当前状态只需要保存A和B哪些位相等和这一位上A,B的状态即可。

复杂度4* n^2*log

全部评论

相关推荐

点赞 评论 收藏
分享
焦虑中,不知道怎么办了。。。
西北上单:应该放俩项目合理一些 我是一个业务开发项目 一个AI项目和你这个写的亮点差不多
你的简历改到第几版了
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务