修补骑士

分类

题解(18)

/ 注册

全部文章（共7篇）

题解 | #牛牛的战役#

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

C++ 数学贪心二分查找

2025-06-14

1 13

题解 | #牛牛的朋友#

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

C++ 数组贪心数学

2025-06-09

1 17

题解 | #位数差#

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

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

2025-06-09

1 18

题解 | #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 20

题解 | #表达式计算4#

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

C++ 数学递归计数模拟

2025-04-15

1 40

题解 | #Sliding Window#

我看不少人和我一样，这样写会过60%其他TLE，好像是卡常或者别的什么？不过思路已经确定了，下面这串仅供参考 ">#define int long long using namespace std; //修补骑士之前写过树状数组，加权线段树，以及归并排序的方法 //对于树状数组与线段树，都是利用...

C++ 归并排序树状数组线段树数学

2025-04-13

1 39