君鸿

分类

题解(1)

/ 注册

全部文章（共35篇）

题解 | 小美的树上染色

整体思路先定义一个概念【叶子】节点：该节点为白色节点，有且只有一个相邻节点可以一起涂成红色。若某个白色节点A存在多个相邻节点，但其中只有一个相邻的白色节点，满足双方权值的乘积是完全平方数，那么节点A也是叶子节点。本题有一个关键的说明，也就是第一句话：小美拿到了一棵树。既然是树，那么就不存在环。因此根...

2024-12-25

1 76

题解 | 合法的括号序列一维数组动态规划

题目求的是合法的括号序列数量，那么必然左括号和右括号数量相等，都是字符串长度的二分之一，设为n。这里首先排除字符串长度是奇数的情况，直接输出0。我们使用动态规划，令dp[i]表示左括号比右括号多i个的数量，那么i的取值范围可以是0-n。初始化状态，左右括号都为0个，只有这一种情况，dp[0] = 1...

2024-12-24

0 131

题解 | 游游出游 c++ 二分答案&单源最短路径

知识点1：二分答案对于一个问题，它的答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断（check函数），看是否对应的那个量达到了需要的大小，如果满足check，就放弃右半区间（或左半区间），如果不满足，就...

2024-12-24

0 57

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

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

2024-12-24

0 102

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

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

2024-12-23

1 51

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

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

2024-12-20

1 65

题解 | 游游开车出游

设加油时间为 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 37

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

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

2024-12-18

0 57

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

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

2024-12-18

1 46

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

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

2024-12-18

1 98