B. And It‘s Non-Zero
题目链接：https://codeforces.com/problemset/problem/1615/B
位运算之前没怎么写过，所以不会写。留一份题解，作为复习使用。
题解：按位与的结果不为0，则至少有一列全为1.要求删除的数最少，即要求该列原本含有的1最多。则统计每一位的1的个数，找出个数最大值，用数组数字的总数，减去1的个数，即需要删除的个数。
第一版写的是枚举每一个数，对每一个数的每一位用&（1<<j)判断是不是1，用一个数组来统计每一位的结果。然而是TLE...
第二版，借助AI工具，发现了从0开始到某一位的数据的二进制排列规律，用前缀和求解可得。
背景知识
在二进制表示中，每一位（bit）会以固定的周期出现 0 和 1。例如：
- 第 0 位（最低位）：
0, 1, 0, 1, 0, 1, ...，周期为 2。 - 第 1 位：
0, 0, 1, 1, 0, 0, 1, 1, ...，周期为 4。 - 第 2 位：
0, 0, 0, 0, 1, 1, 1, 1, ...，周期为 8。
我们可以直接计算某一位为 1 的数量，而不需要逐个遍历每个数字。
公式解释
1. 完整周期的贡献
对于第 j 位：
- 每
(1 << (j + 1))个数字中，第 j 位会有连续(1 << j)个 1。 - 例如：
- 第 0 位：每 2 个数字中有 1 个 1。
- 第 1 位：每 4 个数字中有 2 个 1。
- 第 2 位：每 8 个数字中有 4 个 1。
完整的 (1 << (j + 1)) 块的数量为：（r + 1）/(1 << (j + 1)) ＋1是因为0也要算进去
这些完整块中，第 j 位的 1 的总数为：（r + 1）/(1 << (j + 1)) * (1 << j)
2. 剩余部分的贡献
可能还有一部分数字不足一个完整的 (1 << (j + 1)) 块，这部分的长度为 (r + 1) % (1 << (j + 1))
在这部分中，第 j 位为 1 的数量为：
- 如果剩余部分长度大于
(1 << j)，那么第 j 位会有 (r + 1) % (1 << (j + 1)) - (1 << j)个 1。 - 如果剩余部分长度小于等于
(1 << j)，那么第 j 位会有0个 1。
3. 总计第 j 位的 1 的数量
将完整周期和剩余部分的贡献相加
代码如下：
#include <bits/stdc++.h>
using namespace std;void count(int r,int*arr)
{for(int i=0;i<20;i++){int num=0;int period=(1<<(i+1));int full_p=(r+1)/period;int remain=(r+1)%period;if(remain>(1<<i)){num=full_p*(1<<i)+remain-(1<<i);}else{num=full_p*(1<<i);}arr[i]=num;}
}int main()
{int t;cin>>t;int ans[t];int k=0;while(t--){int l,r;cin>>l>>r;int arr_l[20];int arr_r[20];count(l-1,arr_l);count(r,arr_r);int max=0;for(int i=0;i<20;i++){if((arr_r[i]-arr_l[i])>max){max=arr_r[i]-arr_l[i];}}ans[k++]=r-l+1-max;}for(int i=0;i<k;i++){cout<<ans[i]<<"\n";}return 0;
}