- 技术
- 毒瘤xor（二进制，贪心）
思路：我们要他异或的和最大那么我们对第i位为1时X的第i为0，第i位为0时X的第i位为1，这时我们需要知道区间L-R的第i位是1多还是0多，用前缀和的思想sum[i][j]表示从1到第i个数的第j位上1的个数之和，要保证x最小那么我们再1的个数和0的个数相同的情况下将X的第i位置0
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e4+7;
const int N
=2e5+10;
const int inf
=0x7f7f7f7f;
ll
gcd(ll a
,ll b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
int sum
[N
][35],a
[N
];
int main()
{
int n
,m
;
read(n
);
for(int i
=1;i
<=n
;i
++)
read(a
[i
]);
for(int i
=1;i
<=n
;i
++)
{
for(int j
=0;j
<31;j
++)
{
sum
[i
][j
]=sum
[i
-1][j
]+((a
[i
]>>j
)&1);
}
}
read(m
);
while(m
--)
{
int l
,r
;
read(l
),read(r
);
int ans
=0;
for(int i
=0;i
<31;i
++)
{
int x
=sum
[r
][i
]-sum
[l
-1][i
];
if(x
*2<r
-l
+1) ans
+=(1<<i
);
}
write(ans
);enter
;
}
return 0;
}
Processed:
0.017, SQL:
8
