1057. Amount of Degrees
Time limit: 1.0 secondMemory limit: 64 MB
Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactlyKdifferent integer degrees ofB.
Example.LetX=15,Y=20,K=2,B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
17 = 24+20,18 = 24+21,20 = 24+22.
Input
The first line of input contains integersXandY, separated with a space (1≤X≤Y≤2311). The next two lines contain integersKandB(1≤K≤20; 2≤B≤10).
Output
Output should contain a single integer— the amount of integers, lying betweenXandY, being a sum of exactlyKdifferent integer degrees ofB.
Sample
inputoutput
15 20223
/*题意: 求一个区间的 degree进制的1的个数为k的数的个数思路:数位dp,一定要注意是1个个数为k dp[i][j][k] 代表到达了i位的j进制还差k个1具体注意的地方写在了代码中*/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<stack>#include<vector>#include<set>#include<map>#define L(x) (x<<1)#define R(x) (x<<1|1)#define MID(x,y) ((x+y)>>1)#define bug printf("hihi\n")#define eps 1e-8typedef long long ll;using namespace std;#define N 35int dp[33][15][33];int degree,k;int bit[N];int dfs(int pos,int degree,int t,bool bound){if(t<0) return 0;if(pos==0) return t ? 0:1;if(!bound&&dp[pos][degree][t]>=0) return dp[pos][degree][t];int up=bound ? min(bit[pos],1):1;int ans=0;for(int i=0;i<=up;i++)ans+=dfs(pos-1,degree,t-i,bound&&i==bit[pos]); //必须是bit[pos]，不能是uoif(!bound) dp[pos][degree][t]=ans;return ans;}int solve(int x){int i,j;int len=0;while(x){bit[++len]=x%degree;x/=degree;}return dfs(len,degree,k,true);}int main(){int i,j,le,ri;memset(dp,-1,sizeof(dp));while(~scanf("%d%d",&le,&ri)){scanf("%d%d",&k,°ree);printf("%d\n",solve(ri)-solve(le-1));} return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，所有的赏赐都只是被用来奖励工作成果的。
