首页 > 代码库 > URAL1057 Amount of Degrees

URAL1057 Amount of Degrees

2024-07-20 10:47:11   212人阅读

题意：给定x,y,K,B，要求找出在区间[x,y]内的正整数个数，使它们满足恰好由K个不同的某个B的幂组成

例如

 X=15, Y=20, K=2, B=2
17 = 24+20,
18 = 24+21,
20 = 24+22. 有三个正整数满足要求
 
把问题转化一下，设g(x)为有多少个<=x的正整数满足题意，那么原题差分一下=g(y)-g(x-1)
现在解决转化之后的问题，把x进行B进制展开，目标是得到一个B进制串使它只含0和1，并且小于等于x，可以用动态规划来解决
用f[i][j][flag]表示进行到第i位，有j个1，flag=0,1分别表示小于，等于时的满足要求的总数，递推式容易得到，从高位到低位递推，注意细节。
最后答案为f[1][k][0]+f[1][k][1]（这里1为最低位）
 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 int x,y,k,b; 5 int len,Bbas[51]; 6 int f[51][21][2]; //1 等于 0 小于  7 int solve(int p){ 8     len=0;memset(Bbas,0,sizeof(Bbas)); 9     memset(f,0,sizeof(f));10     int t=p;11     while (t){12         Bbas[++len]=t%b;t=t/b;13     }14     if (Bbas[len]==1) {f[len][1][1]=1;f[len][0][0]=1;}15         else {f[len][1][0]=1;f[len][0][0]=1;}16     for (int i=len-1;i>=1;i--)17         for (int j=0;j<=k;j++){18             if (j==0) {19                 f[i][j][0]=1;20             }else {21                 if (Bbas[i]>1) {22                     f[i][j][0]=f[i+1][j-1][1]+f[i+1][j-1][0]+f[i+1][j][1]+f[i+1][j][0];23                 }else {24                     if (Bbas[i]==1) {25                         f[i][j][0]=f[i+1][j][1]+f[i+1][j][0]+f[i+1][j-1][0];26                         f[i][j][1]=f[i+1][j-1][1];    27                     }28                     if (Bbas[i]==0) {29                         f[i][j][0]=f[i+1][j][0]+f[i+1][j-1][0];30                         f[i][j][1]=f[i+1][j][1];31                     }    32                 }33             }34     }35     return f[1][k][0]+f[1][k][1];36 }37 int main(){38     cin>>x>>y>>k>>b;39     cout<<solve(y)-solve(x-1)<<endl;40     return 0;41 }

 

URAL1057 Amount of Degrees


联系
我们