扶明の小站

读题 原题链接：LeetCode 306. 累加数 题目要求我们在找到一个长串的数的分割方案使得这个数满足分割得到的数组满足累加序列的性质，通过示例我们很容易理解其含义 需要注意两点： 数字不会以0开头（除数字0外） 数据可能会很大 解题思路 通过经验我们容易发现分割方案的题很容易与深度优先搜索（DFS | 回溯法）联系，但是这里的数据范围1 <= num.length <= 35着实让我捏了把汗，不考虑剪枝的复杂度为 2352^{35}235 远远超过我们能承受的范围 然后我们可以考虑一下累加序列有没有特别的性质可作为突破口，这时我们可以发现：对于一个合理的累加序列如果前两个数字确定那么整个序列也就可以通过这两个数推出 所以我们就可以只枚举前两个数然后检查后续的数字是否可能分割成满足累加序列的数字来判断整体是否满足累加序列的性质了 我们考虑特殊情况：如果我们枚举到一个数以0开头那么它只能是0，即当测试过数不能是0后就表示这样的分割方案是不合理的 关于数据可能过大的问题： 对于一个待分割的累加数我们可以发现只有当把这个数分割为三个部分时才会得到单个数数最大的情况，而 ...

题目描述 在一条数轴上有 N 家商店，它们的坐标分别为 A1∼ANA_1∼A_NA1​∼AN​。 现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。 为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。 原题链接：AcWing 104. 货仓选址 思路 假设我们现在已经将这些商店在数轴上排列好了位置并且根据他们的相对位置编好号 我们将 A1A_1A1​ 与 ANA_NAN​ 放在一起分析，要在数轴上选取一个点让这个点到 A1A_1A1​ 和 ANA_NAN​ 的距离之和最小，那么这个点一定是在 [A1, AN][A_1,\ A_N][A1​, AN​] 这段距离之间，并且可以是这个区间上的任意一个值 同样的我们将 A2A_2A2​ 与 AN−1A_{N-1}AN−1​ 放在一起分析，得到这个点必须在 [A2, AN−1][A_2,\ A_{N-1}][A2​, AN−1​] 这个区间内，以此类推 最终，我们可以找到这段距离上的中间点（中位数）若这时这个中间值是一个点即N为奇数，那么这个点就是 AN/2A_{N/2}AN/2​ ；若此时这个中间 ...

题目描述 农民约翰的N头奶牛（编号为1…N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。 奶牛们不是非常有创意，只提出了一个杂技表演： 叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。 奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。 这N头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度Si。 一头牛只撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。 您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。 原题链接：AcWing 125. 耍杂技的牛 备用链接：洛谷 P1842 USACO05NOV奶牛玩杂技 提高版：洛谷 P1080 NOIP2012 提高组 国王游戏 思路 假设存在两头相邻牛其重量和强壮度分别为分别是 wi, wi+1, si, si+1w_i,\ w_{i+1},\ s_i,\ s_{i+1}wi​, wi+1​, si​, si+1​ 则构建针对这两头牛位置交换的表格 牛 i 的危险值 牛 i+1 的危险值 ...

Servlet简介 servlet是JavaEE的规范（接口）之一， 也是JavaWeb的三大组件之一；三大组件分别是Servlet程序、Filter过滤器、Listener监听器。 Servlet是运行在服务器上的一个Java小程序，它可以接收客户端发送过来的请求，并相应数据给客户端。 实现Servlet程序 编写一个类去实现servlet接口 创建一个类然后implements Servlet并实现其方法（实际开发中不使用） 创建一个类然后extends HttpServlet去继承已经实现好的Servlet子类（实际使用） 实现service方法处理请求并响应数据 在web.xml中去配置servlet程序的访问地址 要在web.xml中配置两个标签servlet和servlet-mapping 123456789101112131415<!-- servlet标签给Tomcat配置Servlet程序 --><servlet> <!-- servlet-name标签：给Servlet程序其一个别名（一般设定为类名） - ...

Tomcat 目录解析 目录 作用 bin 专门存放tomcat服务器的可执行程序 conf 专门用来存放tomcat服务器的配置文件 lib 专门用于存放tomcat服务器的jar包（对JavaEE实现的规范） logs 专门用于存放tomcat服务器运行时输出的日志信息 temp 专门用于存放tomcat服务器运行时产生的临时数据 webapps 专门用于存放部署的Web工程 work 是Tomcat工作时的目录，用于存放tomcat运行时jsp翻译为Servlet的原码和Session钝化的目录 运行Tomcat 打开tomcat的解压目录然后找到 bin 目录下的 startup.bat 文件，打开即可。也可以在bin目录下打开命令行使用 catalina run 命令启动服务。同目录下的shutdown.bat 可以结束tomcat服务器。 tomcat守候在8080端口，所以只需要在浏览器中打开本机的 8080端口 即可查看tomcat是否已经启动（浏览器打开 http://localhost:8080 或者 http://127 ...

动态习题集 众所周知，动态规划问题的训练不但需要学习其精巧的思维还需要大量练习积累经验，才能较好地掌握这一方面的知识。所以这篇文章就当作记录一些我所收集到的经典的动态规划问题的习题集。 显然这个习题集的体系逐渐完善体量也越来越大，所以请善用目录。 本集初建于2022年1月1日将持续更新。 动态规划（Dynamic Programming， DP）是一种将原问题分解成结构相似规模更小的子问题的进行递推处理的求解复杂问题的有力算法。但是动态规划并不是指某一种特定解法的算法而是一种复杂问题简单化的思路，针对这种思路可以考察到的问题形式和种类非常丰富非常考验解题人的思维~ 动态规划问题的要素： 最优子结构：从子问题的最优解可以推出更大规模的问题的最优解的问题结构就满足最优子结构的特点，对于这样的问题你可以假定不必知道子问题具体是如何获得的，只需由已知的最优子解就可得到更大规模的最优解即子问题间相互独立 重叠子问题：从最小子问题递推（递归）地重复求解能得到最优解就一定要满足子问题与原问题只是规模上的差别在计算方法需要是一致的而不能在解决子问题的时候生成新的子问题，这样就能通过子问题的解重构出原 ...

哈希表/散列表 哈希函数 作用：把一个比较复杂的数据结构（特大整数、浮点数、字符串）映射到一个较固定的数据范围内，实现通过映射值(key)查找对应元素(value) 实现：一般情况下我们使用直接使用将键值模上一个较大的质数作为索引，也即取 f(x) = x mod Pf_{(x) \ =\ x\ mod\ P}f(x) = x mod P​​ ，很显然我们这样的处理是很容易导致键值的冲突发生的，所以我们需要设计冲突处理解决相应的问题。 冲突处理 拉链法（开散列法） 实现：整个哈希表的每个节点都维护了一个链表每次都将映射到该节点的对应值添加到链表中，查找时需要遍历整个节点链表，如果加入的节点数为 nnn 取模 PPP （即索引范围为 [0,P)\left[ 0,P\right)[0,P) ）这样插入和查找的期望复杂度就都是 OnPO_{\frac{n}{P}}OPn​​ 的（一般不做删除节点的操作，一般用标记代表删除） 核心代码： 12345678910111213141516const int N = 100003;int h[N], e[N], ne[N], idx;void in ...

堆 堆的分类： 操作\数据结构 配对堆 二叉堆 左偏树 二项堆 斐波那契堆 插入（insert） O(1)O_{(1)}O(1)​ O(log⁡n)O_{(\log_{n})}O(logn​)​ O(log⁡n)O_{(\log_{n})}O(logn​)​ O(1)O_{(1)}O(1)​ O(1)O_{(1)}O(1)​ 查询最小值（find-min） O(1)O_{(1)}O(1)​ O(1)O_{(1)}O(1)​ O(1)O_{(1)}O(1)​ O(log⁡n)O_{(\log_{n})}O(logn​)​ O(1)O_{(1)}O(1)​ 删除最小值（delete-min） O(log⁡n)O_{(\log_{n})}O(logn​)​ O(log⁡n)O_{(\log_{n})}O(logn​)​ O(log⁡n)O_{(\log_{n})}O(logn​)​ O(log⁡n)O_{(\log_{n})}O(logn​)​ O(log⁡n)O_{(\log_{n})}O(logn​)​ 合并 (merge) O(1)O_{(1)}O(1)​ ...

并查集 作用： 将两个集合合并 询问两个元素是否在一个集合当中 可以在近乎 O(1)O_{(1)}O(1)​ 的时间复杂度上完成以上的两个操作 基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号。每个节点存储它的父节点，用p[x] 来表示x的父节点（注意这里的树并不是二叉树） 判断树根节点：p[x] == x 求 x 的集合编号：while(p[x] != x) x = p[x] 合并两个集合：合并的方法就是保留一个根节点，将里一个作为根节点的子树，p[x] 是 x 的集合编号， p[y] 是 y 的集合编号，直接令 p[x] = y 优化之路径压缩：将一次搜索得到的路径上的所有节点的父节点都转化为根节点，这样在多次转化查找后就会实现树的高度近似为1 优化之按秩合并：并查集 - OI Wiki 注意：简单的并查集并不支持高效的集合的分离 （图片源自 OI-wiki) 核心代码： 12345678910//返回x的祖宗节点 + 路径优化int find(int x){ if(p[x] != x) p[x] = find(p[x]); retu ...

Trie树（字典树） 作用： 高效存储和查找字符串 实现：将字符串按序排列形成树状结构，查找时就可按照类似字典查找一样的顺序查找匹配字符串因此Trie树也被称为字典树或前缀树 构造链式存储结构存储树状的Trie树 这里使用了数组模拟链表的形式 使得插入操作更简单；需要考虑的是每个节点的分叉个数即每个节点的状态数来确定每个节点的下指针域的数量 插入时，按序查找如果匹配到结尾就在结尾节点标定匹配成功标记或者设置匹配节点数量加一，如遇到查找失效则自行建立下指针直至字符结尾并设置结尾匹配成功标记 查询时只需要根据是否在匹配到字符结尾的同时匹配到字典树的结尾标定或者是在匹配过程中发现下指针指向根节点代表匹配失败 （图片引用自OI-wiki） 核心代码： 1234567891011121314151617181920212223242526#include<iostream>using namespace std;const int N = 100010;int son[N][26], cnt[N], idx; //下标为0的点 既是根节点也是空节点void insert(cha ...