题目要求图片说明 最大,涉及到异或操作,很显然我们需要用位运算来处理这题

思路:
位运算时,每一个bit可以被独立的拿出来运算,所以我们记X的第p位bit为图片说明 ,区间里图片说明 的第p位bit为图片说明看看怎么让区间里图片说明 最大,也就是让区间里第p位bit上出现1的次数最多
二进制中每一个bit不是0就是1,我们又知道异或运算图片说明图片说明图片说明 ,想让一个bit变成1,那么参与运算的两个bit必须是一个0和一个1,区间里图片说明都是固定的,所以我们需要改变图片说明
结合题目说明 “若有多组可行解,请输出较小的解”
这样我们就可以推断出:

  • 当区间里第p位上1的数量大于0时,令图片说明
  • 当区间里第p位上1的数量等于0时,令图片说明 ,(输出较小的解)
  • 当区间里第p位上1的数量小于0时,令图片说明

这样对每一个图片说明处理完以后,就得到了符合题意的图片说明

当然,如果每一次询问都数一下出现了多少次1的话计算量 可能 有点大,所以下面用了前缀和

*把DEBUG改成1会输出nums和bit

#include <iostream>
#include <memory.h>
#include <algorithm>

#define DEBUG 0
using namespace std;

int main() {
    int N;  //序列长度
    cin >> N;
    int nums[N + 1];  //a1~aN
    int bit[N + 1][33];   //a1~aN的二进制各个位中1出现的次数(从右往左数)
    memset(nums, 0, sizeof(nums));
    memset(bit, 0, sizeof(bit));
    for (int i = 1; i <= N; ++i) {
        cin >> nums[i];
        for (int j = 0; j <= 31; ++j) {
            bit[i][j + 1] = bit[i - 1][j + 1];
            if (nums[i] & (1 << j))bit[i][j + 1]++;
        }
    }
    //输出nums
    if (DEBUG) {
        cout << "nums: ";
        for (int i = 1; i <= N; ++i) {
            cout << nums[i] << " ";
        }
        cout << endl;
    }
    //输出bit
    if (DEBUG) {
        cout << "bit: " << endl;
        for (int i = 0; i <= N; ++i) {
            cout << "[" << i << "]: ";
            for (int j = 32; j >= 1; --j) {
                cout << bit[i][j] << " ";
            }
            cout << "( " << nums[i] << " )" << endl;
        }
        cout << endl;
    }

    int q;  //询问的次数
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int L, R;    //区间端点(闭区间)
        cin >> L >> R;
        int X = 0;    //解
        for (int j = 31; j >= 1; --j) {
            if (bit[R][j] - bit[L - 1][j] < (R - L + 1) / 2.0) {
                X += (1 << (j - 1));
            }
        }
        cout << X << endl;
    }
}