Aquabet

Talk is cheap. Show me the code.

0%

力扣杯2021秋个人赛解题报告

先放题目

  LCP 39. 无人机方阵
  LCP 40. 心算挑战
  LCP 41. 黑白翻转棋
  LCP 42. 玩具套圈
  LCP 43. 十字路口的交通

A题B题

  俩签到题
  A题:两组哈希存下每种颜色的个数,然后 ans += map[0][i]-map[1][i] , return ans/2
  B题:贪心 从大到小排序,取前cnt个的和sum,并记录在前cnt个中最小的奇数oddMin和最小的偶数evenMin。然后在剩下的数里面找最大的奇数oddMax和最大的偶数evenMax。(注意:这里的oddMin,evenMin要大于等于oddMax,evenMax)如果sum为偶数, return sum 。如果sum是奇数, return max(sum-oddMin+evenMax, sum-evenMin+oddMax)

C题

  模拟。首先找到图上所有的白点,然后对白点进行搜索。搜索包含三个方向,横着,竖着,斜着。对目标点三个方向分别向前,向后遍历。遇到黑点、空格或者边界就停下来。如果两边截止点都是黑就 ans += 中间的棋数 。如果有一个黑一个空就 putChess = max(putChess, 中间的棋数) (记得记录每颗白棋在三个方向是否遍历过,如果已经遍历过就跳过,可以剪枝)。遍历完之后 ans += putChess。最后还有一个检查while(上一轮检查有棋能翻转){检查所有白棋能不能被翻,能翻就翻了并且ans += num}

D题

  最开始以为是个计算几何, $O(n^2)$ T了两次优化不过
  后来想起这个里 P2249 【深基13.例1】查找 题解 用户Graphcity的胡扯莫队。于是我按照这个思路,过了这题,具体如下:
  首先对所有圆和玩具按x坐标进行排序,x坐标相同的按y排序。然后开始查询,对每一个圈适配玩具,并将该圆圈的圆心减半径$X_i-r$之后的第一个玩具记为nowMinX,如果下一个圆圈的$X_{i+1}$与$X$不等,此时搜索直接从nowMinX开始,对玩具的Y坐标同样进行类似处理,当$circles_i$和$circles_{i+1}$的$X$坐标相同时,就可以从nowMinY开始。

E题

  惯例不做

代码

  详见我的github仓库