往期浏览

第六期 - 树上分治

位运算

讲解

常见的位运算为：与、或、异或这三种。

这一块的内容比较散乱，以海量刷题为首要学习方向，同时需要收集一些常用结论。

常用结论

1. 对于给定的 \(X\) 和序列 \([a_1,a_2,\dots,a_n]\) ，有：\({X=(X {\rm and} a_1) {\rm or} (X {\rm and} a_2) {\rm or} \dots {\rm or} (X {\rm and} a_n)}\) 。
   原理是 $ {\rm and} $ 意味着取交集，$ {\rm or} $ 意味着取子集。

题单

1. 牛客小白月赛49C - 圣：考察了常用结论；
2. abc147_d - Xor Sum 4：基础拆位操作；
3. abc117_d - XXOR：基础拆位操作，与上一题几乎一致；
4. arc098_b - Xor Sum 2：考察了异或的常用性质。

部分题解

题单第二题 abc147_d - Xor Sum 4

题意：给定长度为 \(N\) 的序列 \(A\) ，计算 \(\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}(A_i \oplus A_j)\) 。

单纯位运算。拆位，对于每一位而言，只有 \(0\) 和 \(1\) 相互组合才能产生贡献，所以每一位的贡献即为 \(0\) 和 \(1\) 的乘积： \(cnt_0 \cdot cnt_1 \cdot 2^i\) 。

坑：别忘了取模。

signed main() {
    int n;
    cin >> n;
    
    vector<int> bit(60);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        
        bitset<60> val = x;
        for (int j = 0; j < 60; j++) {
            bit[j] += val[j];
        }
    }
    
    Z ans;
    for (int i = 0; i < 60; i++) {
        ans += (Z)bit[i] * (Z)(n - bit[i]) * (Z)(1LL << i);
    }
    cout << ans << endl;
}

题单第三题 abc117_d - XXOR

题意：给定长度为 \(N\) 的序列 \(A\) ，在 \([1,K]\) 范围内取一个 \(X\) ，使得 \(\displaystyle \sum_{i=1}^{N}(A_i \oplus X)\) 最大。

单纯位运算。和上一题差不多的思路，略难一点。首先每一位的贡献还是 \(0\) 和 \(1\) 的乘积，从高位到低位遍历，判断 \(X\) 的这一位为 \(0\) 合适还是为 \(1\) 合适（即判断 \(cnt_1\) 是否大于 \(cnt_0\) ）；若为 \(1\) 合适，判断是否会超过 \(K\) 的限制。

坑：数据比较弱，一开始多加了个排序的贪心，结果就WA了一个点。

signed main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> bit(40);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        
        bitset<40> val = x;
        for (int j = 0; j < 40; j++) {
            bit[j] += val[j];
        }
    }
    
    int X = 0, ans = 0;
    for (int i = 39; i >= 0; i--) {
        if (n - bit[i] > bit[i] && X + (1LL << i) <= k) {
            X += (1LL << i);
            ans += (n - bit[i]) * (1LL << i);
        } else {
            ans += bit[i] * (1LL << i);
        }
    }
    cout << ans << endl;
}

题单第四题 arc098_b - Xor Sum 2

题意：给定长度为 \(N\) 的序列 \(A\) ，求解区间 \([l,r]\) 的数量，使得 \(a_l,a_{l+1},\dots a_{r-1},a_r\) 的异或和等于和。

位运算+尺取+暴力，也有双指针、二分解。由于位运算满足 \(x\oplus x\oplus x=0\) ，符合尺取性质，所以直接暴力即可。

如果用二分或者双指针解，可能需要用到：如果两个元素的某一位均为 \(1\) ，那么其异或和一定小于和，所以我们需要寻找这样的一个区间，对于每一位均满足这一位为 \(1\) 的元素数量不超过一个。

signed main() {
    int n;
    cin >> n;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    int ans = 0, val = 0;
    for (int l = 1, r = 0; l <= n; l++) {
        while (r + 1 <= n && (val ^ a[r + 1]) == val + a[r + 1]) {
            r++;
            val ^= a[r];
        }
        ans += r - l + 1;
        val ^= a[l];
    }
    cout << ans << endl;
}