题意

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

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

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

Solution

题意

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

思路

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

题目

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

Solution

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

题意

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

Solution

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

题意

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

Solution

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

题意

给定一棵树，A 在 $x$ 点，B 在 $y$ 点，B 追 A，两人每次可以往相邻点移动，A 先跑，问 A 最晚什么时候被追上。

Solution

结论：找到一个点，满足 $dis_B > dis_A$ 且 $dis_B$ 最大，即为最终落脚点。

题意

给定一个字符串 $s$，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

Solution

等价于求字符串 $s$ 以 $s_0$ 开头的最长回文串，然后多出来的后缀翻转后就是需要补足的最小长度，判断回文可以采用哈希。

题目

$n$ 个物体，每个物品都有 $k$ 个属性，实际上就是 $a[n][k]$ 的数组，满足 $a[i][0]+a[j][0]=a[i][1]+a[j][1]=…=a[i][k−1]+a[j][k−1]$ 的物体 $i$ 和物体 $j$ 称为一对完美对，求完美对对数。

Solution

题目

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

注意：1 ≤ k ≤ n ≤ 10^9。

Solution

题意

给定数组，求上述式子的最大值。

Solution