2021秋季个人赛

1. 无人机方阵

class Solution:
    def minimumSwitchingTimes(self, source: List[List[int]], target: List[List[int]]) -> int:
        ds = Counter(reduce(lambda x,y:x+y, source))
        dt = Counter(reduce(lambda x,y:x+y, target))
        #print(ds,dt)
        
        res = 0
        for c,f in dt.items():
            if c not in ds:
                res += f
            else:
                res += max(0, f-ds[c])
        
        return res

一直以为 [i for i in row for row in grid] 写不出来是系统原因，
然后发现要这样写：[i for row in grid for i in row]

2. 心算挑战

选 cnt 张牌，总和为偶数，求最大值

class Solution:
    def maxmiumScore(self, cards: List[int], cnt: int) -> int:
        cards.sort()
        left, right = cards[:-cnt], cards[-cnt:]
        res = sum(right)
        #print(left,right,res)
        
        if res%2:
            r1, r2 = 0, 0  #右边最小奇数，偶数
            for r in right:
                if not r1 and r%2==1:
                    r1 = r
                if not r2 and r%2==0:
                    r2 = r
                if r1 and r2:
                    break
            l1, l2 = 0, 0 #左边边最大奇数，偶数
            for l in left[::-1]:
                if not l1 and l%2==1:
                    l1 = l
                if not l2 and l%2==0:
                    l2 = l
                if l1 and l2:
                    break
            #print(r1,r2,l1,l2)
            
            if all([r1, r2, l1, l2]):
                return max(res - r1 + l2, res - r2 + l1)
            elif r1 and l2:
                return res - r1 + l2
            elif r2 and l1:
                return res - r2 + l1
            else:
                return 0
            
        return res

刚开始是用两个堆，没做出来。然后贪心出来了

3. 黑白翻转棋⭐

测试用例都对的，不知为啥结果不对

class Solution:
    def flipChess(self, chess: List[str]) -> int:
        rows, cols = len(chess), len(chess[0])
        board = []
        for row in chess:
            board.append([])
            for c in row:
                board[-1].append(c)
        
        
        res = 0
        def dfs(i,j,dx,dy,cnt,vis):
            x, y = i+dx, j+dy
            if 0<=x<rows and 0<=y<cols and board[x][y] != ".":
                if board[x][y] == "X":
                    if vis:
                        for ii,jj in vis:                     #回溯
                            board[ii][jj] = "X"
                        
                        for ii,jj in vis:
                            for x,y in ([(-1,-1),(-1,0),(-1,1),(0,1),(0,-1),(1,1),(1,0),(1,-1)]):
                                cnt += dfs(ii,jj,x,y,0,set())  
                                
                        for ii,jj in vis:
                            board[ii][jj] = "O"
                    return cnt
                else:
                    vis.add((x,y))
                    return dfs(x,y,dx,dy,cnt+1,vis)
            return 0
            
        for i in range(rows):
            for j in range(cols):
                if board[i][j]==".":
                    res = max(res,sum([dfs(i,j,x,y,0,set()) for x,y in ([(-1,-1),(-1,0),(-1,1),(0,1),(0,-1),(1,1),(1,0),(1,-1)])]))
        
        return res

啊这，有个地方重复计数了，重写dfs还是错，麻了，用 bfs 写了

class Solution:
    def flipChess(self, chess: List[str]) -> int:
        rows, cols = len(chess), len(chess[0])

        def bfs(i, j):
            board = [list(row) for row in chess]
            q = deque([(i,j)])
            board[i][j] = "X"
            cnt = 0
            while q:
                x, y = q.popleft()
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
                    cur_x, cur_y = x+dx, y+dy
                    while 0<=cur_x<rows and 0<=cur_y<cols and board[cur_x][cur_y] == "O":
                        cur_x += dx
                        cur_y += dy
                    if 0<=cur_x<rows and 0<=cur_y<cols and board[cur_x][cur_y] == "X":
                        cur_x -= dx
                        cur_y -= dy
                        while cur_x != x or cur_y != y:
                            board[cur_x][cur_y] = "X"
                            cnt += 1
                            q.append((cur_x, cur_y))
                            cur_x -= dx
                            cur_y -= dy
            return cnt

        res = 0
        for i in range(rows):
            for j in range(cols):
                if chess[i][j] == ".":
                    res = max(res, bfs(i,j))

        return res

终于写出来了，找错找半天，bfs牛的

4. 玩具套圈⭐

超时

class Solution:
    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
        res = 0
        
        @lru_cache(None)
        def check(x1,y1,x2,y2):
            return dist((x1,y1),(x2,y2))
        
        for x1,y1,r1 in toys:
            if r1 > r:
                continue
            elif r1 == r:
                res += ([x1,y1] in circles)
            else:
                for x2, y2 in circles:
                    if check(x1,y1,x2,y2) + r1 <= r:
                        res += 1
                        break
        
        return res

一般情况下，暴力枚举超时时，需要枚举答案：

class Solution:
    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
        d = set((a,b) for a,b in circles)

        def check(x1, y1, dis):
            for x2 in range(x1-dis, x1+dis+1):
                for y2 in range(y1-dis, y1+dis+1):
                    if dist((x1,y1),(x2,y2)) > dis:
                        continue
                    if (x2,y2) in d:
                        return True
            return False

        res = 0
        for x1, y1, r1 in toys:
            if r1 > r:
                continue
            dis = r - r1
            if check(x1, y1, dis):
                res += 1

        return res

注意看题目的数据范围：

• 1 <= toys.length <= 10^4
• 0 <= toys[i][0], toys[i][1] <= 10^9
• 1 <= circles.length <= 10^4
• 0 <= circles[i][0], circles[i][1] <= 10^9
• 1 <= toys[i][2], r <= 10

这摆明了用 r 枚举，两层 for 才 10^2

5. 十字路口的交通