[原创]SPOJ SUBXOR - SubXor [Trie]【思维】
[原创]SPOJ SUBXOR - SubXor [Trie]【思维】
2017-03-25 12:38:34 Tabris_ 阅读数:422
博客爬取于2020-06-14 22:41:08
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/65935956
题目链接:http://www.spoj.com/problems/SUBXOR/en/
————————————————————————————————————————————
SUBXOR - SubXor
no tags
A straightforward question. Given an array of positive integers you have to print the number of subarrays whose XOR is less than K.
Subarrays are defined as a sequence of continuous elements Ai, Ai+1, …, Aj . XOR of a subarray is defined as Ai^Ai+1^ … ^Aj.
Symbol ^ is Exclusive Or. You can read more about it here:
http://en.wikipedia.org/wiki/Exclusive_or
Input Format:
First line contains T, the number of test cases. Each of the test case consists of N and K in one line, followed by N space separated integers in next line.
Output Format:
For each test case, print the required answer.
Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5
1 ≤ K ≤ 10^6
Sum of N over all testcases will not exceed 10^5.
Sample Input:
1
5 2
4 1 3 2 7
Sample Output:
3
Explanation:
Only subarrays satisfying the conditions are [1],[1,3,2] and [3,2].
————————————————————————————————————————————
题目大意:
给你一个序列,问你有多少个区间的所有元素异或和小于k
解题思路:
首先我们很容易想到,
对于一个区间异或和 可以先预处理出前缀异或和pre[],这样的话区间的异或和成就变成了pre[r]^pre[l-1]
现在问题就变成了序列中选取两个元素异或结果小于K的方案数有多少了
如果是等于k的话 相信大家都会做了,但是要小于k怎么处理呢 ,
其实一样的 ,只是在计算等于K的过程中进行统计,对于k当前二进制位下为1的时候我们就记录下和当前位异或为0的组合有多少 ,然后遍历下去重复此过程就好了,
注意要把pre[0]先插入字典树,这样才能统计区间的结果
附本题代码
————————————————————————————————————————————
1 | # include <bits/stdc++.h> |