题意

给你一个 $a$ 数组，其中 $a[i] = [startDay_i, endDay_i, value_i]$ ，表示第 $i$ 个会议在 $startDay_i$ 天开始，第 $endDay_i$ 天结束，如果你参加这个会议，你能得到价值 $value_i$ 。同时给你一个整数 $k$ 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和。$(k \in [1, n], k * n \in [1, 1e6], startDay_i, endDay_i \in [1, 1e9], value_i \in[1, 1e6])$

Solution

题意

给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。$(n, k \in [1, 100000])$

Solution

用优先队列+延迟删除有点麻烦，可以考虑直接用 multiset 做，本质都是一样的，维护两个大小相同或差一的集合（自动排序）$l 和 r$，$l$ 维护小于等于中位数的值，$r$ 维护大于等于中位数的值，$multiset$ 的优秀特性可以在 $log$ 时间复杂度内进行增删操作。具体细节较多，时间复杂度 $O(nlog(k))$。

题意

给定一个 $nm$ 的权值矩阵，求从左上角走到右下角。$(n, m \in [1, 100], w \in [1, 1e6])$

一条路径耗费的体力值是路径上相邻格子之间 高度差绝对值的最大值 决定的。

Solution

1. 二分答案：由于答案具有单调性，所以可以二分答案，然后通过 $bfs$ 进行验证。
2. 并查集：类似于最小生成树，将所有的边都建出来，然后贪心的将当前权值最小的边加入集合，判断起点和终点是否联通即可。
3. 最短路：将所有的边建出来，做一次起点到终点的最短路径即可。

题意

给你一个整数数组 $g$，它是前 $n$ 个正整数的排列，且 $n$ 是个 奇数 。

它被加密成另一个长度为 $n - 1$ 的整数数组 $a$ ，满足 $a[i] = g[i]$ ^ $g[i + 1]$。比方说，如果 $g = [1,3,2]$，那么 $a = [2,1]$。

给你 $a$ 数组，请你返回原始数组 $g$。题目保证答案存在且唯一。

Solution

题意

给你一个字符串 $s$，以及该字符串中的一些「索引对」数组 $pairs$，其中 $pairs[i] = [a, b]$ 表示字符串中的两个索引（编号从 $0$ 开始）。

你可以 任意多次交换 在 $pairs$ 中任意一对索引处的字符。

返回在经过若干次交换后，$s$ 可以变成的按字典序最小的字符串。

Solution

题意

在数轴上找到一个点，使得到其余 $n$ 个点距离之和最小。$(n \in [1, 1e5])$

Solution

考虑绝对值不等式：

题意

给定一个已排序的正整数数组 $nums$，和一个正整数 $n$ 。从 $[1, n]$ 区间内选取任意个数字补充到 $nums$ 中，使得 $[1, n]$ 区间内的任何数字都可以用 $nums$ 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

Soluiton

容易证明，对于正整数 $x$，如果区间 $[1,x−1]$ 内的所有数字都已经被覆盖，且 $x$ 在数组中，则区间 $[1,2x−1]$ 内的所有数字也都被覆盖。

题意

给定一个仅包含 $0$ 和 $1$ 、大小为 $n * m$ 的二维二进制矩阵，找出只包含 $1$ 的最大矩形，并返回其面积。$(n, m \in [1, 200])$

思路

有一个子问题，求柱状图最大矩形。预先求出 $1-i$ 层的 $h[i]$ 然后利用套用子问题的模板即可，复杂度 $O(n * m)$.

题意

现在有 $n$ 个音符和 $m$ 对共鸣关系，编号为 $1-n$，每个音符自己有一个奏响时的优美程度，共鸣关系 $(x,y,z)$ 表示音符 $x$ 和 $y$ 同时奏响的额外优美程度是 $z$，同时不奏响则为 $-z$，其他情况为 $0$，求最大优美程度。$(n,m \in [1,1e5])$

思路

对于一对共鸣关系而言，在不选的情况下收益为 $-z$，则选择一个的话，收益为 $-z + z = 0$，都选择的话为 $-z + 2z = z$。因此可以预先把每对关系的两个数都加上 $z$，刚开始我们是不选任何有联系的音符的，因此初值为 $-z$，那么选择一个数就会加上 $z$，选择两个就会加上 $2z$，满足了之前所讨论的关系。答案初始化为所有关系都不选的情况，即 $-sum(z)$，然后只要贪心的选择对答案有正贡献的值就行了。

题意

从 $n$ 个数中任选 $k$ 个数，取得这 $k$ 个数中最大的一个数，求每个数被取得的概率。$(n, k \in [1, 2e5])$

Solution

将数组排序后，枚举每个数被作为最大值的可能性，当第 $i$ 个数作为最大值时，其它 $k - 1$ 个一定从前 $i - 1$ 个里面选，即方案数为 $C(i - 1, k - 1)$，将其除以总方案数 $C(n, k)$ 即为被取得概率。