目录

一，3280. 将日期转换为二进制表示

二，3281. 范围内整数的最大得分

三，3282. 到达数组末尾的最大得分

四，3283. 吃掉所有兵需要的最多移动次数

---

一，3280. 将日期转换为二进制表示

本题就是简单的字符串和整数之间的转换，可以直接调用库函数解决，代码如下：

class Solution {public String convertDateToBinary(String date) {String[] t = date.split("-");int i = 0;for(String x : t){t[i++] = Integer.toBinaryString(Integer.parseInt(x));}return String.join("-", t);}
}

二，3281. 范围内整数的最大得分

本题求数组两两之间最小的绝对差，那么最小值一定会出现在排序后相邻的两数之间，所以我们可以先将数组排序。又因为题目中的数据范围导致我们无法使用O(n^2)的做法，这时就需要至少O(nlogn)的做法，再结合排序和求最大值，自然而然就能想到二分，再分析一下是否具有单调性，答案越小，它越能使满足题目要求，具有单调性，所以该题的做法就是二分答案。

知道二分后，最难的一步就是如何判断二分的答案 k 是否满足条件，要想使得每个start[i]的范围都在[start[i]，start[i] + d]之间，那么对于每个值都需要尽可能的小（这样后一个值才更可能处于范围内），所以我们的第一个值一定选择start[0]，如果 x1 = start[0] + k 超过了 start[1] + d，那么 r 缩小；如果 x1 <= start[1] + d，此时还需要保证 x1 >= start[1]，也就是 x1 = max(start[i]，x0 + k)，对于所有的 i 都满足 xi <= start[i] + d，那么 l 增大。

代码如下：

class Solution {public int maxPossibleScore(int[] start, int d) {int n = start.length;Arrays.sort(start);long l = 0, r = (start[n-1] - start[0] + d)/(n-1);//最大是均值while(l <= r){long mid = (l + r) / 2;if(check(mid, start, d)){l = mid + 1;}else{r = mid - 1;}}return (int)l-1;}boolean check(long k, int[] start, int d){int n = start.length;long now = start[0];for(int i=1; i<n; i++){now = Math.max(now + k, start[i]);if(now > start[i] + d) return false;}return true;}
}

三，3282. 到达数组末尾的最大得分

本题看到后的第一个想法就是dfs选或不选，记录前一个选择的下标 j，看是否选择nums[i]。但是对于本题来说，dfs的做法的时间复杂度是O(n^2)，它一定会超时，所以需要其他做法。

"dp的尽头是贪心"，所以我们可以试着使用贪心的思路去做，下面画个图理解一下：

我们将数组转换成矩形，那么计算最大总得分就变成了计算矩形的最大面积，那么要想面积大，那么对于每个下标 i 来说，当前能得到的面积一定是max(nums[0:i])。注意：题目中的终点是n-1！！

代码如下：

class Solution {public long findMaximumScore(List<Integer> nums) {int n = nums.size();long ans = 0, mx = nums.get(0);for(int i=1; i<n; i++){ans += mx;mx = Math.max(mx, nums.get(i));}return ans;}
}

四，3283. 吃掉所有兵需要的最多移动次数

本题是一道综合题，我们需要先通过 bfs 计算出(kx，ky) 与 (xi，yi) 任意两点之间的距离（指🐎从a -> b最小的移动距离），预处理之后，问题就变成了从 0 开始，将所有点联通所需的最大移动次数。

假设有 n 个兵，考虑下面两种情况：

• Alice 吃 1 号兵，Bob 吃 2 号兵，Alice 吃 3 号兵，轮到 Bob 操作
• Bob 吃 1 号兵，Alice 吃 2 号兵，Alice 吃 3 号兵，轮到 Bob 操作

可以发现上述两种做法都是 Alice 吃 3 号兵，轮到 Bob 操作，具有重复子问题，可以使用dfs来做。根据上述情况，我们需要两个参数：

• i：表示前一个被吃掉的兵
• mask：表示所有已经被吃掉的兵的集合

还有一点需要注意：Alice 和 Bob 所进行的操作不相同，所以需要分别讨论：

• 当 mask 中 1 的个数为奇数时，说明轮到 Alice 操作，假设当前选 j（不在mask集合中），dfs(i，mask) = max(dfs(j，maskUk) + dis[i][j])
• 当 mask 中 1 的个数为偶数时，说明轮到 Bob 操作，假设当前选 j（不在mask集合中），dfs(i，mask) = min(dfs(j，maskUk) + dis[i][j])

代码如下：

class Solution {int[][] dirct = new int[][]{{1,2},{-1,-2},{-1,2},{1,-2},{2,1},{-2,-1},{-2,1},{2,-1}};public int maxMoves(int kx, int ky, int[][] positions) {int n = positions.length;//(kx,ky)->(i,j)的最短距离//将(kx, ky) 和 (xi, yi) 依次当成 0 1 2 3 ..... nint[][] dis = new int[n+1][n+1];int[][] f = bfs(kx, ky);for(int i=0; i<n; i++){dis[0][i+1] = dis[i+1][0] = f[positions[i][0]][positions[i][1]];}for(int i=0; i<n; i++){f = bfs(positions[i][0], positions[i][1]);for(int j=i+1; j<n; j++)dis[i+1][j+1] = dis[j+1][i+1] = f[positions[j][0]][positions[j][1]];}//点到点的最短距离//从0开始互相联通的最多移动次数memo = new int[n+1][1<<(n+1)];for(int i=0; i<=n; i++)Arrays.fill(memo[i], -1);return dfs(0, 1, dis);}int[][] memo;int dfs(int i, int mask, int[][] dis){int cnt = Integer.bitCount(mask);if(cnt == dis.length) return 0;if(memo[i][mask] != -1) return memo[i][mask];int res = cnt%2==1?Integer.MIN_VALUE:Integer.MAX_VALUE;for(int j=1; j<dis.length; j++){if((mask>>j&1)==1) continue;if(cnt%2 == 1) res = Math.max(res, dfs(j, mask|1<<j, dis) + dis[i][j]);//Alice要求最大路径if(cnt%2 == 0) res = Math.min(res, dfs(j, mask|1<<j, dis) + dis[i][j]);//Bob要求最短路劲}return memo[i][mask] = res;}int[][] bfs(int kx, int ky){//计算从 (kx, ky) -> (x, y) 的最小移动次数int[][] f = new int[50][50];Queue<int[]> que = new LinkedList<>();que.add(new int[]{kx, ky});while(!que.isEmpty()){int size = que.size();while(size-- > 0){int[] t = que.poll();for(int[] d : dirct){int x = t[0] + d[0], y = t[1] + d[1];if(x>=0 && x<50 && y>=0 && y<50 && f[x][y]==0){f[x][y] = f[t[0]][t[1]] + 1;que.add(new int[]{x, y});}}}}return f;}
}