先放题目
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题
惯例不做