You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

72 lines
3.9 KiB

This file contains invisible Unicode characters!

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
const int N = 32; // 输入的数据范围2^31-1,也就是整数上界。2进制是最小的进制32也够了
int l, r; // 数位DP的区间范围
int k, b; // k:个进制位为1,b进制
int a[N], al; // 用来分解b进制的数组
int f[N][N]; // f[i][j] i:枚举到的位置 j:已经计算完1的个数,这里需要一点DP的状态描述的思想只有一维记录到哪了是无法描述整个当时场景的
/**
*
* @param u 当前枚举到的数位
* @param st 数字1出现的次数
* @param op 是否贴上界
* @return 在当前情况下,它 后续 符合条件的一共有多少个数
*/
int dfs(int u, int st, bool op) {
// 到最后一位数位是否恰好有k个不同的1,是:贡献价值+1贡献价值+0
if (u == 0) return st == k;
if (op == 0 && ~f[u][st]) return f[u][st]; // 不贴上界,并且计算过,返回结果
/*
① 不贴着上界,可以将此区间算满,缓存起来,不用重复计算
② 贴上界,每次重新计算
本题要求:
(1)如果op = 1, 贴上界
如果a[u]=0,那么up最大是0,否则,up最大是1,简写成min(a[u],1)
(2)如果op = 0, 不贴上界,可以选择的范围[0,1],up最大是1
*/
int ans = 0;
int up = op ? min(a[u], 1) : 1; // up就是你的极限本题这句是一个精华点
for (int i = 0; i <= up; i++) { // 枚举上限之内的数字(其实也只有0和1有机会这还要看up的取值。up=0,跑一次循环up=1,跑两次循环)
// 如果i==0,则st+i=st,st不会变大也不会超过k,此句无影响后面的代码执行。
// 如果i==1,则表示多选择了一个是1的数位st+1,有可能已经超过了k的限制再向后跑深搜就没有了意义及时止损剪枝
if (st + i > k) continue; // 剪枝更健康
// u-1:继续向低一位进行前进
// st+i:1的个数变化情况如果i==0,则表示u这个数位没有选择数字1如果i==1则表示u这个数位选择了数字1不断的向后传递这个信息用于判断是不是符合条件的数字
// op && i == a[u] :此参数的含义是是否贴合上限
// op:原来是贴上界的 && i == a[u]: 当前位取值也是贴上界
// 那么,下面一位是继承前面的结果关系,也就是,它也在贴上界的情况下进行讨论
// ==的运算优先级 高于 && 所以先判断 i == a[u]是第一步,与 op 相 && 是第二步
ans += dfs(u - 1, st + i, op && i == a[u]);
}
// 只记录不受上限限制的个数,受上限限制的每次重新计算
// 为什么只记录不贴上界的结果,贴上界的为什么不能直接使用结果?
// 这是因为:如果第一位贴了上界,那么第二位也可能继续贴上界,导致后续的无法取完整,无法直接使用结果
if (!op) f[u][st] = ans;
/*这里对应上面的记忆化在一定条件下时记录保证一致性当然如果约束条件不需要考虑lead这里就是lead就完全不用考虑了*/
return ans;
}
// 采用类似于前缀和的思想所以需要封装成一个calc函数,计算两次,然后取差值
int calc(int x) {
al = 0; // 临时数组a初始化这里挺有意思把al=0就相当于全新初始化掉了a,不用采用memset(a,0,sizeof a);
while (x) a[++al] = x % b, x /= b; // 把x按照进制分解到数组中,下标从1开始
return dfs(al, 0, true); // 从最高位开始目前数字1出现了0次贴上界
}
int main() {
memset(f, -1, sizeof f); // 初始化
cin >> l >> r >> k >> b; // 边界k个数位是1b进制
// 前缀和
cout << calc(r) - calc(l - 1) << endl;
return 0;
}