第一题
n = int(input()) dp = [[0] * n for _ in range(n)] half = n // 2 def func(i, j): if i + 1 > half: if j + 1> half: if i > j: return 6 else: return 7 else: if i + j + 1 > n: return 5 else: return 4 else: if j + 1 > half: if i + j + 1 > n: return 8 else: return 1 else: if i > j: return 3 else: return 2 for i in range(n): for j in range(n): if i == j&nbs***bsp;i + j + 1 == n: continue if n & 1: if i == half&nbs***bsp;bsp;j == half: continue dp[i][j] = func(i, j) for i in dp: print(*i, sep=' ')
刚发现考试时的代码细节上有问题(太难受了),修改之后大概能再多点分了,不过根据leetcode的经验,python写并查集效率挺低的,大概达不到70%
我习惯m是行n是列
m, n = map(int, input().split()) grid = [] for _ in range(m): grid += [list(map(int, input().split()))] class Solution: def UF(self, grid, m, n): self.count = 0 self.parent = [-1] * (m * n) self.size = [0] * (m * n) for i in range(m): for j in range(n): if grid[i][j] == 1: self.parent[i * n + j] = i * n + j self.size[i * n + j] = 1 self.count += 1 self.cnt = self.count def union(self, p, q): rootP = self.find(p) rootQ = self.find(q) if rootP == rootQ: return if self.size[rootP] > self.size[rootQ]: self.parent[rootQ] = rootP self.size[rootP] += self.size[rootQ] else: self.parent[rootP] = rootQ self.size[rootQ] += self.size[rootP] self.count -= 1 def find(self, x): while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] x = self.parent[x] return x def numIslands(self, grid): if len(grid) == 0&nbs***bsp;len(grid[0]) == 0: return 0 m, n = len(grid), len(grid[0]) self.UF(grid, m, n) for i in range(m): for j in range(n): if grid[i][j] == 1: for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: if 0 <= x < m and 0 <= y < n and grid[x][y] == 1: self.union(i * n + j, x * n + y) s = Solution() s.numIslands(grid) res = max(s.size) for i in range(m): for j in range(n): if grid[i][j] == 0: tmp_set = set() for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: if 0 <= x < m and 0 <= y < n and grid[x][y] == 1: tmp_set.add(s.find(x * n + y)) if len(tmp_set) == 0: continue tmp = sum(s.size[root] for root in tmp_set) + 1 if tmp > s.cnt: print(s.cnt) quit() res = max(res, tmp) print(res)
第三题只拿了60%就不用说了。。普通背包骗个分
第四题集合思想+最小公倍数,数学题
from itertools import combinations as comb from functools import reduce n, m = map(int, input().split()) primes = [] for _ in range(m): primes += [int(input())] def gcd(x, y): if x % y == 0: return y else: return gcd(y, x % y) def lcm(x, y): return x * y // gcd(x, y) res = 0 plus = 1 for i in range(1, m + 1): for j in comb(primes, i): tmp = reduce(lcm, j) res += plus * (n // tmp) plus = - plus print(res)
全部评论
(1) 回帖