题解：CF2053C Bewitching Stargazer

lalaji2010 · 2024-12-29 17:18:34 · 题解

CF2053C Bewitching Stargazer

分析

又是一道结论题。

由于两边在进行区间拆分的过程中是严格对称的，所以最终的答案显然是某个系数 c 乘上中位数。

然后我们发现我们只需要一层一层模拟就好了，我们将 n 不断除以二，设 n 本身这一层为第 0 层；如果第 k 层的 n 是奇数，令 cnt 加上 2^k 即可。

代码应该相当好懂，记得把 n 的值先存一下，后面算中位数还要用到。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int t;
long long n,k;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        long long t=n;
        long long tmp=1;
        long long cnt=0;
        while(1){
            if(n<k){
                break;
            }
            if(n%2==1){
                cnt+=tmp;
            }
            n/=2;
            tmp*=2;
        }
        cout<<cnt*(1+t)/2<<"\n";
    }
    return 0;
}