本人排名第14名，第三题忽略了一个corner case，不然还能蹭进前10混个奖金。
整体而言，这次个人赛不难。前三题虽然有点小想法，但整体并不复杂，也比较直接。第四题第五题的数据范围都给了很强的提示。整体难度的话，差不多相当于周赛的3/4/5/6/6吧。（最近几个月周赛的难度总是瞎标，没太大参考价值）
第一题、***方阵
第一题标准的easy题。因为可以随意变动位置，所以只需要关注哪些颜色，开始时没有，结束时有了；哪些颜色，开始时少，结束时多。这一点用python的Counter可以简单实现。
时间复杂度：O(n)，空间复杂度：O(n)
class Solution:
def minimumSwitchingTimes(self, source: List[List[int]], target: List[List[int]]) -> int:
cs = collections.Counter([t for l in source for t in l])
ct = collections.Counter([t for l in target for t in l])
to_ret = 0
for k in ct :
if ct[k] > cs[k] :
to_ret += ct[k] - cs[k]
return to_ret第二题、心算挑战
第二题的核心问题在于什么时候，最大的cnt个数不满足要求，以及遇到不满足要求的情况，应该如何调整。
而这两个问题的答案也很简单。当最大的cnt个数中有奇数个奇数时不满足要求。调整方式为：先选取最大的cnt个数，然后将最小的偶数替换为未被选取的最大奇数，或将最小的奇数替换为未被选取的最大偶数。
比赛时为了省事，利用排序，写的时间复杂度：O(n logn)，空间复杂度：O(n)的解法。这里选取前cnt大的数，可以不用排序，从而将时间复杂度降低为O(n)。空间复杂度也可以调整为O(1)的。
class Solution:
def maxmiumScore(self, cards: List[int], cnt: int) -> int:
cards = sorted(cards, reverse=True)
e1 = [t for t in cards[:cnt] if t % 2 == 0]
o1 = [t for t in cards[:cnt] if t % 2 == 1]
e2 = [t for t in cards[cnt:] if t % 2 == 0]
o2 = [t for t in cards[cnt:] if t % 2 == 1]
sumt = sum(e1+o1)
if len(o1) % 2 == 0 :
return sumt
to_ret = 0
if len(e2) > 0 :
to_ret = max(to_ret, sumt+e2[0]-o1[-1])
if len(o2) > 0 and len(e1) > 0 :
to_ret = max(to_ret, sumt+o2[0]-e1[-1])
return to_ret第三题、黑白翻转棋
这题虽然操作很复杂，还有递归存在，不过由于棋盘最大只有8*8，可以用比较暴力的算法，对每个可以落子的点，依次尝试落子，并计算棋盘的变化。
我不太确定递归地去解是否会超时。但由于（我猜大概率）需要维护一个变化的棋盘，比较麻烦，我在比赛时，用了另一种解法：计算每个点，从白或空变为黑，会同时将哪几个点变成黑色，并将之存起来。而在尝试落子的过程中，用BFS/宽搜，逐一计算被影响的点。
没细算，我猜时间复杂度O(n^4)或O(n^5)，空间复杂度O(n^3)，主要考虑p2ps的规模。n=8。
代码中的减一，主要是题目问的是有多少颗子由白变黑，而我计算的是棋盘上添加了多少黑子。这里需要把落子减去。而我wa的那次，是因为没写那个和0取max。当棋盘上无处落子时，没有取max返回会是-1。
class Solution:
def flipChess(self, chessboard: List[str]) -> int:
m, n = len(chessboard), len(chessboard[0])
p2ps = {}
for i in range(m) :
for j in range(n) :
if chessboard[i][j] == 'X' :
continue
dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
dirs += [[1, 1], [1, -1], [-1, 1], [-1, -1]]
sett = set()
for dx, dy in dirs :
set_temp = set()
for k in range(1, 8) :
ti, tj = i+dx*k, j+dy*k
if not 0<=ti<m or not 0<=tj<n :
break
if not chessboard[ti][tj] == 'O' :
if chessboard[ti][tj] == 'X' :
sett |= set_temp
break
set_temp.add((ti, tj))
p2ps[(i, j)] = sett
to_ret = 0
for i in range(m) :
for j in range(n) :
if not chessboard[i][j] == '.' :
continue
to_ret_set = set()
to_visit = [(i, j)]
while len(to_visit) > 0 :
pt = to_visit.pop(0)
to_ret_set.add(pt)
for pn in p2ps[pt] :
if not pn in to_ret_set :
to_visit.append(pn)
to_ret = max(to_ret, len(to_ret_set))
return max(to_ret - 1, 0)第四题、玩具套圈
这道题数据量很唬人，但也有很强的提示。
最简单的想法，逐一比较每个圈和玩具，看是否套种。但圈的数量和玩具的数量都在10^4量级，10^8肯定超时。但可以看到半径小呀无论玩具的半径还是圈的半径都在110之间。那每个玩具只有可能被中心落在一个20*20范围内的圈套中。这样，时间复杂度就OK了。
严格来讲，对每个玩具，记d为其半径与圈半径之间的差距（比圈半径大的玩具不考虑）。只有在离玩具中心d距离以内的圈才能套中它。用一个set去存所有的圈。O(1)时间检查圈是否存在。每个玩具需要检查O(d^2)量级的圈。
时间复杂度：O(d^2*n)，空间复杂度：O(1)。n=10^4，d=9
class Solution:
def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
scircles = set([(a, b) for a, b in circles])
to_ret = 0
for ai, bi, ri in toys :
if ri > r :
continue
dis = r-ri
mark = False
for x in range(ai-dis, ai+dis+1) :
for y in range(bi-dis, bi+dis+1) :
if (x-ai)**2+(y-bi)**2 > dis ** 2 :
continue
if (x, y) in scircles :
mark = True
break
if mark :
break
if mark :
to_ret += 1
return to_ret第五题、十字路口的交通
这道题数据量的提示也非常明显。每个方向的车不超过20辆，也就是说，所有中间的通行状态数规模为20^4≈10^5，可以作为状态进行DP。
状态之间的转移方程说简单也简单，就是每个方向最多通行一辆车，且通行的车不相撞。说复杂也复杂，这个不相撞我就没想好怎么写。
反正我中间是边写边改，最后版本是用一个状态压缩，15种可能的消除方式。每种方式再写很多规则，根据车的走向，判断是否能够消除。
时间复杂度：O(n^4*4^4)，空间复杂度：O(n^4)。n=20。这里4^4代表4个方向，下一辆车的所有可能状态（3种方向+1种空）。
class Solution:
def trafficCommand(self, directions: List[str]) -> int:
@functools.lru_cache(None)
def solve(e, s, w, n) :
print(e, s, w, n)
if len(e+s+w+n) <= 1 :
return len(e+s+w+n)
to_ret = 1e99
for case in range(1, 16) :
des = ''
mark = True
for k, st in zip([1, 2, 4, 8], [e, s, w, n]) :
if k & case > 0 :
if len(st) == 0 :
mark = False
des += st[:1]
if not mark :
continue
if len(set(des)) < len(des) :
continue
if (1+2) & case == (1+2) :
if e[0] + s[0] in ['WN', 'SN', 'SW'] :
continue
if (1+4) & case == (1+4) :
if e[0] + w[0] in ['WN', 'SE'] :
continue
if (1+8) & case == (1+8) :
if e[0] + n[0] in ['WE', 'WS', 'SE'] :
continue
if (2+4) & case == (2+4) :
if s[0] + w[0] in ['NE', 'WE', 'WN'] :
continue
if (2+8) & case == (2+8) :
if s[0] + n[0] in ['NE', 'WS'] :
continue
if (4+8) & case == (4+8) :
if w[0] + n[0] in ['ES', 'NS', 'NE'] :
continue
ne = e if (1&case==0) else e[1:]
ns = s if (2&case==0) else s[1:]
nw = w if (4&case==0) else w[1:]
nn = n if (8&case==0) else n[1:]
to_ret = min(to_ret, solve(ne, ns, nw, nn))
return to_ret + 1
return solve(directions[0], directions[1], directions[2], directions[3])