欢迎访问个人博客

传送门 $\looparrowright$

题目描述

  小 $a$ 有 $n$ 个数 $a_1,a_2,...,a_n$，给出 $q$ 个询问，每次询问给出区间 $[l,r]$，现在请你找到一个数 $x$，使得 $\sum _{i=l}^{r}x\oplus a_i$最大，要保证 $0\le x<2^{31}$。

输入描述

  第一行一个整数 $n$，表示序列的长度。第二行N个整数，表示序列内的元素。第三行一个整数 $q$，表示询问的个数。接下来 $q$ 行，每行两个整数 $l,r$，表示询问的区间。

输出描述

  输出 $q$ 行，每行一个整数表示答案。若有多组可行解，请输出较小的解。

示例1

输入 5 4 78 12 1 3 3 2 5 1 4 3 3 输出 2147483632 2147483635 2147483635

备注

  对于 $30\%$ 的数据，$n,q\le 10$。对于 $60\%$ 的数据，$n,q\le 1000$。对于 $100\%$ 的数据，$n,q\le 10^5$。保证 $a_i$$ <$ $2^{31}$。

分析

  将所有数拆成 $31$ 位二进制数。对于一个区间 $[l,r]$，若 $x $ 的第 $j$ 位为 $1$，且 $[l,r]$ 内第 $j$ 位为 $0$ 的数字个数为 $se{g}_0$，那么对和式 $\sum _{i=l}^{r}x\oplus a_i$ 产生的贡献为 $se{g}_0\times 2^j$；同理，若 $x$ 的第 $j$ 位为 $0$ ,且 $[l,r]$ 内第 $j$ 位为 $1$ 的数字个数为 $se{g}_1$，那么对和式 $\sum _{i=l}^{r}x\oplus a_i$ 产生的贡献为 $se{g}_1\times 2^j$。   $se{g}_0\times 2^j>se{g}_1\times 2^j$ 的充要条件是 $se{g}_0>se{g}_1$。每次询问一个区间 $[l,r]$，我们依次考察 $[l,r]$ 内所有数的第 $0\sim 30$ 位，若某一位 $0$ 居多，则 $x$ 在该位取 $1$；否则，$x$ 在该位取 $0$。   显然，可以预处理某一位 $1$ 个数的前缀和，考察一个区间时，可以 $O(1)$ 得到答案。

代码

#include<iostream> #include<cstdio> #define N 100003 using namespace std; //------------------------------ //代表[1,i]的数字第j位为1的数字个数 int sum[N][32]; //------------------------------ int q; int n; int main() { cin>>n; int i,j; for(i=1;i<=n;i++) { int temp; scanf("%d",&temp); for(j=0;j<=30;j++) { if(temp&(1<<j)) sum[i][j]=1;//第j位为1 else sum[i][j]=0;//第j位为0 } } for(i=1;i<=n;i++)//计算前缀和 { for(j=0;j<=30;j++) { sum[i][j]+=sum[i-1][j]; } } cin>>q; while(q--) { int l,r; int x=0; scanf("%d%d",&l,&r); for(j=0;j<=30;j++) { int seg1=sum[r][j]-sum[l-1][j];//第j位为1的个数 int seg0=r-l+1-seg1;//第j位为0的个数 //若0的个数多，该位取1。 if(seg0>seg1) x=x+(1<<j); } printf("%d\n",x); } return 0; }