目录

一，3274. 检查棋盘方格颜色是否相同

二，3275. 第 K 近障碍物查询

三，3276. 选择矩阵中单元格的最大得分

四，3277. 查询子数组最大异或值

---

一，3274. 检查棋盘方格颜色是否相同

本题就是找规律，假设白色是true，黑色是false，可以发现 a - 2 4 6 8，b - 1 3 5 7 是白色，也就是说可以通过 （x - 'a'）% 2 == (y - '0')%2 来判断该点是什么颜色，再返回两个点颜色是否相同。

代码如下：

class Solution {//a - 2 4 6 8//b - 1 3 5 7//c - 2 4 6 8//白public boolean checkTwoChessboards(String c1, String c2) {boolean a = (c1.charAt(0)-'a')%2 == (c1.charAt(1)-'0')%2;boolean b = (c2.charAt(0)-'a')%2 == (c2.charAt(1)-'0')%2;return a == b;}
}

二，3275. 第 K 近障碍物查询

本题是一种常见的堆应用问题（Top k 问题），维护第 k 小使用最大堆，维护第 k 大使用最小堆。本题求第 k 小的距离，所以使用最大堆。通过维护堆的大小来达到目的。

代码如下：

class Solution {public int[] resultsArray(int[][] queries, int k) {int n = queries.length;int[] ans = new int[n];PriorityQueue<Integer> que = new PriorityQueue<>((x,y)->y-x);for(int i=0; i<n; i++){que.offer(Math.abs(queries[i][0]) + Math.abs(queries[i][1]));if(que.size() > k)que.poll();ans[i] = que.size() == k ? que.peek() : -1;}return ans;}
}

三，3276. 选择矩阵中单元格的最大得分

本题可以使用枚举选哪个来做，枚举每一行可以选取的数字，求出所有组合中的最大得分，可以这样定义 dfs(i，j)：前 i 行可以获得的最大得分，j表示已经选举过的数字。代码如下：

//超时写法
//Java无法支持长度为100的整形，所以这里用py写的
class Solution:def maxScore(self, grid: List[List[int]]) -> int:@cachedef dfs(i: int, x: int) -> int:if i < 0: return 0res = dfs(i-1, x)for j in range(len(grid[0])):y = grid[i][j]if x >> y & 1: continueres = max(res, dfs(i-1, x|1<<y) + y)return resdfs.cache_clear()ans = dfs(len(grid)-1, 0)return ans 

但是该算法的时间复杂是O(n^2*2^100)，这个做法明显超时了，那么我们要如何来降低时间复杂度？

之前有场周赛可以提供一点思路，就是如果枚举下标超时，那么我们是否可以尝试枚举值呢？对于本题来说，矩阵的数据范围是1~100，此时它的时间复杂度就变成了O(mn * 2 ^ n)，我们可以使用选或不选的思路，定义dfs(i，j)：在 [1，i] 区间选择数字，且该数字不会出现在 j 集合中，此时所选元素的最大值之和。

• 对于 i，如果不选，那么接下来就变成从 [1，i-1] 区间选择数字，且该数字不会出现在 j 集合中，此时所选元素的最大值之和，状态表示为 dfs(i-1，j)
• 对于 i，如果选，假设该值在 k 行（在dfs之前要预处理每个值所在的行），那么接下来就变成从 [1，i-1] 区间选择数字，且该数字不会出现在 j U k 集合中，此时所选元素的最大值之和，状态表示为 dfs(i-1，j|1<<k)

代码如下：

class Solution {public int maxScore(List<List<Integer>> grid) {List<Integer>[] pos = new ArrayList[101];Arrays.setAll(pos, e -> new ArrayList<>());for(int i=0; i<grid.size(); i++){Set<Integer> set = new HashSet<>();for(int x : grid.get(i))set.add(x);for(int x : set)pos[x].add(i);}memo = new int[101][1<<grid.size()];for(int i=0; i<101; i++)Arrays.fill(memo[i], -1);return dfs(100, 0, pos);}int[][] memo;int dfs(int i, int j, List<Integer>[] pos){if(i == 0) return 0;if(memo[i][j] != -1) return memo[i][j];int res = dfs(i-1, j, pos);for(int x : pos[i]){if((j>>x&1) == 1) continue;res = Math.max(res, dfs(i-1, j|1<<x, pos) + i);}return memo[i][j] = res;}
}

递推版本：

class Solution {public int maxScore(List<List<Integer>> grid) {List<Integer>[] pos = new ArrayList[101];Arrays.setAll(pos, e -> new ArrayList<>());for(int i=0; i<grid.size(); i++){Set<Integer> set = new HashSet<>();for(int x : grid.get(i))set.add(x);for(int x : set)pos[x].add(i);}int[][] f = new int[101][1<<grid.size()];for(int i=1; i<101; i++){for(int j=0; j<1<<grid.size(); j++){f[i][j] = f[i-1][j];for(int x : pos[i]){if((j>>x&1) == 1) continue;f[i][j] = Math.max(f[i][j], f[i-1][j|1<<x] + i);}}}return f[100][0];}
}

四，3277. 查询子数组最大异或值

本题可以通过模拟每一步的过程来得到一个递推公式，如图所示：

根据该公式我们可以得到任意一个区间的异或值，那么要如何计算 [L，R] 区间子数组的最大异或值呢？这里也可以使用区间dp，mx[i][j]：[i，j] 区间的子数组的最大异或值，mx[i][j] = max(f[i][j]，mx[i][j-1]，mx[i+1][j])，画个图理解一下：

代码如下：

class Solution {public int[] maximumSubarrayXor(int[] nums, int[][] queries) {int n = nums.length;int[][] f = new int[n][n];//f[i][j] = f[i+1][j]^f[i][j-1];int[][] mx = new int[n][n];//mx[i][j] = max(f[i][j], max(mx[i+1][j], mx[i][j-1]))for(int i=n-1; i>=0; i--){f[i][i] = mx[i][i] = nums[i];for(int j=i+1; j<n; j++){f[i][j] = f[i+1][j]^f[i][j-1];mx[i][j] = Math.max(f[i][j], Math.max(mx[i+1][j], mx[i][j-1]));}}int[] ans = new int[queries.length];for(int i=0; i<queries.length; i++){ans[i] = mx[queries[i][0]][queries[i][1]];}return ans;}
}