数花（count）题解

发表于 更新于 本文字数： 314 阅读时长 ≈ 1 分钟

题干传送门

先说结论：若用一个数组 cc 来存数 i(i>1)i(i>1) 中 00 的个数，则：

  • 当 ii 为偶数， ci=ci2+1c_i=c_{\frac{i}{2}}+1 ；
  • 当 ii 为奇数， ci=c⌊i2⌋c_i=c_{\lfloor\frac{i}{2}\rfloor} 。

举个例子，当 i=6i=6 ，其二进制表示为 (110)2(110)_2 。 i2\frac{i}{2} 即为 33 ，二进制表示为 (11)2(11)_2 ，相当于将 nn 的二进制表示去掉最后一位 。而去掉的这一位刚好为 00 ，因此要在 ci2c_{\frac{i}{2}} 的基础上加上 11 。奇数同理。

这样以后，就可以 O(n)O(n) 处理出 10710^{7} 内的 cc 。

最后，再前缀和预处理一下 cc 就可以 O(1)O(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
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000001;
int c[maxn];
int q[maxn];  // 前缀和
int n,m,l,r;
void init()
{
    c[0]=1,c[1]=0;
    if(n==0) q[0]=0,q[1]=1;
    else if(n==1) q[0]=q[1]=1;
    else q[0]=q[1]=0;
    for(int i=2;i<maxn;i++)
    {
        if(i&1) c[i]=c[i>>1];  //当 i 是奇数，c[i]=c[i/2]
        else c[i]=c[i>>1]+1;	//当 i 是偶数，c[i]=c[i/2]+1
        q[i]=q[i-1];
        if(c[i]==n) ++q[i];  
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    init();
    while(m--)
    {
        scanf("%d%d",&l,&r);
        if(l==0) printf("%d\n",q[r]);
        else printf("%d\n",q[r]-q[l-1]);
    }
    return 0;
}