修补骑士
修补骑士
全部文章
分类
题解(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
首页
上一页
1
2
下一页
末页