Gnomeshgh112

分类

/ 注册

全部文章（共17篇）

题解 | 最长上升子序列(一)

DP的模板题目。dp[i]表示以a[i]为结尾的最长上升子序列的长度。dp[i] = max(dp[i], dp[j] + 1);其中，j < i并且a[j] < a[i]。遍历所有的i, j。计算出的dp数组中的最大值即为结果。 #include <bits/stdc++.h&g...

2025-04-07

1 23

题解 | 【模板】哈夫曼编码

哈夫曼树的创建：所有出现过的字符都作为叶子结点，放到优先队列中从优先队列中取两个出现频率最小的结点，将两个结点合并-->既创建一个新节点，这个节点的左右子树为刚才取出来的那两个频率最小的结点，这个结点的频率为这两个结点的频率之和。将这个新创建的结点重新放到优先队列中。迭代步骤2，步骤2每次会让...

2025-04-02

1 49

题解 | 活动安排->DP+离散化

先将所有的起始位置进行排序，从后往前依次查看，查看到下标为 i 的位置，如果以这个位置为起点的活动要被选择的话，那么就将这个位置结束的位置+1作为结果，如果不被选择的话，就是这个位置的下一个时刻的位置作为结果。就是：dp[i] = max(dp[i + 1], dp[k] + 1）其中k是以i为起始...

2025-04-01

1 39

题解 | 隐匿社交网络-->map维护

因为权重在18次方以内，变为2进制不超过64位，最多情况下只有64个网络，从左到右针对每一个数字，可以通过遍历网络，来看自己是否属于某一个网络。网络的标志为：网络内各个数字的或，如果这个位置上为1，说明网络内至少存在一个用户，在这个位置上为1。判断一个数字是否属于一个网络：这个数字和网络标识与，如果...

2025-03-28

2 35

题解 | 而后单调-->遍历+二分

因为最后的结果要求是严格递增或者严格递减，所以如果原来的序列中存在相同的元素，直接判负考虑序列中不存在相同元素的情况，可以找到一个长度为m的单调递增或者单调递减的序列，查看其最大值和最小值在已经排序好的序列中的位置的差值是不是等于m。如果等于m，则说明未排序的序列中，其他n - m个数字，不会出现在...

2025-03-27

2 36

题解 | 小红的01子序列构造（easy）

假设最后的结果左边界为i，右边界为j，那么当左边界为i，右边界在j右边时，计算出的结果一定大于等于k，同样的，如果右边界在j左边，结果一定小于等于k。同理，固定j变化i可以得到相似的结论。所以，使用i和j两个位置，先将j一直向右移动，一旦i j超过了k，那么就将i向右移动。直到满足等于k为止，这样就...

2025-03-26

2 35

题解 | 气球谜题

所有的解空间中，一共存在15中状态，每一种状态满足无后效性的性质，可以用动态规划来维护这15种状态，得到最优解。详细状态可见代码注释 #include <bits/stdc++.h> using namespace std; long long Min(long long a, lon...

2025-03-26

5 61