其实数位DP,我还是更容易理解DFS
题目描述
求给定区间 [X,Y] 中满足下列条件的整数个数:这个数恰好等于 K 个互不相等的 B 的整数次幂之和。
例如,设 X=15,Y=20,K=2,B=2,则有且仅有下列三个数满足题意:
17=2^4+2^0
18=2^4+2^1
20=2^4+2^2
输入样例
15 20
2
2
输出样例
3
C++ 代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=35,M=25;
int f[N][N],digit[N];
int k,b;
inline int dfs(int eq,int dep,int num)
{
if(num>k) return 0;
if(dep+num<k) return 0;
if(dep==0) return num==k;
if(!eq&&f[dep][num]!=-1) return f[dep][num];
int ed=(eq&&!digit[dep]) ? digit[dep]:1;
int ret=0;
for (int i=0;i<=ed;i++)
ret+=dfs((eq&&(i==digit[dep])),dep-1,num+(i==1));
if(!eq) f[dep][num]=ret;
return ret;
}
inline int dp(int n)
{
if(!n) return 0;
memset(f,-1,sizeof(f));
int cnt=0;
while(n) digit[++cnt]=n%b,n/=b;
return dfs(true,cnt,0);
}
int main()
{
int l,r;
scanf("%d%d%d%d",&l,&r,&k,&b);
printf("%d\n",dp(r)-dp(l-1));
return 0;
}
大佬,跪求解答一下为啥
(eq&&!digit[dep])
要加!digit[dep]
和i==digit[dep]
为啥不是i==ed
??谢谢!!!!!好久之前的题解了,我先看看
嗯嗯,好的,谢谢!!!
大佬,可以只解释
i==digit[dep]
这句话吗??😢这句话确实实在是看不懂了。。😢dfs函数中的eq变量如果为1,说明此时是有界的。何谓有界,假设有一个数1234,如果我第一位上枚举到了1,那我第二位上,可以枚举1,可以是2,但是如果是3的话,就会超过原数范围
i==digit[dep]说明此时我枚举到了边界,
嗯嗯,那可以在解释一下为啥加
!digit[dep]
吗??🤣谢谢!!首先,根据题目要求,要有k个不相等的B进制相加,说明每一位只能填1or0.
再然后,你可以试几个数据,可以知道 ed=(eq&&!digit[dep]) 中ed的值只可能为1or0,
至于加!digit[dep],
哦哦,我懂了,感谢大佬的讲解和分享!!!要是没有大佬的分享,感觉与数位dp无缘了🤣
digit[dep]
就是控制最高位为1的吧🤣别急,我还有没说完的
是的,三目运算符里那个地方可以直接改为0
嗯嗯,感谢!!🤣🤣
如果你想按
i==up
写可以看下我的代码理解一下这里面为什么 i > 1 要break 掉