君鸿

分类

题解(1)

/ 注册

全部文章（共22篇）

题解 | 【模板】最小生成树 Kruskal + 并查集

最小生成树一般有两种方法，即Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法。前者以边来生成，后者以顶点来生成。这里介绍Kruskal算法。具体思路是，将所有m条边按照权重w从小到大排序，然后遍历其中的每一条边，判断该边的两个顶点是否联通，若没有联通，则选取该边，并将两个顶点联通。这里一个比...

2024-12-24

0 74

题解 | 【模板】单源最短路Ⅰ ‖ 无权图

step1：创建一个数组，表示从起点s到每个顶点的最短路径。初始化值为-1。step2：创建一个队列，起点s的最短路径设为0，将起点s加入队列中。step3：从队列首部取出一个顶点u，依次判断该顶点连接到的每一个顶点v。若v的最短路径为-1，则更新为u的最短路径+1，并将v加入到队列末尾。step4...

2024-12-23

1 39

题解 | 请客吃饭贪心+前缀和+双指针

由题意可知，饭局的隔阂值为隔阂最大的那一对朋友的隔阂，也就是所有参与饭局的朋友中财富最大的减去财富最小的。根据贪心的思想，如果邀请了其中两名成员和，那么想要让愉悦值最大，应当尽可能多的邀请财富值在两者之间的其他朋友。将所有成员按照财富从小到大排序，就可以将题目转化为求连续区间的愉悦值之和大于等于k的...

2024-12-20

1 43

题解 | 游游开车出游

设加油时间为 t，那么总用时 = t + y / (v0 + xt) = t + (y / x) / (v0 / x + t)令 c = y / x，a = v0 / x，那么原式 = t + c / ( t + a) = (t + a) + c / (t + a) - a <= 2 * sq...

2024-12-18

0 22

题解 | 【模板】整数域三分

函数 f(x) = | kx + a | + b，当x = -a/k 时最小，函数图像是一个V字形，有最小值。看到这个形状，我们很容易想到用三分法寻找最小值的位置。然而题目中的F(x) 是多个f(x) 的和，如果要用三分法，就必须保证F(x)在最小值左边单调递减（或平），在右边单调递增（或平），否则...

2024-12-18

0 39

题解 | 平均数为k的最长连续子数组

思路：将输入数组的每个元素减去k，即可将题目转化为求“和为0的最长连续子数组”。使用前缀和的思想，我们维护一个变量sum。并用哈希表记录前缀和为sum的最小位置。假设前i个元素和为sum，前j个元素和也为sum，那么毫无疑问，第i+1个元素开始直到第j个元素之和必然为0。根据这个思路，我们遍历一遍数...

2024-12-18

1 30

题解 | 小红的子序列逆序对

先思考这样一个问题，若存在一个逆序对，那么这个逆序对会被多少个子序列包含呢？数组的长度为n，除去逆序对所包含的两个元素外，其余的元素都有存在或者不存在两种选择，由此构成的子序列数量应为2^(n-2)个。显而易见，最终答案就是逆序对数量乘以 2^(n-2)。而求逆序对数量有多种实现方法，常见的有并归排...

2024-12-18

0 35

题解 | 小美的蛋糕切割

看到很多人说二位前缀和，不禁有些奇怪，有那么复杂吗？这题完全就用不到动态规划呀，纯数字计算不就好了？说说我的思路，首先维护两个一维数组row和col，分别保存矩阵每一行的元素和，与每一列的元素和。这一步在数据输入的时候就完成了，同时我们还得到了矩阵所有元素的和sum。接下来分别计算横着切和竖着切，以...

2024-12-17

0 38

15天大厂真题带刷 - ZT19 | 不用线段树，用树状数组

虽然题目标题写的线段树，但实际上更适合用树状数组求解。先上传一下代码，后续再试试线段树。链接 - 树状数组详解 #include <iostream> #include <vector> using namespace std; int n; vector<long ...

2024-12-17

1 37

题解 | 小红的好数

看了其他人的题解，感觉都挺复杂。我来个简单易懂的，五重循环搞定。 #include <iostream> using namespace std; int main() { int k; cin >> k; for (int a = 9; a >...

2024-12-16

0 39