关于解决 NC18979 毒瘤xor 时发生的卡顿及问题

题目链接：https://ac.nowcoder.com/acm/problem/18979

题目描述：

小a有N个数a1, a2, ..., aN，给出q个询问，每次询问给出区间[L, R]，现在请你找到一个数X，使得

1、0⩽X<2³¹

2、 $\sum^{R}_{i=L}X⊕a[i]$ 最大,⊕表示异或操作(不懂的请自行百度)

数据范围：

对于30%的数据，n , q ≤ 10

对于60%的数据，n , q ≤ 1000

对于100%的数据，n, q ≤ 10⁵

保证a_i < 2³¹

解题思路：

X 最大值可以为2147483647，即2³¹-1

xor 异或，相当于二进制非进位加法。

实质上是比较每次询问的所有数的对应二进制数中，统计所有数的每位的 01 个数，

初步：

把数组a的每一个数转换为二进制01串数组，
再统计每次询问的范围中二进制每一列的01个数是否超过 (询问范围的数字个数)/2

第一次卡顿：

被一个非常简单的隐藏细节卡（很气！），第60行，奇数问题，判定询问的范围为奇数时，(询问范围的数字个数)/2 ---->小数会四舍五入，导致判断错误。
比如查询 q = 3 个数，
if (one[k] >= (R-L+1)/2)
ans -= (1 << k);
我们希望它在统计出 one_k == 2 或 3 的时候要执行，但是上面的代码实际上是one_k >= 3/2=1 时就执行。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>

using namespace std;

const int maxn = 1e5+7;
int a[maxn] = {};

// 每轮统计[L, R]范围内的 0 的个数， 
// 把个数等于 R - L + 1 的那位标记出来让2^31 来减
int one[35] = {};

long long result[maxn] = {};

void deal(int x) // 可以参考NC 200190 的矩阵消除游戏的思路：先二进制枚举行，再贪心选列，这里的deal参考先二进制枚举行的思路
{
	int i = 0;
	while (x)
	{
		if ((x&1))
		{
			one[i]++;
		}
		x >>= 1;
		i++;
	}

}

int main ()
{
	int N;
	cin >> N;
	
	memset(a, 0, sizeof(a));
	
	for (int i = 1; i <= N; i++)
		cin >> a[i];
	
	int q;
	cin >> q;
	
	int L, R;
	for (int i = 1; i <= q; i++)
	{
		memset(one, 0, sizeof(one));
		long long ans = 0x7fffffff; // (1 << 31) - 1
		
		cin >> L >> R;		
		
		for (int j = L; j <= R; j++)
			deal(a[j]);
		
		if (L != R)
		{
			for (int k = 0; k < 31; k++)
				if (one[k] >= (R-L+1)/2)
					ans -= (1 << k);
		}
		else 
		{
			for (int k = 0; k < 31; k++)
				if (one[k] == 1)
					ans -= (1 << k);
		}
		
		result[i] = ans;
	}	
	for (int i = 1; i <= q; i++)
	{
		cout << result[i];
		if (i != q)
			cout << endl;	
	}
}

// 通过率0%

改进：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>

using namespace std;

const int maxn = 1e5+7;
int a[maxn] = {};

// 每轮统计[L, R]范围内的 0 的个数， 
// 把个数等于 R - L + 1 的那位标记出来让2^31 来减
int one[35] = {};

long long result[maxn] = {};

void deal(int x)  // 可以参考NC 200190 的矩阵消除游戏的思路：先二进制枚举行，再贪心选列，这里的deal参考先二进制枚举行的思路
{
	int i = 0;
	while (x)
	{
		if ((x&1))
		{
			one[i]++;
		}
		x >>= 1;
		i++;
	}

}

int main ()
{
	int N;
	cin >> N;
	
	memset(a, 0, sizeof(a));
	
	for (int i = 1; i <= N; i++)
		cin >> a[i];
	
	int q;
	cin >> q;
	
	int L, R;
	for (int i = 1; i <= q; i++)
	{
		memset(one, 0, sizeof(one));
		long long ans = 0x7fffffff; // (1 << 31) - 1
		
		cin >> L >> R;		
		
		for (int j = L; j <= R; j++)
			deal(a[j]);
		
		if (L != R)
		{
			for (int k = 0; k < 31; k++)
				// if (one[k] >= (R-L+1)/2)  
				// 这种写法有问题，会有奇数导致四舍五入的问题
				// 此问题隐藏卡的有点气！，下面是解决方法
				if (one[k]*2 >= (R-L+1))
					ans -= (1 << k);
		}
		else 
		{
			for (int k = 0; k < 31; k++)
				if (one[k] == 1)
					ans -= (1 << k);
		}
		
		result[i] = ans;
	}	
	for (int i = 1; i <= q; i++)
	{
		cout << result[i];
		if (i != q)
			cout << endl;	
	}
}

// 通过率： 60% ————> 被数据范围卡，超时！！！

最终解题：

#include<iostream>
using namespace std;
const int N = 1e5+7;
int n, q;
int l, r;
int a[N][35];
int sum[N][35];
 
int main ()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i][0]; // 哨兵暂存读入的数据
        for (int j = 1; j <= 31; j++)
            a[i][j] = (a[i][0] >> (j-1)) & 1;         
    }
     
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 31; j++)
            sum[i][j] += a[i][j] + sum[i-1][j];
     
    cin >> q;
    while(q--)
    {
        int x = 0;
        int cnt;
        cin >> l >> r;
        for (int i = 1; i <= 31; i++)
        {
            cnt = sum[r][i] - sum[l-1][i];
            if (cnt < r-l+1-cnt)
                x += 1 << (i-1);
        }
        cout << x << endl;
    }
    return 0;
}

// AC