首页 > Beautiful Subarrays
开通博客写题解
头像 lifehappy
发表于 2020-12-22 17:48:48
Beautiful Subarrays 有 所以我们可以先求一遍异或前缀和，然后再通过枚举右端点，去查找有多少个左端点符合要求。 假设我们当前枚举到这个位置，前个数的异或前缀和是，我们要查找异或值大于等于的, 这里我们可以去找一个，满足，这个时候大于等于的数就是满足要求的数了， 这个操作我们可以通过 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2021-01-07 13:52:08
传送门 首先确定肯定使用字典树 然后因为异或的性质有 那么只需要把所有的前缀插入字典树 然后枚举端点去字典树上找有多少个即可 也就是对每一个都去字典树上找有多少个前缀满足条件 那么最后答案需要除以,因为每个一可以作为字典树上的前缀,也可以作为 值得一提的是需要把0插入进去 因为允许存在 那么我们也 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2021-01-07 20:34:04
做法：01Trie 思路 我们可以先求异或前缀和然后套上字典树在执行find时如果 k 的这一位是 1 ，那么必须往 1 那一边走。如果 k 的这一位是 0 ，那么分情况讨论如果往 1 走，那么整个子树内所有的叶子结点都要计算。如果往 0 走，那么继续循环下去最后不要忘记等于k的个数 代码 #inc 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”