最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

环球热点！AcWing1081. 度的数量

来源：博客园

题目描述

求给定区间 \([X,Y]\) 中满足下列条件的整数个数：这个数恰好等于 \(K\) 个互不相等的 \(B\) 的整数次幂之和。

例如，设 \(X = 15, Y = 20, K = 2, B = 2\)，则有且仅有下列三个数满足题意：

\(17 = 2^4 + 2^0\)\(18 = 2^4 + 2^1\)\(20 = 2^4 + 2^2\)


(相关资料图)

题意剖析

\(\qquad\) 我们把原本的数拆成一个与 \(B\) 有关的多项式，系数最高只能是 \(1\)（这是因为要求互不相同），会呈现这样的情况：

\[\qquad\large x = a_{n}B^n+a_{n-1}B^{n-1}+a_{n-2}B^{n-2}.....+a_{2}B^{2} + a_{1}B^{1}+a_{0}B^{0}\]

\(\qquad\)如果此时我们把系数数列单独提出来(\(\forall x\in a,\ x\in[0,1]\))，会呈现下面的这种情况：

\[\large 010101001001010010001010001010\]

那么只要在系数数列中有 \(k\) 个 \(1\) 就说明这个数符合题意。

因此题目转化成：当一个序列对应的B进制数在区间内时，中选出K个1的方案有多少种

解题思路

\(\qquad\) 这种统计关于数字位的题目就采用数位dp，对于区间的方案数可以很自然转化成前缀方案数。

\(\qquad\)问题就是如何进行数位DP\(\qquad 1.\)首先要把一个数的每一位分解出来，这一步比较简单。

while (x) a[ ++ len] = x % b, x /= b;

\(\qquad 2.\)从最高位开始 \(DP\)

状态表示

\[f[i][j]表示在再第n\sim i位填数，且已经填入了j个1的方案数\]

状态边界

\[f[0][k] = 1\]

状态转移

\(\qquad\) 我比较菜，这里就用记忆化搜索了

搜索参数：\(dfs(p, cnt, limit)\)

limit的转移

\(\qquad\) \(limit\) 表示的是前面填的数是否和区间右端点对应数相等，当 \(limit=0\) 代表 这个位置上可以填所有数，因为上一个数并未着区间右端点的这位上的最高，所以不管这位填谁，都不超出区间。相反，如果 \(limit = 1\)，那么我们只能填\(0\sim a[p]\)的数（\(p\)是当前搜索的位）。

\(\qquad\)所以我们可以对 \(limit\) 的转移做以下分析

\(\qquad 1.\)当\(limit = 1\) 且 填的数 \(i = up\), 的时候，\(limit=1\)\(\qquad 2.\)当\(limit = 1\) 且 填的数 \(i\neq up\) 的时候，\(limit = 0\)\(\qquad 3.\)当\(limit = 0\)时，不论如何，\(limit\) 只能变成 \(0\)

\(\qquad\)得到结论：limit转移到limit&&(i==up)

cnt的转移

\(\qquad\)我们的\(cnt\)可以加的时候，只有填入的数 \(i == 1\)才可以转移，这个简单，不再赘述

p的转移

\(\qquad\)从最高位开始，每次枚举上一位，这样每次 \(p-1\)

所以将上面三者结合起来，可以得到下面的代码

int dp(int p, int cnt, int limit) {    int &v = f[p][cnt]; //记忆化    if (!p) return cnt == k; //搜索完毕判断方案合法    if (!limit && ~v) return v; // 记忆化    int up = limit ? a[p] : b - 1, res = 0; // limit的限制填数上界    for (int i = 0; i <= min(up, 1); i ++ ) //最多只能填到1    {        if (i == 1 && cnt == k) break ; //k个用完了，退出        int l = limit & (i == up); // limit的转移        res += dp(p - 1, cnt + (i == 1), l); // 统计子节点送上来的信息    }    return v = res; // 返回+记忆化}

完整代码

#include #include #include #include using namespace std;const int N = 35;int f[N][N], k, b, l, r;int a[N << 2], al;int dp(int p, int cnt, int limit) {    int &v = f[p][cnt];    if (!p) return cnt == k;    if (!limit && ~v) return v;    int up = limit ? a[p] : b - 1, res = 0;    for (int i = 0; i <= min(up, 1); i ++ )     {        if (i == 1 && cnt == k) break ;        int l = limit & (i == up);        res += dp(p - 1, cnt + (i == 1), l);    }    return v = res;}int calc(int x) {    len = 0;    memset(f, -1, sizeof f);    while (x) a[ ++ len] = x % b, x /= b;    return dp(len, 0, 1);}int main() {    scanf("%d%d%d%d", &l, &r, &k, &b);    printf("%d\n", calc(r) - calc(l - 1));    return 0;}

关键词： 结合起来 这样的情况 比较简单