兩個bit的異或（下文均用^代表異或運算）：1^0=1 0^1=1 1^1=0 0^0=0，也就是左右元素不同時為1，相同時為0。

對于兩個int的異或，就是對它的二進制表示的每一位進行異或運算，比如2^5=binary(010^101)=binary(111)=7

并且異或運算滿足交換律、結合律，即a^b=b^a，a^b^c=(a^b)^c=a^(b^c)

異或運算還有性質：x^0=x，x^x=0（這里可以得出推論：若x^y=0，則x=y；）

OK，到此就可以分析題目了，題目給出數組a[N]找出所有不重疊區間，區間的數字xor和為0。

這里定義f(i,j)=a[i]^a[i+1]^...^a[j]，這里值得注意的是不重疊區間，那么假如有一對重疊區間的xor和為0，那我們應該選擇哪一組呢？

設重疊區間為[b,c]，兩個區間為[a,c]和[b,d]，其中a<=b<c<=d。

顯然應該選擇[a,c]，因為這樣相當于在[c,N]區間尋找xor和為0的子區間數量，而c<=d<N，[c,N]是在[d,N]的基礎上多了0個以上數，那么子區間數量肯定不少于[d,N]。

因此思路就是先找出最左邊的子區間，然后在右邊剩余區間重復以上操作。

最左邊也就是區間[a,b]滿足b最小，也就是b從0到n，如果找到了一組異或和為0的區間[a0,b0]，那么b就從b0+1開始，但是a不用從0開始，而是也從a0+1開始。

因為若存在f(a0,b0+t)=0，那么易證f(b0+1,b0+t)也為0，可以分成2個異或和為0的區間。

更詳細的證明就不用說了，有這樣的思路后直接上代碼吧。

#include <iostream> #include <vector> #include <algorithm> using namespace std;void solution(int a[], int n) {int cnt = 0; // 閉區間個數vector<int> v;v.reserve(n);int low = 0; // 閉區間左邊界的下限(即上一個找到異或和為0的閉區間右邊界+1)for (int i = 0; i < n; i++){ // 查找以i為閉區間的右邊界的區間是否存在滿足異或和為0的 v.clear();// 依次加入a[k]、a[k-1]^a[k]、...、a[low]^a[low+1]^...^a[k] v.push_back(a[i]);for (int j = i - 1; j >= low; j--){v.push_back(v.back() ^ a[j]);}if (find(v.begin(), v.end(), 0) != v.end()){ // 存在異或和為0的子區間cnt++;low = i + 1; // 更新閉區間左邊界, 避免重復查找 }}cout << cnt << endl; }int main() {int n;cin >> n;vector<int> v(n);for (int i = 0; i < n; i++){cin >> v[i];}solution(&v[0], n);return 0; }

?

轉載于:https://www.cnblogs.com/Harley-Quinn/p/7513052.html

總結

以上是生活随笔為你收集整理的2017滴滴出行笔试题：异或和为0的最大区间个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。