题意分析
求 $[l,r]$ 中有多少个整数满足其二进制中，$0$ 的个数大于等于 $1$ 的个数。
注意一个数的二进制不包括其前导 $0$。例如对于 $9$，其二进制仅仅是 $1001$。
分块打表
考虑到 $1\leq l\leq r\leq 2\times 10^9$，并不是很大，考虑分块打表。
计算机一秒内能够处理的数据规模约为 $4\times 10^8$，我们使用 $10^7$ 作为一段的长度（过短会导致代码长度过长），只有 $200$ 段，在可接受范围内。
暴力检查函数
很好写。
1
2
3
4
5
6
7
bool check(int x){
int cnt[2]={};
while(x){
cnt[x&1]++;
x>>=1;
}return cnt[0]>=cnt[1];
}
打表程序
很简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2e9,M=1;
bool check(int x){
int cnt[2]={};
while(x){
cnt[x&1]++;
x>>=1;
}return cnt[0]>=cnt[1];
}
int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
printf("int a[%d]={",M+1);
for(int i=1;i<=M;i++){
cerr<<"a["<<i<<"] begined.\n";
int cnt=0;
for(int j=(i-1)*1e7+1;j<=i*1e7;j++){
cnt+=check(j);
}printf("%d",cnt);
if(i<M)putchar(',');
}cout<<"};\n";
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
注意自己的打表程序的边界，不要弄混了，否则就会挂成 $\text{60pts}$。
得到的表（$a[i]$ 是 $[(i-1)\times 10^7+1,i\times 10^7]$ 内所有符合条件的数的个数）：
1
int a[201]={0,4888435,5100564,4184973,5401066,5074479,4995911,4410533,5902664,4975816,3513684,4839148,3548842,2641791,5549869,6899843,6446471,5498547,6094889,5032461,3663540,5968886,5274230,4485769,4248565,3765136,3082735,3162815,7734751,6626021,5536339,6067626,5226918,4668337,4757631,5673930,4808186,3680446,4764462,3301232,2555845,5363735,5092384,4835389,4072879,4107691,3251858,2088458,4973596,3458985,2580781,2936210,1951935,2055300,3517162,8610669,7942279,6775212,7842682,6780557,5897716,6701436,6850798,6483382,5531814,5960939,5071802,3586122,7309227,6797821,6141267,5848161,5405195,4707236,4208129,6201560,5006198,3784125,4446430,3705123,2946680,4798854,7143090,6446629,5327102,6394020,4939432,4008803,5703432,5122944,4787689,4023403,4098897,3215665,2284737,6501746,5094747,4110072,4445311,3338116,3377468,3202275,4146502,3294690,1973496,3421737,2074514,1435403,5984945,8145114,7901124,7051213,7442813,6682171,5222997,7556496,6790162,6018415,5933066,5305335,4794515,4394994,7653969,6616596,5443715,6035709,5334516,4528517,4973939,5499400,4714575,3899077,4615044,3359980,2367413,6615098,6731097,6422442,5575945,5769001,4811974,3684448,6474121,5001002,4108383,4437771,3422194,3247716,3815388,5801645,4901398,3315147,5076632,3456267,2616262,4011539,3390509,3405753,2590428,2639967,1954648,1076639,7579720,6784270,5900492,6004658,5249387,4853619,4251422,6063491,5035260,3656625,4609125,3610833,2865787,4502111,5449214,4636740,4013803,4548431,3383298,2322169,4303970,3645766,3010888,2697155,2404930,1880605,1750939,6431299,4908672,4102754,4451579,3496709,3179149,3300608,4102166,3240561,2090267,3298993,2062209};
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
bool check(int x){
int cnt[2]={};
while(x){
cnt[x&1]++;
x>>=1;
}return cnt[0]>=cnt[1];
}
int a[201]={0,4888435,5100564,4184973,5401066,5074479,4995911,4410533,5902664,4975816,3513684,4839148,3548842,2641791,5549869,6899843,6446471,5498547,6094889,5032461,3663540,5968886,5274230,4485769,4248565,3765136,3082735,3162815,7734751,6626021,5536339,6067626,5226918,4668337,4757631,5673930,4808186,3680446,4764462,3301232,2555845,5363735,5092384,4835389,4072879,4107691,3251858,2088458,4973596,3458985,2580781,2936210,1951935,2055300,3517162,8610669,7942279,6775212,7842682,6780557,5897716,6701436,6850798,6483382,5531814,5960939,5071802,3586122,7309227,6797821,6141267,5848161,5405195,4707236,4208129,6201560,5006198,3784125,4446430,3705123,2946680,4798854,7143090,6446629,5327102,6394020,4939432,4008803,5703432,5122944,4787689,4023403,4098897,3215665,2284737,6501746,5094747,4110072,4445311,3338116,3377468,3202275,4146502,3294690,1973496,3421737,2074514,1435403,5984945,8145114,7901124,7051213,7442813,6682171,5222997,7556496,6790162,6018415,5933066,5305335,4794515,4394994,7653969,6616596,5443715,6035709,5334516,4528517,4973939,5499400,4714575,3899077,4615044,3359980,2367413,6615098,6731097,6422442,5575945,5769001,4811974,3684448,6474121,5001002,4108383,4437771,3422194,3247716,3815388,5801645,4901398,3315147,5076632,3456267,2616262,4011539,3390509,3405753,2590428,2639967,1954648,1076639,7579720,6784270,5900492,6004658,5249387,4853619,4251422,6063491,5035260,3656625,4609125,3610833,2865787,4502111,5449214,4636740,4013803,4548431,3383298,2322169,4303970,3645766,3010888,2697155,2404930,1880605,1750939,6431299,4908672,4102754,4451579,3496709,3179149,3300608,4102166,3240561,2090267,3298993,2062209};
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
int l,r,ans=0,L=2147483647,R=-1;
scanf("%d %d",&l,&r);
if(r-l+1<=2e7){//确保至少存在一段,防止L,R值异常
for(int i=l;i<=r;i++){
ans+=check(i);
}printf("%d\n",ans);
return 0;
}
for(int i=1;i<=200;i++){
if(l<=(i-1)*1e7+1&&i*1e7<=r){
L=min(L,(int)((i-1)*1e7+1));
R=max(R,(int)(i*1e7));
ans+=a[i];
}
}
for(int i=l;i<L;i++){
ans+=check(i);
}
for(int i=R+1;i<=r;i++){
ans+=check(i);
}
printf("%d\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
