「一本通 5.3 例 1」Amount of Degrees
点击查看代码
// 先转化为前缀和
// 从头到尾枚举每一位: 这一位的贡献为前面的位都相同, 这一位比原来更小, 后面的位任意的方案书
#include <vector>
#include <stdio.h>
#include <string.h>
int k, b;
int C[35][35]; // 组合数
int dp(int n) {
if(!n) return 0;
std::vector<int> num;
while(n) num.push_back(n % b), n /= b;
n = num.size();
int res = 0, last = 0; // res 为答案, last 为当前 1 的个数
for(int i = n - 1; i >= 0; i --) {
int x = num[i];
if(x) { // 这一位非0: 可以选择
res += C[i][k - last]; // 这一位填0的情况(假设前面若干位都是)
if(x > 1) { // 这一位可以尝试填1
if(k - last - 1 >= 0) res += C[i][k - last - 1];
break; // 由于只能填0或1,则
} else // 只能选0: 如果1过多,跳过
if(++ last > k) break;
}
if(!i && last == k) res ++; // 最后一位的贡献
}
return res;
}
int main() {
int l, r; scanf("%d%d%d%d", &l, &r, &k, &b);
for(int i = 0; i <= 34; i ++) {
C[i][0] = 1;
for(int j = 1; j <= i; j ++)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
printf("%d\n", dp(r) - dp(l - 1));
return 0;
}
点击查看代码
#include <vector>
#include <stdio.h>
#include <string.h>
int f[15][10]; // 共有 i 位, 最高位为 j 的答案
int dp(int n) {
if (!n)
return 1; // 0满足条件
std::vector<int> num;
while (n)
num.push_back(n % 10), n /= 10;
int res = 0, last = 0; // last 为上一位
for (int i = num.size() - 1; i >= 0; i --) {
int x = num[i];
for (int j = last; j < x; j ++)
res += f[i + 1][j]; // 第i位填 j, 后面的随便填
if (x < last)
break; // 不能够保留
last = x;
if (!i)
res ++; // 0满足条件
}
return res;
}
int main() {
for (int i = 0; i < 10; i ++)
f[1][i] = 1;
for (int i = 2; i < 15; i ++)
for (int j = 0; j < 10; j ++)
for (int k = j; k < 10; k ++)
f[i][j] += f[i - 1][k];
int l, r;
while (scanf("%d%d", &l, &r) == 2)
printf("%d\n", dp(r) - dp(l - 1));
return 0;
}
点击查看代码
#include <math.h>
#include <vector>
#include <stdio.h>
#include <string.h>
int f[15][10]; // 总共 i 位数, 首位为 j 的方案数
int dp(int n) {
if (!n)
return 0; // 0不算
std::vector<int> num;
while (n)
num.push_back(n % 10), n /= 10;
int res = 0, last = -2;
for (int i = num.size() - 1; i >= 0; i --) {
int x = num[i];
for (int j = (i == num.size() - 1); j < x; j ++) // 首位不能是0
if (abs(j - last) >= 2)
res += f[i + 1][j]; // 可以选的位
if (abs(x - last) >= 2)
last = x;
else
break; // 填不下去了
if (!i)
res ++; // 0结尾
}
for (int i = 1; i < (int)num.size(); i ++)
for (int j = 1; j < 10; j ++)
res += f[i][j]; // 位数不足的
return res;
}
int main() {
for (int i = 0; i < 10; i ++)
f[1][i] = 1;
for (int i = 2; i < 15; i ++)
for (int j = 0; j < 10; j ++)
for (int k = 0; k < 10; k ++)
if (abs(j - k) >= 2)
f[i][j] += f[i - 1][k];
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", dp(r) - dp(l - 1));
return 0;
}