原题链接:https://www.luogu.com.cn/problem/P6824
题意解读:已知整数序列a[i],i在1~n,有整数k,求一个整数x,要求a[i] ^ x <= k,使得符合要求的a[i]数量最多,求这个数量。
解题思路:
1、确定x的范围
由于a[i] ^ x <= k,因此,x的有效二进制位不可能超过a[i],而a的取值范围<=1000000,因此x差不多最多20位,取值范围是0~2^20 - 1
2、分情况讨论
对于每一个a[i],枚举a[i]和k的每一个二进制第j位(第一位是0),设定初始x = 0
如果k的第j位是1:
当a[i]的第j位是1:
x的第j位如果取1,异或之后得0,j之后随便取都能保证结果比k小,因此得到一个有效的x的范围 [x + (1 << j), x + (1 << j + 1) - 1]
x的第j位如果取0,还需要继续处理j之后的二进制位,此时x的值依然是x
当a[i]的第j位是0:
x的第j位如果取0:异或之后得0,j之后随便取都能保证结果比k小,因此得到一个有效的x的范围[x, x + (1 << j) - 1]
x的第j位如果取1:还需要继续处理j之后的二进制位,此时x的值更新为x + (1 << j)
如果k的第j位是0:
x的第j位必须和a[i]的第j位一致,异或之后才得0,才能保证结果不超过k,此时x根据a[i]第j位的情况来更新
如果a[i]第j位是1,x更新为x + (1 << j),否则x值还是x
最后得到的x也是一个有效的x
3、差分统计
对于以上分情况讨论中,得到的有效x的区间,最后统计一个覆盖最多的x的即可,可以借助于哈希数组
定义数组s[1 << 20],s[i]表示满足a ^ i <= k的a的数量
当找到一个有效的x的范围,对范围内每一个元素加1即可,如何快速实现区间加1?可以借助于差分数组,定义c[1 << 20]来进行区间加1操作,最后再还原s数组,找到s中最大值即是答案。
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005, X = (1 << 20); //X取值范围,是a[i]对应值的有效二进制位的最大值
int n, k, a[N], c[X], s[X], ans;
//利用差分数组c[]将l~r区间每个数加上1
void update(int l, int r)
{
c[l]++;
c[r + 1]--;
}
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) //对每一个a[i]按位与k进行比较
{
int x = 0; //x初始值
for(int j = 20; j >= 0; j--) //枚举a[i]和k的每一位
{
if(k >> j & 1) //k的第j位是1
{
if(a[i] >> j & 1) //a[i]的第j位也是1
{
//x的第j位如果是1,后面是多少都可以满足
//对应到x的取值范围是x + (1 << j) ~ x + (1 << j + 1) - 1
update(x + (1 << j), x + (1 << j + 1) - 1);
//x的第j位如果是0,还要继续看后面的,此时第j位的0对x没有贡献
}
else //a[i]的第j位是0
{
//x的第j位如果是0,后面是多少都可以满足
//对应到x的取值范围是x ~ x + (1 << j) - 1
update(x, x + (1 << j) - 1);
//x的第j位如果是1,还要继续看后面的,此时第j位的1对x有贡献
x += (1 << j);
}
}
else //k的第j位是0
{
//x的第j位必须与a[i]的第j位相同,然后继续看后面的
if(a[i] >> j & 1)
{
x += (1 << j);
}
}
}
//最终得到的x是符合要求的
update(x, x);
}
ans = c[0];
s[0] = c[0];
for(int i = 1; i < X; i++)
{
s[i] = s[i - 1] + c[i]; //还原前缀和
ans = max(ans, s[i]); //取最大值即得到x能满足的最多的a[]的数量
}
printf("%d", ans);
return 0;
}
标签:洛谷题,位是,之后,异或,P6824,EZEC,如果,范围 From: https://www.cnblogs.com/jcwy/p/18520267