河南萌新联赛2024第（三）场:F累加器(前缀和)

题目描述

存在一个累加器，每次可以对一个数进行加 111 操作，此时在二进制下有一些位发生改变，对一个数 xxx 进行 yyy 次累加操作，总共有多少位发生改变。

输入描述:

第一行一个正整数 TTT (1≤T≤105)(1\leq T \leq 10^5)(1≤T≤105)代表多组询问。

接下来 TTT 行 每行两个正整数 x,y(1≤x,y≤106)x,y(1\leq x,y \leq 10^6)x,y(1≤x,y≤106)，代表对 xxx 进行 yyy 次累加操作。

输出描述:

TTT 行每组询问一行代表总共发生改变的位数。

示例1

输入

复制4 1 4 10 1 20 20 1 100

4
1 4
10 1
20 20
1 100

输出

复制7 1 40 197

7
1
40
197

说明

对于第一个样例开始 (0001)2(0001)_2(0001)2​ 进行 444 次累加。

第一次 (0010)2(0010)_2(0010)2​ 两位改变。

第二次 (0011)2(0011)_2(0011)2​ 一位改变。

第三次 (0100)2(0100)_2(0100)2​ 三位改变。

第四次 (0101)2(0101)_2(0101)2​ 一位改变。

做法

先预处理前缀和，前缀和数组表示为从1到i的转换次数。

#include<bits/stdc++.h>
using namespace std;
int t,ans;
int x,y;
int qzh[2000010];
int main(){
    scanf("%d",&t);
    for(int i=1;i<=2000000;i++){
        int x=i^(i-1);//i和i-1二进制不同的话，该位是1
        int cnt=0;
        while(x){
            if(x&1) cnt++;//看有多少个1
            x >>= 1;
        }
        qzh[i]=qzh[i-1]+cnt;
    }
    while(t--){
        ans=0;
        scanf("%d%d",&x,&y);
        y+=x;
        cout<<qzh[y]-qzh[x]<<endl;
        
    }
}

比赛时写超时了，我还真的去暴力模拟了。然后发现有类似1213121412131215的规律，想了半天想表示这个规律，太难，弄不出来。就一直在转牛角尖，也没想到用别的方法。