B. And It‘s Non

B. And It’s Non-Zero

题意

给出l~r区间，区间内所有数都存在。问最少删除几个数，保证剩下的所有数按位与后不为0。

思路

我们寻找每一位上1的个数，找到1个数最多的那一位，把这一位上为0的数都去掉，剩下的所有数在这一位都是1，按位与之后一定不是0。

起初使用log和lowbit求每一位上的1的个数，但是发现每次询问都需要重新lowbit，时间复杂度太高，WA3.
下边TLE代码：

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 10;int f[70], lg[N];void lowbit(int x) {while (x) {f[lg[x & -x]]++;x ^= (x & -x);}
}int main() {for(int i = 2; i <= N; i ++) lg[i] = lg[i>>1]+1;int T;scanf("%d",&T);while (T--) {int l, r;memset(f, 0, sizeof f);scanf("%d%d",&l,&r);for (int i = l; i <= r; i ++) {lowbit(i);}int ans = -1;for (int i = 0; i <= 100; i ++) {ans = max(f[i], ans);}printf("%d\n",r - l + 1 - ans);}
}

AC代码

然后预处理出每一位1的个数并且使用前缀和预处理每个数和他之前所有数每一位上1的个数。这样每次询问时O(1)。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 10;int mp[N][32]; // mp[i][1~32] = 1的个数
bool get_bit(int i, int x)
{return (x >> i) & 1;
}
int main() {// 预处理所有数每一位上的1，避免重复lowbitfor(int i = 1; i <= N; i ++) {for(int j = 0; j < 32; j ++)if (get_bit(j, i))mp[i][j]++;}for (int i = 1; i <=200000; i++){for (int j = 0; j < 32; j++)mp[i][j] += mp[i - 1][j];}int T;scanf("%d",&T);while (T--) {int l, r;scanf("%d%d",&l, &r);int ans = -1;for(int i = 0; i < 32; i ++)ans = max(ans, mp[r][i] - mp[l-1][i]);printf("%d\n",r - l + 1 - ans);}}

参考文章 blog.csdn.net/thexue/article/details/122148958