口嗨解说340竞赛场

竞赛场T340口嗨解说

T1:N×N个方形格子，需要你找出对角线的最大指数。

解法①：扫描+预处理质数，把质数的范围是[测试用例的范围最小值-最大值这个区间]根据对联线规律，左上和右下构成的对角线是的坐标关系是是(r=c),左下和右上构成的对角线的坐标关系是(abs(r-c)=N-1)。预处理是假想，是为了方便频繁查询

T2：

解法①：用平衡二叉树HashMap，key是数字，value是分两断前缀与后后缀和，记前缀和是preSum,后缀和是suffixSum.

preSum+suffixSum+nums[i]=连续和

List,因为坐标是增量的，比他小的数字在左边，

比它大的数字在右边

左边的绝对值差值和是nums[ai]×(i-a0)-preSum(前缀和)

右边的绝对值差值和是：

后缀和-nums[ai]×(j-i+1)

综上所述:

总体时间复杂度是:O(2N)+NlogN

空间复杂度是：O(N)

解法②:能否一次过就能标记出来，取决于绝对值的运算技巧！

T3:

因为是最大差值最小值，不是最小差值最大值，如果是后者，是可以排序完就可以一遍找出所有的数字，这个规模是每个数字与邻居节点的绝对值差值，找差值用优先队列找第k个最小的。使用排序+贪心算法+二分，可以找每个数与最左端点，和最右端点，以及左右邻居节点，如果是最小差值最大化是可以排序一遍过，选每个数的左右结点的差值，然后大小刚好满足题目需求的n/2向下取整。

二分的check条件是统计当前下标数字是否满足p,并用cnt记作当前位置可以选中的数量，这个数量是符合线性递增的。大于往右移2个单位，小于往左边移动一个单位。

这题的核心是需要找到二分的check，难度是比较高的。

另外解法是穷举每个位置的规模，穷举复杂度是N²。 第一个位置的数字规模是n/2,第二个位置的数字规模是(n-1)/2,二分的核心引发的条件是这里。二分的查找目标是基于当前点去找符合条件的数字，基于递增排序明显大于它的是右边，所以很容易找。

T4:

想象为机器人移动，第一行和第一列的最大移动点是题目要求的区间，初始位置左和下的移动点都是可以发散的，这题的子问题是由条件决定，状态由当前移动到的目标点来决定

解法①是可以用单调性+每一行的线性DP,DP有两种状态转移，1是往左到目标位置(右下角)，往下也是的。可以计算一个点到目标点的最小距离，如果对角线长度大于3个单位的最小路径是两步，如果是两步或者一步可以直接返回。单调栈的单调性是当前行的移动位置的最大步数呈现递增

解法②是BFS,把它想象成原点(0，0)开始计数，每一个格子都计算步数，把它想象成一个矩阵移动坐标图标，按照左和下移覆盖每个格子计算，每一行符合动态计算。贪心动态计算下去，遇到当前节点是目标节点立即返回。

解法三：并查集，找当前坐标的父节点，每次迭代优化最短路径，每次迭代都加入路径，用路径的可达坐标与目标坐标进行匹配。如果目标节点和可达路径匹配，需要立即返回

解法四：启发性搜索，用Nextkey,但是需要预处理

解法五是:BitSet

解法六是:基于时间复杂度允许的情况下，可以用优先队列暴力枚举迭代，行列的最大步数加入队头。

解法⑧是:逆向走

解法9:把行列转换为一维数组，用线性树维护。把原点(0,0)作为根节点