题解：P14074 [GESP202509 五级] 有趣的数字和

· · 题解

感觉这题真的不止黄（可能是我太菜了<(＿　＿)>

这道题会让我们联想到数位 dp（其实没有多少关系(＠_＠;)

MYBLOG https://www.cnblogs.com/dongdongmao/p/19125902

这里还是借用的老师的思路

计算 l-r 之间有趣数字的个数，也就是 0-r 之间有趣数字的个数减去 0-(l-1) 之间有趣数字的个数

我们想想怎么计算从 0~x 之间一共有多少个有趣数字

另外 30% 的测试点，保证 l=1 并且 r=2^k-1 ，其中 k 是大于 1 的正整数。

题目中的这个有提示意义的数据告诉我们， 2^k-1 可以直接计算(或推出来)， 这样我们就可以试着将数拆成类似于 2^k-1 的形式

like this

代码放上，如果有什么问题记得@我

https://www.luogu.com.cn/discuss/1165743 还有我关于这道题有些问题，希望大佬解答QWQ

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=31;
int l,r;
LL f[N][2],g[N][2],c[N][N];

void init(){
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(j)c[i][j]=c[i-1][j-1]+c[i-1][j];
            else c[i][j]=1;
            f[i][j&1]+=c[i][j];
        }
    }
    for(int i=1;i<N;i++){
        g[i][0]=f[i-1][1]*(1<<(i-1))+g[i-1][0]+g[i-1][1];
        g[i][1]=f[i-1][0]*(1<<(i-1))+g[i-1][1]+g[i-1][0];
    }
}

LL count(int x,int op){
    if(x==0){
        return f[x][op];
    }
    int idx=0;
    for(int i=30;i>=0;i--){
        if((x>>i)&1){
            idx=i;
            break;
        }   
    } 
    LL p=(1<<idx);
    return f[idx][op]+count(x-p,op^1);
}

LL solve(int x,int op){ 
//  cout<<x<<"\n";
    LL res=0;
    int idx=-1;
    for(int i=30;i>=0;i--){
        if((x>>i)&1){
            idx=i;
            break;
        }   
    } 
    if(idx==-1){
        return 0;
    }
    LL p=(1<<idx);
    res=g[idx][op]+p*count(x-p,op^1)+solve(x-p,op^1);
    return res;
}

int main(){
    init();
    cin>>l>>r;
    cout<<solve(r,1)-solve(l-1,1);//1 奇数  0  偶数 
    return 0;
}

审核大大求通过QWQ