当前位置：首页 > article >正文

【菜笔cf刷题日常-1400】C. Johnny and Another Rating Drop（位运算，数学）

article 2024/11/29 21:22:30

链接：Problem - 1362C - Codeforces

题意：给出一个 n ，求出 0 ~ n 在二进制下每相邻两数的不同位数的总和。

思路：先列了几个找了一下规律，取 i 在 0 ~ n 之间，当 i 等于 $2^{k}$ 时，其不同位数等于 k 。

并且可以进一步发现： $2^{k}$ 之前的总和 = $2^{k-1}$ 之前的总和 + ( k - 1 )。

并且对于任意一位而言，其总和的计算可以在 $2^{k}$ （不同位阶）之间独立计算。

因此只要预处理一个 k 在1 ~ 63 区间内 $2^{k}$ 之前的总和，随后遍历 n 的每一位是否为 1 ，求得总和。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t,k,l,r,q,p,x,idx,res,cnt,sum,flag,maxx,minn;
const int N=200010;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f3f3f3f3f;
int a[N],b[N];

int lowbit(int x){
	return x & -x;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int sum=0,res=0;
	for(int i=1;i<=63;i++){			
		a[i-1]=res+i;
		res=res*2+i;
	}

	cin>>t;
	while(t--){
		cin>>n;
		int ans=0;
		for(int i=0;i<=62;i++){
			if(lowbit(n>>i)==1){
				ans+=a[i];
			}
		}
		cout<<ans<<"\n";

	}

	return 0;
}

查看全文

http://www.kler.cn/a/414709.html