数的分类
题目
小f回到了璃月，前往位于蒙德和璃月交界处的龙脊雪山。雪山的气候十分恶劣，小f经常感觉自己头晕，并且伴随着打喷嚏的症状，但是他是个热爱冒险喜欢作死的冒险家，所以这些并不能阻拦他登上雪山。在雪山的最高处，有一个奇怪的物品，被人们叫做寒天之钉。小f想要登上这个奇怪的物品。他来到了寒天之钉的正下方，发现这里有一处机关挡在了通往寒天之钉的道路上。这里有两个数字 [l, r] 代表数值的范围，小f需要将区间内的数分为 A、B 两类，并将他们的数目输入左右两侧的机关中。小f被冻得快病倒了，只能向你求助。请你帮助小f解开这个机关，赶快登上寒天之钉，离开雪山。
具体地，一个数转化为二进制后，如果其中 1 的数量大于等于 0 的数量，则这个数为 A 类数，否则为 B 类数。
输入：两个数 l, r，代表数值的范围。
输出：两个数，分别表示 A 类数的个数和 B 类数的个数。
数据范围：1 ≤ l, r ≤ 100000。
样例：
输入
1 7
输出
6 1
思路
写两个函数：countOnes 统计二进制中 1 的个数（%2 判断末位，/2 移位），countBits 统计总位数（每次 /2 计一位）。判断条件化简：1的个数 ≥ 0的个数 等价于 2 × ones ≥ bits，不需要显式统计 0，枚举区间累计 A、B 计数输出。
#include<bits/stdc++.h>
using namespace std;
int countOnes(int x){
int count1=0;
while(x!=0){
if(x%2==1) count1++;
x/=2;
}
return count1;
}
int countBits(int y){
int count=0;
while(y!=0){
count++;
y/=2;
}
return count;
}
int main(){
int l,r;
cin>>l>>r;
int A=0,B=0;
for(int c=l;c<=r;c++){
if(2*countOnes(c)>=countBits(c)) A++;
else B++;
}
cout<<A<<" "<<B<<endl;
return 0;
}复杂度分析
- 时间复杂度：O((r−l+1) · log r)，每个数调用两次函数，循环次数为二进制位数 log₂x。
- 空间复杂度：O(1)。
一开始想同时数 1 和 0 的个数，后来发现 0的个数 = 总位数 − 1的个数，条件 ones ≥ zeros 等价于 2 × ones ≥ bits，完全不需要单独统计 0，化简之后代码也更干净。以后看到"比较两个量"的问题，可以先想想能不能用一个量表示另一个。