秋招突击——6/28、6.29——复习{数位DP——度的数量}——新作{}

引言

• 头一次产生了那么强烈的动摇，对于未来没有任何的感觉的，不知道将会往哪里走，不知道怎么办。可能还是因为实习吧，再加上最近复习也没有什么进展，并不知道该怎么办，投的提前批基本上没什么回应，投的实习基本上都挂了。
• 在加上不在学校，没有办法和同学一块共享信息，一个人总是觉得有点孤零零的，难受，并且是忧郁的。
• 想那么多也没用，还是得继续复习。按照我的计划来。
• 上午出去有事，基本上没有刷算法，下午才开始刷算法。

复习

数位DP——度的数量

• 这一类题型之前基本上都没有做过，现在得好好补充一下，感觉听名字和状态压缩DP很像。

注意

• X和Y是区间长度，是INT类型的数字的上限，并且只能是正数
• 左右区间的都是闭合的，所以临界条件是两边相等，仅仅只有一个数字。

个人实现

• 首先，这里得先解决一个数字，才能解决所有的数字，所以得先专注于解决一个数字的判定。
• 这里是B的整数次幂，所以可以想成若干进制去思考，之前应该做过类似的出发是一个思路，肯定是能够先用高次幂的结果进行表示，然后再用低次幂的结果进行表示。然后在判定这个数字能否用一个较低位进行表示，这道题就算是结束了。

#include <iostream>
#include <vector>using namespace std;int x,y,k,b;
vector<int> exp;int main(){cin>>x>>y;cin>>k>>b;// 保存b的不同次幂的中间结果int res = 0;int i=1;exp.push_back(1);for ( i = b; i <= y ; i *= b)exp.push_back(i);for (int i = x; i <= y; ++i) {// 判断每一个数字是否能够使用对应的数字进行保存int cnt = k,temp = i;for (int j = exp.size() - 1; j >= 0 ; j --) {if (exp[j] <= temp){temp -= exp[j];cnt --;if (cnt >= 0 ){if (cnt == 0 && temp == 0)res ++;}elsebreak;}}}cout<<res;
}

实验结果如下

• 我的时间复杂度太高了，遍历所有的数字，然后在遍历每一个数字，看看能否出现对应的结果。相当于使（y - x） * k相当远的平方的运算时间复杂度。
  

参考实现

• 这里应该是使用了数位DP，之前并没有学过。

数位DP的相关技巧

• 区间转成边界相减问题：
  • 计算的区间【X，Y】中所有符合条件的数字，使用1到Y的所有符合条件的数字的数量，减去1到X中所有符合条件的数字的数量。【X，Y】 = f(Y) - f(X - 1)
• 从树的角度去考虑数位DP问题
  • 对于每一个数字的位数，只有两种情况，就是加入对应的分支以及不加入对应的分支等。

这里完全跳过了，看不懂，大约花了差不多一个小时，视频讲解有问题在加上题目的难度比较大，以后调整自己的复习思路，不在学习这种难度较高的算法题，主要还是刷对应的笔试题库

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 35;int l, r, k, b;
int a[N], al;
int f[N][N];int dp(int pos, int st, int op) //op: 1=,0<
{//枚举到最后一位数位，是否恰有k个不同的1（也是递归的终止条件）if (!pos) return st == k;//记忆化搜索，前提是不贴着上界（可以枚举满这一位所有的数字）if (!op && ~f[pos][st]) return f[pos][st];//01数位dp，贴着上界时，本轮能枚举的最大数就是上界数位的数字和1之间的最小值int res = 0, maxx = op ? min(a[pos], 1) : 1;for (int i = 0; i <= maxx; i ++ ){if (st + i > k) continue;res += dp(pos - 1, st + i, op && i == a[pos]);}return op ? res : f[pos][st] = res;
}
int calc(int x)
{al = 0; memset(f, -1, sizeof f);        //模板的必要初始化步骤while (x) a[ ++ al] = x % b, x /= b;  //把x按照进制分解到数组中return dp(al, 0, 1);
}
int main()
{cin >> l >> r >> k >> b;cout << calc(r) - calc(l - 1) << endl;return 0;
}

作者：一只野生彩色铅笔
链接：https://www.acwing.com/solution/content/66855/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

• 明天朋友来家里做客，忙完这一阵之后，就闭门谢客，专心好好准备秋招。马上第一批就开始了，但是我的项目还是没有准备好，进度太慢了，不行的。

• 我就在想，我真的有必要刷这么多算法进阶题目吗？今天的数位DP好难呀，感觉要花一上午，不如多花点时间去做热搜题目的一百道题。感觉到此为止了，不想再花时间去做这写题目了，数位DP太难了，根本就不会做。讲的有问题。

• 不想浪费时间了，单纯的针对一百热题吧，不在刷什么难题了，只能用题库堆起来，然后如果有不会的题目，再去看他的讲解，不能在这样往下跟了，然后每天上午的题目，就是单纯复习现在已经学到的相关算法了。 我是找工作的，不是面对算法竞赛的。

• 大概看了一下，就课程安排来说，虽然刷的是leetcode，但是还是会提到对应的题型进行讲解，所以转变以下自己的思路，不然这样化的时间实在太多了，完全没有必要。

• 而且我大概看了一下，基本上我在面试中遇到的问题，在这里基本上都能遇见，在腾讯面试中遇见的使用LRU，然后华为面试中遇见的三数之和等等。还是调整一下重点，重点围绕以下两个课题，分别是

  • leetcode热题100道
  • 面试经典150道

• 差不多一天三到四道题，差不多一个月刷一遍，还能回顾一遍。不要浪费时间。