修补骑士

分类

题解(13)

/ 注册

全部文章（共13篇）

题解 | #K-th Number#

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

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

2025-06-03

1 14

题解 | #合并回文子串#

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

C++ 数组动态规划数学

2025-06-01

1 10

题解 | #Butterfly#

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

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

2025-04-26

1 29

题解 | #走出迷宫#

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

C++ 深度优先搜索

2025-04-23

1 22

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

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

C++ 深度优先搜索

2025-04-23

1 20

题解 | #Music Problem#

题目名称：音乐问题问题描述：强迫症患者HH只有在歌曲结束时处于整点时间（即分钟和秒均为0）才能停止听歌他初始时间为12:00:00，且一旦开始听歌就只能通过满足上述条件的方式停止给定若干首歌曲的时长，请判断是否存在一种选歌方式（每首歌最多选一次），使得HH能在某个整点时间停止听歌。输入描述...

C++ 动态规划设计

2025-04-21

1 36

题解 | #「木」迷雾森林#

哎呦我操帕秋莉怎么这么坏啊这题直接浪费了我大好的一个上午加中午的学习时间，我现在正在一边啃着我最爱的腰果一边控诉这道题：思路上很明显，虽然说这题一股子BFS味，但是为了求所有方式，复杂度上DFS又不合适，我们自然而然想到了DP。“情况”也很明显——不同位置走到的方式，同时只能向上向右走又保证了有...

C++ 动态规划

2025-04-18

1 24

题解 | #小A买彩票#

哇，这也是DP？修补骑士一开始当背包来想：我们要写4个数组来DP吗？每一个都记录可行的最大次数吗？但他很快发现——这个主要是可以积累，你不知道他上一个可行究竟剩下来多少！看了看题解：我们要维护“成功数量”与“剩余数量”，只写一维不好维护，我们就拿不到每种成功情况下对应的剩余，就没法持续DP运算。...

C++ 动态规划

2025-04-18

1 30

题解 | #CSL分苹果#

非常板子的DP背包问题，不过板子也有板子的好处，可以让修补骑士快速上手熟悉某个知识点的写法在这里就说两个我犯的错吧 1：我们都知道，对于每一个元素选或者不选，我们是从后向前的（防止多选），但是我们写循环要写成for(int y = allwei/2;y >= weight[r];y--)而不...

C++

2025-04-17

1 18

题解 | #装备合成#

修补骑士一开始又想写DP了，这是个什么完全二维背包DP，看着都抽象。并且可能会有TLE，MLE的问题但是，这道题的思路让我想起了NC15446（同样也被我当成了背包）单次判断的核心在于：我们只关心于是否存在合规的情况，虽然这个情况很可能不是最终答案但至少说明了存在就行，我们继续二分下去，最后的...

C++ 二分查找

2025-04-17

1 25