秋招突击——6/28、6.29——复习{数位DP——度的数量}——新作{}
文章目录
- 引言
- 复习
- 数位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道
-
差不多一天三到四道题,差不多一个月刷一遍,还能回顾一遍。不要浪费时间。
相关文章:
秋招突击——6/28、6.29——复习{数位DP——度的数量}——新作{}
文章目录 引言复习数位DP——度的数量个人实现参考实现 总结 引言 头一次产生了那么强烈的动摇,对于未来没有任何的感觉的,不知道将会往哪里走,不知道怎么办。可能还是因为实习吧,再加上最近复习也没有什么进展,并不知…...
Spring Boot中使用Thymeleaf进行页面渲染
Spring Boot中使用Thymeleaf进行页面渲染 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们将探讨如何在Spring Boot应用中使用Thymeleaf模板引擎进行页面…...
恢复策略(下)-事务故障后的数据库恢复、系统故障后的数据库恢复(检查点技术)、介质故障后的数据库恢复
一、数据库恢复-事务故障 系统通过对事物进行UNDO操作和REDO操作可实现故障后的数据库状态恢复 1、对于发生事务故障后的数据库恢复 恢复机制在不影响其他事务运行的情况下,强行回滚夭折事务,对该事务进行UNDO操作,来撤销该事务已对数据库…...
如何知道docker谁占用的显卡的显存?
文章目录 python环境安装nvidia-htop查看pid加一个追踪总结一下【找到容器创建时间】使用说明示例 再总结一下【用PID找到容器创建时间,从而找到谁创建的】使用说明示例 python环境安装nvidia-htop nvidia-htop是一个看详细的工具。 pip3 install nvidia-htop查看…...
wps linux node.js 加载项开发,和离线部署方案
环境准备 windwos 安装node.js 安装VSCode 安装wps linux 安装node.js 安装VSCode 安装wps 通过npm 安装wpsjs SDK 使用npm安装wpsjs npm install -g wpsjs 创建一个项目 wpsjs create WPS-Addin-PPT 创建项目会让你选择2个东西: 1:选择你的文…...
红队内网攻防渗透:内网渗透之内网对抗:横向移动篇Kerberos委派安全非约束系约束系RBCD资源系Spooler利用
红队内网攻防渗透 1. 内网横向移动1.1 委派安全知识点1.1.1 域委派分类1.1.2 非约束委派1.1.2.1 利用场景1.1.2.2 复现配置:1.1.2.3 利用思路1:诱使域管理员访问机器1.1.2.3.1 利用过程:主动通讯1.1.2.3.2 利用过程:钓鱼1.1.2.4 利用思路2:强制结合打印机漏洞1.1.2.5 利用…...
nginx上传文件限制
默认限制 Nginx 限制文件大小可以通过 client_max_body_size 指令来设置,该指令通常在 http、server 或 location 块中设置,如果不设置,默认上传大小为1M。 修改上传文件限制 要修改Nginx的文件上传大小限制,你需要编辑Nginx的配…...
76. 最小覆盖子串(困难)
76. 最小覆盖子串 1. 题目描述2.详细题解3.代码实现3.1 Python3.2 Java 1. 题目描述 题目中转:76. 最小覆盖子串 2.详细题解 在s中寻找一个最短的子串,使之包含t中的所有字符,t中可能存在多个相同字符,寻找的子串也应至少含有…...
K8S 集群节点扩容
环境说明: 主机名IP地址CPU/内存角色K8S版本Docker版本k8s231192.168.99.2312C4Gmaster1.23.1720.10.24k8s232192.168.99.2322C4Gwoker1.23.1720.10.24k8s233(需上线)192.168.99.2332C4Gwoker1.23.1720.10.24 当现有集群中的节点资源不够用&…...
AI大模型技术在音乐创造的应用前景
大模型技术在音乐创作领域具有广阔的应用前景,可以为音乐家、作曲家和音乐爱好者提供以下方面的帮助。北京木奇移动技术有限公司,专业的软件外包开发公司,欢迎交流合作。 音乐创作辅助:大模型可以帮助音乐家和作曲家生成旋律、和声…...
Linux多进程和多线程(一)-进程的概念和创建
进程 进程的概念进程的特点如下进程和程序的区别LINUX进程管理 getpid()getppid() 进程的地址空间虚拟地址和物理地址进程状态管理进程相关命令 ps toppstreekill 进程的创建 并发和并行fork() 父子进程执行不同的任务创建多个进程 进程的退出 exit()和_exit() exit()函数让当…...
熊猫烧香是什么?
熊猫烧香(Worm.WhBoy.cw)是一种由李俊制作的电脑病毒,于2006年底至2007年初在互联网上大规模爆发。这个病毒因其感染后的系统可执行文件图标会变成熊猫举着三根香的模样而得名。熊猫烧香病毒具有自动传播、自动感染硬盘的能力,以及…...
使用Vue3和Tailwind CSS快速搭建响应式布局
### 第一部分:初始化Vue3项目并安装Tailwind CSS 首先,在你的开发环境中打开终端,然后通过Vue CLI来创建一个新的Vue3项目。输入如下命令: vue create my-vue-app 按照提示选择Vue3的相关选项,创建完毕后࿰…...
J019_选择排序
一、排序算法 排序过程和排序原理如下图所示: 二、代码实现 package com.itheima.sort;import java.util.Arrays;public class SelectSort {public static void main(String[] args) {int[] arr {5, 4, 3, 1, 2};//选择排序for (int i 0; i < arr.length - 1…...
【linux】vim的使用
目录 一、Vim的基本模式 二、Vim的常见命令 三、Vim的高级用法 四、Vim的进阶使用技巧 在Linux系统中,Vim是一款功能强大的文本编辑器,特别适用于程序员的代码编辑和修改。以下是Vim的详细使用教程,包括其基本模式、常见命令和高级用法。…...
【工具测评】ONLYOFFICE8.1版本桌面编辑器测评:好用!
随着远程工作的普及和数字化办公的发展,越来越多的人开始寻找功能强大、易于使用的办公软件。在这个背景下,ONLYOFFICE 8.1应运而生,成为许多用户的新选择。ONLYOFFICE 8.1是一款办公套件软件,提供文档处理、电子表格和幻灯片制作…...
核方法总结(四)——高斯过程回归学习笔记
一、定义 基于核方法的线性回归模型和传统线性回归一样,可以用未知数据进行预测,但不能确定 预测的可信度。在参考书第二章中可知,基于贝叶斯方法可以实现对未知数据依概率预测,进而可得到预测的可信度。这一方法中,通…...
【Python3的内置函数和使用方法】
目录 Python 特点 Python 中文编码 Python 变量类型 Python列表 Python 元组 元组是另一个数据类型,类似于 List(列表) Python 字典 Python数据类型转换 Python 运算符 Python算术运算符 Python比较运算符 Python赋值运算符 Pyt…...
递推算法计算信号特征
在线算法(在线计算或递推计算)能够在不存储全部数据的情况下逐步更新信号的特征信息,非常适合资源受限的单片机应用场景。 用途:单片机边采集ADC边计算,最终将采集的信号特征计算结果…...
spring-boot-configuration-processor注释处理器
开源项目SDK:https://github.com/mingyang66/spring-parent 个人文档:https://mingyang66.github.io/raccoon-docs/#/ spring-boot-configuration-processor是springboot提供的一个注释处理器(annotation processor),它用于在编译…...
完整实战指南:使用N_m3u8DL-RE高效解决流媒体下载难题
完整实战指南:使用N_m3u8DL-RE高效解决流媒体下载难题 【免费下载链接】N_m3u8DL-RE Cross-Platform, modern and powerful stream downloader for MPD/M3U8/ISM. English/简体中文/繁體中文. 项目地址: https://gitcode.com/GitHub_Trending/nm3/N_m3u8DL-RE …...
别再点‘忽略’了!开机弹出Visual C++ Runtime Library错误的终极排查指南(附Adobe软件关联排查)
Visual C Runtime Library错误:从崩溃到根治的全链路解决方案 每次开机时那个刺眼的Visual C Runtime Library错误弹窗,就像一位不请自来的访客,固执地打断你的工作节奏。对于依赖Adobe Creative Cloud或达芬奇等创意工具的专业人士来说&…...
CircuitPython状态灯、安全模式与文件系统故障排查实战指南
1. 项目概述与核心价值 如果你正在用CircuitPython做项目,无论是物联网传感器节点、智能穿戴设备还是互动艺术装置,大概率都遇到过这样的瞬间:板子上的RGB状态灯突然开始闪烁诡异的颜色,或者电脑上那个熟悉的 CIRCUITPY U盘图标…...
Claude-Code-KnowCraft:轻量级代码知识库构建与智能问答实践
1. 项目概述与核心价值最近在跟几个做AI应用开发的朋友聊天,大家普遍有个痛点:想把Claude这类大语言模型(LLM)的能力深度集成到自己的代码库分析工具里,但发现现有的方案要么太重,要么太浅。太重的是指那些…...
数据流编排与异步任务调度中间件kelivo部署与实战指南
1. 项目概述与核心价值最近在折腾一个挺有意思的项目,叫“Chevey339/kelivo”。乍一看这个标题,可能有点摸不着头脑,它不像那些直接告诉你“XX管理系统”或“XX工具库”的项目名那么直白。但恰恰是这种看似神秘的命名,背后往往隐藏…...
数据分析师能力展示:从项目构建到报告呈现的完整指南
1. 项目概述:一个数据分析师的能力展示平台最近在GitHub上看到一个挺有意思的项目,叫“dataanalyst-showcase”。光看名字,你可能会觉得这又是一个数据科学项目合集,但点进去仔细研究后,我发现它的定位非常精准——它不…...
无代码物联网实战:基于ESP32与WipperSnapper的泳池水温监测方案
1. 项目概述:告别繁琐编程,用无代码方案守护泳池水温又到了打理泳池的季节,除了常规的清洁和化学平衡,水温其实是个挺关键的指标。水温不仅影响游泳的舒适度,也关系到泳池加热设备的能耗和泳池化学品的反应速率。以前想…...
基于Vanilla JS与IndexedDB构建本地化Markdown笔记工具
1. 项目概述:从零开始构建一个轻量级笔记工具最近在整理个人知识库时,发现市面上的笔记软件要么功能过于臃肿,要么云端同步存在隐私顾虑,要么就是定制化程度不够。作为一个有十多年开发经验的从业者,我决定自己动手&am…...
Python Pydantic介绍(数据校验、自动类型转换、结构化数据建模、序列化JSON、配置管理)pydantic-settings、核心BaseModel、字段约束Field()、FastAPI
文章目录Python 数据校验神器:Pydantic 完全指南一、什么是 Pydantic二、Pydantic 能解决什么问题1)数据校验(Validation)2)自动类型转换(Parsing)3)结构化数据建模4)序列…...
017、Docker在TinyML开发中的应用
017 Docker在TinyML开发中的应用 从一次“环境地狱”说起 上个月帮团队调一个STM32上的TinyML推理延迟问题,模型是MobileNetV2量化版,在开发板上跑得好好的,换到同事的Ubuntu 20.04机器上编译,死活链接不上CMSIS-NN库。折腾半天发现他系统里默认的arm-none-eabi-gcc版本是…...
