做网站需服务器吗,帮传销组织做网站,中国免费素材网站,网站ip查询站长工具文章目录 引言复习数位DP——度的数量个人实现参考实现 总结 引言
头一次产生了那么强烈的动摇#xff0c;对于未来没有任何的感觉的#xff0c;不知道将会往哪里走#xff0c;不知道怎么办。可能还是因为实习吧#xff0c;再加上最近复习也没有什么进展#xff0c;并不知… 文章目录 引言复习数位DP——度的数量个人实现参考实现 总结 引言
头一次产生了那么强烈的动摇对于未来没有任何的感觉的不知道将会往哪里走不知道怎么办。可能还是因为实习吧再加上最近复习也没有什么进展并不知道该怎么办投的提前批基本上没什么回应投的实习基本上都挂了。在加上不在学校没有办法和同学一块共享信息一个人总是觉得有点孤零零的难受并且是忧郁的。想那么多也没用还是得继续复习。按照我的计划来。上午出去有事基本上没有刷算法下午才开始刷算法。
复习
数位DP——度的数量 这一类题型之前基本上都没有做过现在得好好补充一下感觉听名字和状态压缩DP很像。
注意
X和Y是区间长度是INT类型的数字的上限并且只能是正数左右区间的都是闭合的所以临界条件是两边相等仅仅只有一个数字。
个人实现
首先这里得先解决一个数字才能解决所有的数字所以得先专注于解决一个数字的判定。这里是B的整数次幂所以可以想成若干进制去思考之前应该做过类似的出发是一个思路肯定是能够先用高次幂的结果进行表示然后再用低次幂的结果进行表示。然后在判定这个数字能否用一个较低位进行表示这道题就算是结束了。
#include iostream
#include vectorusing namespace std;int x,y,k,b;
vectorint exp;int main(){cinxy;cinkb;// 保存b的不同次幂的中间结果int res 0;int i1;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;}}}coutres;
}实验结果如下
我的时间复杂度太高了遍历所有的数字然后在遍历每一个数字看看能否出现对应的结果。相当于使y - x * k相当远的平方的运算时间复杂度。
参考实现
这里应该是使用了数位DP之前并没有学过。
数位DP的相关技巧
区间转成边界相减问题 计算的区间【XY】中所有符合条件的数字使用1到Y的所有符合条件的数字的数量减去1到X中所有符合条件的数字的数量。【XY】 f(Y) - f(X - 1) 从树的角度去考虑数位DP问题 对于每一个数字的位数只有两种情况就是加入对应的分支以及不加入对应的分支等。
这里完全跳过了看不懂大约花了差不多一个小时视频讲解有问题在加上题目的难度比较大以后调整自己的复习思路不在学习这种难度较高的算法题主要还是刷对应的笔试题库
#include iostream
#include cstring
#include algorithmusing 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道 差不多一天三到四道题差不多一个月刷一遍还能回顾一遍。不要浪费时间。
