题目描述
存在一个累加器,每次可以对一个数进行加 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二进制不同的话,该位是1int cnt=0;while(x){if(x&1) cnt++;//看有多少个1x >>= 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的规律,想了半天想表示这个规律,太难,弄不出来。就一直在转牛角尖,也没想到用别的方法。