（数位DP）【题解】CF611B-New Year and Old Property

本文主要是介绍（数位DP）【题解】CF611B-New Year and Old Property，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出A、B，请你求出从 A 到 B 之间的所有数中，有多少数转化为 $2$ 进制后，只有一个零。$1\le a,b\le 10^{18}$

思路

加上数据范围考虑就是一道很明显的数位 DP 好吧

在进行搜索的时候我们可以保存一个当前 $0$ 的个数，搜完后判断当前 $0$ 的个数是不是为 $1$ ,是的话就累加答案，最后加个记忆化就行了

code:

int dp[MAXN][MAXN];
int dfs(int pos,bool lim,int cnt0){if(pos==0) return (cnt0==1);if(!lim && ~dp[pos][cnt0]){return dp[pos][cnt0];}int up=lim?a[pos]:1;int ans=0;for(int i=0;i<=up;i++){ans+=dfs(pos-1,lim&&(i==a[pos]),cnt0+(i==0));}if(!lim){dp[pos][cnt0]=ans;}return ans;
}

但是这样又有问题了

在上面这份代码中，前导 $0$ 也会被算作是 $0$，这样就会影响答案

所以我们还需再加一个对前导 $0$ 的判断：

code：

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define int long long
const int MAXN=75;
int a[MAXN];
int dp[MAXN][MAXN];
int dfs(int pos,bool lim,int cnt0,bool zero){
//	cout<<pos<<endl;if(pos==0) return (cnt0==1);if(!lim && ~dp[pos][cnt0] && !zero){return dp[pos][cnt0];}int up=lim?a[pos]:1;int ans=0;for(int i=0;i<=up;i++){ans+=dfs(pos-1,lim&&(i==a[pos]),cnt0+(i==0 && !zero),zero && i==0);}if(!lim && !zero){dp[pos][cnt0]=ans;}return ans;
}
int work(long long n){memset(dp,-1,sizeof(dp));int cnt=0;while(n){a[++cnt]=n%2;n/=2;}return dfs(cnt,1,0,1);
}
signed main(){long long l,r;scanf("%lld %lld",&l,&r);printf("%lld",work(r)-work(l-1));
return 0;
} 

这篇关于（数位DP）【题解】CF611B-New Year and Old Property的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---