修补骑士

分类

题解(11)

/ 注册

全部文章（共11篇）

题解 | #Butterfly#

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

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

2025-04-26

1 21

题解 | #走出迷宫#

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

C++ 深度优先搜索

2025-04-23

1 16

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

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

C++ 深度优先搜索

2025-04-23

1 15

题解 | #Music Problem#

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

C++ 动态规划设计

2025-04-21

1 27

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

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

C++ 动态规划

2025-04-18

1 18

题解 | #小A买彩票#

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

C++ 动态规划

2025-04-18

1 25

题解 | #CSL分苹果#

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

C++

2025-04-17

1 14

题解 | #装备合成#

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

C++ 二分查找

2025-04-17

1 19

题解 | #表达式计算4#

我参考了不少已有的解析，所以说我写的代码还是老掉牙的递归，对于CPP模拟计算式而言，这确实是最好的办法了思路各位大神的题解已经说的很清楚了，我在这里主要是对于“开头负数是否可以处理”发表我的看法——可以不单独显示处理！我们之所以可以处理负数，主要归功于(l > r)时返回0，这一个看似无聊...

C++ 数学递归计数模拟

2025-04-15

1 25

题解 | #wyh的物品#

首先：最大Vz/Wz不是说按照单个Vz/Wz排序，这可是除法口牙！用样例看看就明白了修补骑士一开始感觉这是个01背包，但是这里使用太复杂了，可能会吃MLE或者TLE，后面自我寻思了一下发现了：能达到的单位价值。所以说是bz/az >= m，找到这个最大的m（保留两位小数）二分关系在于：无...

C++

2025-04-15

1 16