题目

给定整数 $m$ 以及 $n$ 各数字 $A_1,A_2,..A_n$，将数列 $A$ 中所有元素两两异或，共能得到 $n(n-1)/2$ 个结果，请求出这些结果中大于 $m$ 的有多少个。

Solution

为了避免重复计算，字典树可以边维护边插入，先查询之前有多少个数与当前数 $x$ 异或和大于 $m$，我们从高位向低位枚举，对于两个数的同一个二进制位，需要分四种情况讨论：

题目

Solution

题意

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

Solution

题意

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。

「超赞子字符串」需满足满足下述两个条件：

该字符串是 s 的一个非空子字符串

题意

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

Solution

栈里面存左括号的位置，当遇到右括号时：

题意

给定两个严格递增数组，从任意一个数组出发到任意一个数组结束，当遇到相同元素时可以切换到另一个数组，只能从左到右走且每个数只计算一次，求最大累计得分。

Solution

当遇到两个数组都有的元素时可以切换，那其实从上一次遇到相同到这一次，假设中间这部分元素和是 $sum$，无非是看到底是上面这部分的 $sum$ 更大还是下面的 $sum$ 更大，然后选走罢了，如此循环下去。至于判断相同元素，提前用map记录每个元素的位置就好了。时间复杂度$O(n)$。

题意

你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

Solution

直接对所有的数排序，然后优先队列维护一个k个数组都有值存在且对当前来说长度最小的滑动窗口，同时维护答案即可。

题意

给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：

1. 这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[k..l] ，要么 j < k 要么 i > l 。
2. 如果一个子字符串包含字符 char ，那么 s 中所有 char 字符都应该在这个子字符串中。

题意

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

Solution

题意

给定权值矩阵，需要从左上角走到右下角，只能往右或往下走且权值会累加，问至少需要提前准备多少权值才能保证过程中不出现权值被耗尽的情况。

Solution

正着不太好写，可以尝试倒过来dp，$dp[i][j]$ 表示当前位置到终点至少需要准备多少权值，这样每个点要么从下边转移，要么从右边转移，选择最小的那个点转移即可，过程中需要保证权值至少为1，得到转移方程：$dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-mp[i][j],1)$。