题目

给定一个整数数组 $a$，返回区间和在 $[lower, upper]$ 之间的个数，包含 $lower$ 和 $upper$。
区间和 $S(i, j)$ 表示在 $a$ 中，位置从 $i$ 到 $j$ 的元素之和，包含 $i$ 和 $j$ $(i ≤ j)$。

Solution

题目

给你两个单词 $a$ 和 $b$，请你计算出将 $a$ 转换成 $b$ 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

1. 插入一个字符

题目

给定一个无向、连通的树。树中有 $N$ 个标记为 $0…N-1$ 的节点以及 $N-1$ 条边 。

第 $i$ 条边连接节点 $edges[i][0]$ 和 $edges[i][1]$ 。

返回一个表示节点 $i$ 与其他所有节点距离之和的列表 $res$。

题目

最少修改几个数，使得数列满足 $a[i + 1] - a[i] = i$。$(n \in [1, 1e5], a[i] \in [-1e9, 1e9])$

Solution

先构造一个长度为 $n$ 满足题意的初始数列，然后将所给的数减去对应的初始构造的数，差值出现的次数最多的就是最长的满足题意的序列，要修改的就是剩余的那些数。

题目

从给定数列中能选出组成的最长等差数列长度为多少？$(n \in [1, 5000], a[i] \in [1, 1e9])$

Solution

$dp[i][j]$ 表示 $a[i]$ 为等差数列最后一个数，$a[j]$ 为倒数第二个数。

题意

最多可以把数组分成几个部分，使得每部分中位数都大于等于$m$。$(n,m,a[i] \in [1,5000])$

Solution

思维题，可以发现答案就是大于等于 $m$ 的个数减去小于 $m$ 的个数。

题意

在一维数轴上给出 $m$ 个线段，每个线段都都有 $l,r,w$ 三个数据代表这个线段的左右端点和这个区间权值。 从中取出若干个不相交的线段(区间端点可以共用)，在覆盖满 $[1,n]$ 的情况下，取出的线段中 $权重的最大值]$ 最小能为多少？

Solution

$dp[i]$ 代表覆盖满 $[1,i]$ 最大权值最小为多少，然后按左端点从小到大枚举线段，就有 $dp[r_i]=min(dp[r_i],max(dp[l_i],w_i))$。

题意

给你两组点，其中第一组中有 $size1$ 个点，第二组中有 $size2$ 个点，且 $size1 >= size2$。

任意两点间的连接成本 $cost$ 由大小为 size1 x size2 矩阵给出，其中 $cost[i][j]$ 是第一组中的点 $i$ 和第二组中的点 $j$ 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

题目

给定一个 $m$ 个元素的集合，问 $1-n$ 中有多少个数能被集合中至少一个元素整除。$(n <= 1e9, m <= 20)$

Solution

容斥原理，二进制枚举集合的所有子集，求子集的 $lcm$，如果子集大小是奇数，则 $res += n / lcm$，否则 $res-= n / lcm$。

题意

有 $n$ 个数，他们对每个数可以进行 $+1$ 或 $-1$ 操作，但对于每一个数，该操作最多只能执行一次。使用最少的操作次数，将这几个数构造成一个等差数列。如果完全不能构造成功，就输出 $-1$。

Solution

每个数最多只能修改一次，因此我们只要枚举前两个数的修改状态就能确定首项和公差，只有 $9$ 种可能，然后逐一判断取最小值即可。