道长的算法笔记：经典哈希表问题

(一)哈希表简述

Waiting…

(二)使用哈希表优化复杂度

(2.1) 两数之和

Waiting…

(2.2) 子数组异或和

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

#define maxn 300005

int n;
int ar[maxn], xr[maxn];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> ar[i];
        xr[i] = xr[i - 1] ^ ar[i];
    }
    // 子数组的长度必须是偶数，然而枚举左端点与数组长度的 O(n^2) 做法无法逃过 TLE
    int ans = 0;
    for(int len = 2; len <= n; len += 2){
        for(int i = 1; i + len - 1 <= n; i++){
            int j = i + len - 1;
            int m = (i + j) / 2;
            if((xr[m] ^ xr[i - 1]) == (xr[j] ^ xr[m])){
                ans++;
            }
        }
    }
    printf("%d/n", ans);
    return 0;
}

Waiting…