修补骑士

分类

题解(18)

/ 注册

全部文章（共18篇）

题解 | #花店橱窗#

一个经典的板子dp题目，时间复杂度不高，可以使用经典dp形式我们定义dp[r][p]，就是第r个花朵放在第p个花瓶的美观度（有点类似背包），首先进行剪枝操作：由于每个花都要放，第i朵花只能放在第i个花瓶到第v - (f - i)个花瓶之间，这是为了预留足够的空间之后对于每一种dp[r][p]，我...

C++ 动态规划

2025-06-19

1 12

题解 | #石子合并#

非常经典的区间dp题啊，这种题的数据结构不大，可以从一些比如n3复杂的的方式入手对于状态转移方程，区间[a,b]与[x,y]合并，代价就是：两个区间之前合并到这一步所记录的代价+他们自己的代价。也就是说我们需要维护两个数组：dp与presum来分别记录路径代价与区间重量总和，对于每个大的区间，可以...

C++ 动态规划模拟

2025-06-19

1 16

题解 | #牛牛的战役#

读一遍就有思路了：贪心原则是：从大到小（排序也是贪心很重要的一环）的敌人战力，我们肯定可以解决的oier会变多，对于没一种敌人战力，我们要对可以处理的oier进行平均分配使得经验值被均分。修补骑士一开始想的是逐步减少之后选择最小者来不断+1模拟处理。不过这样存在两个问题。1：追踪过程难以维护，可能要...

C++ 数学贪心二分查找

2025-06-14

1 14

题解 | #牛牛的朋友#

贪心这种基本是靠猜猜的，思路要证明的话反而不好搞：对于这道题，我们要做的就是“收缩”整个区间，同时从样例可以看出可能有内部的元素变成了新的左边与右边，不能只跟踪原来的两个maxmin元素。主要是我老是在犹豫怎么才能拿到不同转移状态下的最右边/左边的元素，跟在写动态规划似的这里的贪心思路是：一定存在...

C++ 数组贪心数学

2025-06-09

1 18

题解 | #位数差#

区间问题用分治还是挺多的，由于i < j的限制，这里实际上是相当于求“顺序对”（也就是后面的数更大的一对数字，而且还要求这两个数字加起来比起左边那个进位），实际上使用线段树或者树状数组的方法本质上还是属于分治值，在这里不在赘述。这里重点说一下普通的分治方法对于这种区间题，我们会想什么前缀和，...

C++ 数组数学二分查找线段树树状数组

2025-06-09

1 19

题解 | #K-th Number#

这题是真的有点难度，主要在于他的时间复杂度卡的真的特别紧，属于是二分法，前缀和，尺取法，单位元素讨论齐上阵才能够AC，有一点出错了就会TLE，我们来慢慢看思路二分：实际上这个二分关系真的非常邪门，对于第K大的元素x，那说明他前面起码有k个元素是不小于x的，这就是二分关系（很神奇吧），具体成代码就是...

C++ 二分查找双指针数学滑动窗口枚举

2025-06-03

1 21

题解 | #合并回文子串#

这道题的思路很简单，就是普通的dp，甚至比起单个字符串判断最大子回文长度还要简单。但是在细节上有相当多的地方需要注意由于数据量是50所以说可以用一些时间复杂度比较神秘的dp方法，这里我们模仿普通单个字符串回文的求法，设一个四维dp数组，说明a的[l1,r1]区间与b的[l2,r2]区间组成的字符串...

C++ 数组动态规划数学

2025-06-01

1 22

题解 | #Butterfly#

修补骑士一看见题面就放弃的差不多了。这里主要是绝大多数人可能会惯性思维的认为是从中间开始，之后往四边扩展验证，明显实现起来太过麻烦并且时间复杂度过大，不过考虑构造的思路是没有错的对于每一个点，我们考虑积累三个元素：向上的延伸，向左上的延伸与向右上的延伸，对于一个方格（假设为右下角），我们先找到向上...

C++ 动态规划几何枚举图

2025-04-26

1 34

题解 | #走出迷宫#

感觉这题的话还是BFS有优势吧，太深的话那DFS就炸了。不过实际上实现差不多。核心在于我们走全图，如果没走出去那就是绝对走不到。在自己所有衍生情况走完之后自己就结束了，我们可以很轻松的使用一个flag记录，并且把它当做关键的判断与边界条件实现倒还是很简单很板子，很适合拿来当做练手熟悉DFS，这里就...

C++ 深度优先搜索

2025-04-23

1 28

题解 | #「金」点石成金#

修补骑士原本想修补一下自己的DFS，却发现这道题并非传统板子的DFS，主要是没有回溯成分我们首先发现是一串石头“选不选”的问题，有点类似于传统的背包问题（好像是可以的？不过我没有写出来），我们看到n上限不大，就考虑直接暴搜。对于DFS或者这种递归的方法，我们一定要记住：只关注于当前干什么，怎么实现...

C++ 深度优先搜索

2025-04-23

1 26