题意理解
数字n
在B进制
下是不是有K个1
思路过程
-
把
数字n
进行B进制
分解 存入到一维向量nums
-
高位到低位
枚举每一位分类讨论
统计相关信息 维护结果数
和右边分支
的前缀信息
-
当前位
i位
的数字为x
-
x = 0
i位这里只能取0,跳过该位
,直接讨论i-1位即可 -
x = 1
- i = 0 后面
i - 1位
可以用组合数计算f[i-1][k-last]
- i = 1 后面i - 1位只能取在小于题目所给数的的情况下取值 不能用组合数直接计算
- i = 0 后面
-
x > 1
- i = 0 后面
i - 1位
可以用组合数计算f[i-1][k-last]
- i = 1 后面
i - 1位
可以用组合数计算f[i-1][k-last -1]
- i = 0 后面
-
所以对
x > 0
的情况 ,i取0
直接计算,i取1
还得分x = 1
还是x >1
来分别计算 -
最近记得加上
右半边
的值
-
收获
- 递推
求组合数
- 数位dp的
模板
- 特殊情况判断
取每一位
模和除法来帮忙- 分类讨论 每一位上的取值大小所对应的方案数
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 35;
int f[N][N];
int K, B;
// 组合计数初始化
void init() // 从 i个数中选j个数的方案
{
for(int i = 0; i < N; i++)
for(int j = 0; j <= i; j++)
if(!j) f[i][j] = 1;
else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}
int dp(int n)
{
if (!n) return 0;
vector<int> nums;
while(n) nums.push_back(n % B), n /= B; // B进制下把每一位抠出来 低 - > 高
int res = 0;
int last = 0; // 右边信息的前缀的信息 此题为 前面有多少个1
for(int i = nums.size() - 1; i >= 0; i --) // 从高位开始枚举 并分类讨论
{
int x = nums[i];
// 左边的分支
if(x) // 讨论 第i位的取值情况
{
// 第i位 取0
res += f[i][K - last];
// 第i位 取1
if(x > 1)
{
if(K - last -1 >= 0) res += f[i][K - last -1];
break;
}
else
{
last ++;
if(last > K) break;
}
}
//右边的分支 最后一位
if(!i && last == K) res ++;
}
return res;
}
int main()
{
init();
int l ,r;
cin >> l >> r >> K >> B;
cout << dp(r) - dp(l - 1) << endl;
return 0;
}
// 学习阶段 思路 -> 可拓展的代码 -> 熟练的程度(AC SABER)
hxd, 这解析老清楚了
还好有题解记录,两个月过去了,自己看了好一会才明白TT