本文主要是介绍Codeforces Round 943(Div.3) F.Equal XOR Segments，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
C o d e f o r c e s R o u n d 943 ( D i v . 3 ) F . E q u a l X O R S e g m e n t s \Huge{Codeforces~Round~943~(Div.3)F.Equal~XOR~Segments} Codeforces Round 943 (Div.3)F.Equal XOR Segments
文章目录
- 题意
- 思路
- 标程
题意
给出一个长度为 n n n的数组，然后有 m m m次询问，每次询问区间 [ l , r ] [l,r] [l,r]是否是有趣的。
- 有趣的定义： 将区间分为 k k k段 ( 1 < k ) (1<k) (1<k)，使得每段的异或值相等。
思路
区间异或值我们可以通过预处理来解决， b i = b i − 1 ⊕ a i , a l ⊕ a l + 1 . . . a r = b r ⊕ b l − 1 b_i=b_{i-1}⊕a_i~,~a_{l}⊕a_{l+1}...a_r=b_r⊕b_{l-1} bi=bi−1⊕ai , al⊕al+1...ar=br⊕bl−1。
重点就是如何判断区间是否可以分段。
如果区间有趣，那么分成的k段异或值相等。
{ x ⊕ x = 0 x ⊕ 0 = x ⇒ x ⊕ x ⊕ x ⊕ = x \left\{\begin{array}{l} x \oplus x=0 \\ x \oplus 0=x \end{array} \Rightarrow x \oplus x \oplus x \oplus=x\right. {x⊕x=0x⊕0=x⇒x⊕x⊕x⊕=x
- 若k为偶数，那么我们可以按照上面异或的性质合并，那么会发现区间异或值为0。
- 若k为奇数，那么我们可以将k段合并为三段： 0 x 0 0~x~0 0 x 0的形式，即一三段为 0 0 0，第二段可以为任意值。
- 容易证明，当为奇数时，只有这种合并方式可以逆推出区间是否有趣。
标程
void Solved() { int n, m; cin >> n >> m;vector<int> v(n + 1);map<int, vector<int>> mp;mp[0].push_back(0);for(int i = 1; i <= n; i ++ ) {int x; cin >> x;v[i] = x ^ v[i - 1]; //算一下异或前缀和mp[v[i]].push_back(i); //将可以得到这个结果的下标放一起}while(m -- ) {int l, r; cin >> l >> r;if(v[l - 1] == v[r]) { //k为偶数或k为奇数且x=0cout << "YES\n"; continue;}auto &it1 = mp[v[l - 1]];int p1 = *--lower_bound(it1.begin(), it1.end(), r); //找小于等于r的第一个数auto &it2 = mp[v[r]];int p2 = *lower_bound(it2.begin(), it2.end(), l); //找大于等于l的第一个数cout << (p1 > p2 ? "YES" : "NO") << '\n';}cout << endl;
}
这篇关于Codeforces Round 943(Div.3) F.Equal XOR Segments的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
