修补骑士

题解

/ 注册

全部文章 / 题解（共22篇）

题解 | #大佬的生日大礼包#

这道题非常有意思，主要是首先每一个元素都至少包含一个鼠标与键盘，所以说去除后实际上就只是各占一个而已。对于“相邻的两个无法拿相同的礼物”实际上就是“相邻约束”，根据鸽巢原理，如果某一个超过了一半的总数，那么就至少会有两个人拿到一样的果盘。由于我们只关心能不能而不是怎么分配，所以说我们直接使用一个li...

C++ 前端贪心二分查找

2026-04-19

1 7

题解 | #圣诞节糖果#

很明显这道题给了你两种可能的选择情况，一种是不贪心，看看一开始就不如p的两堆，一种是加在一起后被余p后仍然是最大的情况首先，这道题里不可能出现比p大的情况，我们先把自己一个本身就大于p的全部在输入时就取MOD一次，然后对于第一种情况，很明显两个被MOD过的数字加在一起肯定是小于2 * p的，所以说...

C++ 前端双指针二分

2026-04-19

0 7

题解 | #牛牛的旅行#

这里故意把题目给说的很长来混淆视野的，实际上能够购买的肯定是无脑疯狂购买，如果不满足，就战个未来后面拿到了再来。问题就是，为什么是满足的时候就回去找呢？而不是一次性满足之后再回来或者其他莫名其妙的方案？我们这里至少要走一次，而我们是只要满足了自己所有的欠债就回去，那么一个不满足的我们只会走一次（走到...

C++ 前端贪心遍历

2026-04-18

1 9

题解 | #牛牛学括号#

这里用回溯的话肯定炸了，我们观察会发现，实际上对于这种括号问题，每一个左边括号的所有匹配方案是由他右边的右括号决定的，有多少右括号就有多少种选择方式，我们就可以很简单的直接从右往左扫一遍，遇见了左括号就从已有的右括号里拿出一个（都可以配对），然后后续的再次配对由于顺序天然的避免了不可能的情况（也就是...

C++ 前端遍历贪心

2026-04-18

1 8

题解 | #花店橱窗#

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

C++ 动态规划

2025-06-19

1 109

题解 | #石子合并#

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

C++ 动态规划模拟

2025-06-19

1 125

题解 | #牛牛的战役#

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

C++ 数学贪心二分查找

2025-06-14

1 80

题解 | #牛牛的朋友#

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

C++ 数组贪心数学

2025-06-09

1 96

题解 | #位数差#

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

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

2025-06-09

1 90

题解 | #K-th Number#

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

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

2025-06-03

1 96