双指针、广搜与图论练习
文章目录
题目来自 AcWing
1238. 日志统计 | 原题链接
暴力做法：存储每个帖子在对应时间的点赞数，并计算前缀和，再遍历前缀和数组得到答案。时间复杂度和空间复杂度 $O(ND)$，可以通过 13/15 个测试点。
1from collections import defaultdict
2
3
4def check(nums, D, K):
5 prefs = [0] * int(1e5 + 1)
6 for i in range(1, int(1e5 + 1)):
7 prefs[i] = prefs[i - 1] + nums[i - 1]
8 if i >= D and prefs[i] - prefs[i - D] >= K:
9 return True
10 return False
11
12
13N, D, K = map(int, input().strip().split())
14d = defaultdict(lambda: [0] * int(1e5 + 1))
15for _ in range(N):
16 ts, di = map(int, input().strip().split())
17 d[di][ts] += 1
18 s = set()
19for k in d.keys():
20 if check(d[k], D, K):
21 s.add(k)
22print(*sorted(list(s)), sep="\n")
使用双指针解决的思路是，遍历一个长度为 $D$ 的时间段，用字典 $d$ 动态维护时间段内点赞数量，$d[id]$ 表示时间段内 $id$ 的点赞数量。使用 $i$ 遍历时间段的上界，$j$ 维护时间段的下界，每次遍历 $i$ 时修改 $j$，将时间段外的点赞数删除。
这样做的另一个好处是点赞信息的存储方式也不需要使用字典（数据量大时就是二维列表）了，直接将元组存储到列表并按照时间排序，相当于将时间离散化，节约存储空间。
1from collections import defaultdict
2
3N, D, K = map(int, input().strip().split())
4acts = list()
5for _ in range(N):
6 ts, di = map(int, input().strip().split())
7 acts.append((ts, di))
8acts.sort()
9
10ans = set()
11d = defaultdict(int)
12j = 0
13for i in range(N):
14 ts, di = acts[i]
15 d[di] += 1
16
17 while acts[j][0] <= ts - D:
18 d[acts[j][1]] -= 1
19 j += 1
20
21 if d[di] >= K:
22 ans.add(di)
23
24print(*sorted(list(ans)), sep="\n")
1101. 献给阿尔吉侬的花束 | 原题链接
用广搜找最短路径。
1from collections import deque
2import sys
3
4directions = ((0, -1), (0, 1), (-1, 0), (1, 0))
5
6t = int(input().strip())
7for _ in range(t):
8 r, c = map(int, input().strip().split())
9 maze = sys.stdin.read(r * (c + 1)).strip().split("\n")
10 for i in range(r):
11 maze[i] = list(maze[i])
12 for j in range(c):
13 if maze[i][j] == 'S':
14 start = (i, j)
15 maze[i][j] = 0
16 if maze[i][j] == 'E':
17 dest = (i, j)
18
19 queue = deque()
20 queue.append(start)
21 ans = "oop!"
22 while queue:
23 x, y = queue.popleft()
24 if (x, y) == dest:
25 ans = maze[x][y]
26 break
27
28 for dx, dy in directions:
29 nx, ny = x + dx, y + dy
30 if 0 <= nx < r and 0 <= ny < c and (maze[nx][ny] == '.' or maze[nx][ny] == 'E'):
31 maze[nx][ny] = maze[x][y] + 1
32 queue.append((nx, ny))
33
34 print(ans)
sys.stdin.read(r * (c + 1)) 可以保证刚好读取 $r$ 行 $c$ 列的字符（包括换行符）。
1113. 红与黑 | 原题链接
这道题之前做过：NEFU OJ - Problem 784 | 白与黑-搜索
1from collections import deque
2
3directions = ((0, -1), (0, 1), (1, 0), (-1, 0))
4
5while True:
6 c, r = map(int, input().strip().split())
7 if c == r == 0:
8 exit()
9 maze = list()
10 for i in range(r):
11 row = input().strip()
12 for j in range(c):
13 if row[j] == '@':
14 start = (i, j)
15 maze.append(list(row))
16
17 ans = 0
18 queue = deque()
19 queue.append(start)
20 while queue:
21 x, y = queue.popleft()
22 ans += 1
23 for dx, dy in directions:
24 nx, ny = x + dx, y + dy
25 if 0 <= nx < r and 0 <= ny < c and maze[nx][ny] == '.':
26 maze[nx][ny] = 0
27 queue.append((nx, ny))
28 print(ans)
1224. 交换瓶子 | 原题链接
- 方法一：枚举 - 时间复杂度 $O(n^2)$
每一个瓶子的位置必须与其编号相符，否则就将其换到“应许之地”。统计交换次数即可。
1n = int(input())
2bottles = list(map(lambda x: int(x) - 1, input().strip().split()))
3
4ans = 0
5for i in range(n):
6 while bottles[i] != i:
7 bottles[bottles[i]], bottles[i] = bottles[i], bottles[bottles[i]]
8 ans += 1
9print(ans)
- 方法二：置换群
在数列 $a$ 中创建从 $a_i$ 指向 $i$ 的边，因为每一个点的出度为 1，入度也为 1，所以这些点最终能形成若干个环。在环内交换元素时，在最理想情况下一定能保证有一个数回到对应位置，这一节点形成自环，环的总数增加 1。因此用目标状态下环的数量（$n$ 个自环）减去最初状态下环的数量（也包括自环）即为需要交换的最小次数。
1n = int(input())
2bottles = list(map(lambda x: int(x) - 1, input().strip().split()))
3
4record = [False] * n
5rings = 0
6has_ring = False
7for i in range(n):
8 b = i
9 while not record[bottles[b]]:
10 record[bottles[b]] = True
11 b = bottles[b]
12 has_ring = True
13 if has_ring:
14 rings += 1
15 has_ring = False
16
17print(n - rings)
为了避免重复计数，每遍历到一个节点都要记录。
1240. 完全二叉树的权值 | 原题链接
将二叉树存储到堆中，同时层序遍历二叉树，用字典记录每一层的权值。
1from collections import deque, defaultdict
2
3n = int(input().strip())
4tree = [0] + list(map(int, input().strip().split()))
5for i in range(21):
6 if 2 ** i <= n < 2 ** (i + 1):
7 memo = defaultdict(int)
8
9queue = deque()
10queue.append((1, 1))
11while queue:
12 index, depth = queue.popleft()
13 memo[depth] += tree[index]
14
15 if index << 1 <= n:
16 queue.append((index << 1, depth + 1))
17 if index << 1 | 1 <= n:
18 queue.append((index << 1 | 1, depth + 1))
19
20max_val = -float("inf")
21depth = -1
22for i in memo.keys():
23 if memo[i] > max_val:
24 max_val = memo[i]
25 depth = i
26
27print(depth)
1096. 地牢大师 | 原题链接
广搜找最短路。
1from collections import deque
2import sys
3
4directions = ((0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 0, -1), (0, -1, 0), (-1, 0, 0))
5
6while True:
7 L, R, C = map(int, input().strip().split())
8 if L == R == C == 0:
9 exit()
10
11 data = sys.stdin.read((R * (C + 1) + 1) * L).strip().split("\n")
12 maze = [[[0 for _ in range(C)] for _ in range(R)] for _ in range(L)]
13 for i in range(L):
14 for j in range(R):
15 for k in range(C):
16 maze[i][j][k] = data[i * (R + 1) + j][k]
17 if data[i * (R + 1) + j][k] == 'S':
18 start = (i, j, k)
19 if data[i * (R + 1) + j][k] == 'E':
20 dest = (i, j, k)
21
22 queue = deque()
23 queue.append(start)
24 maze[start[0]][start[1]][start[2]] = 0
25 found = False
26 while queue:
27 x, y, z = queue.popleft()
28 if (x, y, z) == dest:
29 print(f"Escaped in {maze[x][y][z]} minute(s).")
30 found = True
31 break
32 for dx, dy, dz in directions:
33 nx, ny, nz = dx + x, dy + y, dz + z
34 if 0 <= nx < L and 0 <= ny < R and 0 <= nz < C and (maze[nx][ny][nz] == '.' or maze[nx][ny][nz] == 'E'):
35 maze[nx][ny][nz] = maze[x][y][z] + 1
36 queue.append((nx, ny, nz))
37 if not found:
38 print("Trapped!")
1233. 全球变暖 | 原题链接
这道题需要使用广搜找连通块，而且要搜两遍。第一遍搜索要统计有多少岛屿同时记录海平面上升后的海陆情况，第二遍搜索时统计剩下的岛屿数量。第一遍搜索的时候需要将被淹没的陆地用另一种符号记录（我使用了 @），这样避免第二遍统计时出错。例如对于海平面上升前的岛屿：
1.......
2..#.#..
3.#####.
4..#.#..
5.......
海平面上升后会变成：
1.......
2.......
3..#.#..
4.......
5.......
原先的一个岛屿并没有沉没，但是被海水切割成两个岛屿了。在这种情况下，答案是 0 而非 1，更不是 -1。
1from collections import deque
2import sys
3
4directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
5
6n = int(input().strip())
7maps = sys.stdin.read(n * (n + 1)).strip().split("\n")
8for i in range(n):
9 maps[i] = list(maps[i])
10
11init = 0
12for i in range(n):
13 for j in range(n):
14 if maps[i][j] == '#':
15 init += 1
16 q = deque()
17 maps[i][j] = '%'
18 q.append((i, j))
19 while q:
20 x, y = q.popleft()
21 for dx, dy in directions:
22 nx, ny = x + dx, y + dy
23 if 0 <= nx < n and 0 <= ny < n and maps[nx][ny] == '.':
24 maps[x][y] = '@'
25 if 0 <= nx < n and 0 <= ny < n and maps[nx][ny] == '#':
26 maps[nx][ny] = '%'
27 q.append((nx, ny))
28
29res = 0
30for i in range(n):
31 for j in range(n):
32 if maps[i][j] == '%':
33 res += 1
34 q = deque()
35 maps[i][j] = '#'
36 q.append((i, j))
37 while q:
38 x, y = q.popleft()
39 for dx, dy in directions:
40 nx, ny = x + dx, y + dy
41 if 0 <= nx < n and 0 <= ny < n and (maps[nx][ny] == '%' or maps[nx][ny] == '@'):
42 maps[nx][ny] = '#'
43 q.append((nx, ny))
44
45print(init - res)
1207. 大臣的旅费 | 原题链接
王国里有 $n$ 座城市和 $n-1$ 条公路，并且“如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的”，根据这些信息可以推断出整个王国的城市和公路是树形，而这道题要求的最大路费，实际上就是要求出树的直径 $d$，再对等差数列求和。
树的直径就是指树中任意两个节点简单路径的最长距离。在树中任取一个节点，搜索与其简单路径最长的节点 $v$，再从 $v$ 出发找到一条最长的简单路径，这条路径的长度就是树的直径。
我最开始尝试将树的信息存储进邻接矩阵，然后通过两次深搜找出树的直径。这样会在通过 7/12 个测试点后 MLE。
1t = int(input().strip())
2mat = [[0 for _ in range(t)] for _ in range(t)]
3for _ in range(t - 1):
4 a, b, d = map(int, input().strip().split())
5 a -= 1
6 b -= 1
7 mat[a][b] = d
8 mat[b][a] = d
9
10def dfs(curr, dist, visited, path):
11 if all(visited):
12 return
13
14 max_dist = 0
15 for i in range(t):
16 if mat[curr][i] != 0 and not visited[i]:
17 visited[i] = True
18 d, p = dfs(i, mat[curr][i], visited, path + [i])
19 if d > max_dist:
20 max_dist = d
21 path = p
22 visited[i] = False
23 return dist + max_dist, path
24
25visited = [False] * t
26visited[0] = True
27d, p = dfs(0, 0, visited, list())
28node = p[-1]
29
30visited = [False] * t
31visited[node] = True
32d, p = dfs(node, 0, visited, list())
33print((21 + d) * d // 2)
对于一些节点稀疏的树，这样做未免太过于浪费空间了。因此我又尝试使用 dict 表示邻接矩阵以实现对邻接矩阵的离散化，从而节省大量空间。这样确实不会有 MLE，但是此时又出现了另一个问题：如果在极限数据中，$10^5$ 个节点组成一个双链表，那么 dfs 就要递归 $10^5$ 层，而 Python 递归上限是 $1000$ 层，修改上限还会 Segmentation Fault。
1t = int(input().strip())
2mat = [[0 for _ in range(t)] for _ in range(t)]
3for _ in range(t - 1):
4 a, b, d = map(int, input().strip().split())
5 a -= 1
6 b -= 1
7 mat[a][b] = d
8 mat[b][a] = d
9
10def dfs(curr, dist, visited, path):
11 if all(visited):
12 return
13
14 max_dist = 0
15 for i in range(t):
16 if mat[curr][i] != 0 and not visited[i]:
17 visited[i] = True
18 d, p = dfs(i, mat[curr][i], visited, path + [i])
19 if d > max_dist:
20 max_dist = d
21 path = p
22 visited[i] = False
23 return dist + max_dist, path
24
25visited = [False] * t
26visited[0] = True
27d, p = dfs(0, 0, visited, list())
28node = p[-1]
29
30visited = [False] * t
31visited[node] = True
32d, p = dfs(node, 0, visited, list())
33print((21 + d) * d // 2)
看来得用 bfs 来解决了，使用两次 bfs 找出树的直径。不过用 bfs 来找最长路径听起来很奇怪吧！使用 bfs 求最短路径时，是找到符合条件的节点就立刻跳出循环。而用 bfs 求最长路径时，则是要将整个树遍历完。当遍历到叶节点时，也就是当前节点没有子节点可以添加到队列时，获取当前走过的距离，并与一个动态维护的最大距离比较。
1from collections import defaultdict, deque
2
3t = int(input().strip())
4mat = defaultdict(list)
5for _ in range(t - 1):
6 a, b, d = map(int, input().strip().split())
7 a -= 1
8 b -= 1
9 mat[a].append((b, d))
10 mat[b].append((a, d))
11
12def bfs(curr):
13 last_node = -1
14 max_dist = 0
15 q = deque()
16 q.append((curr, 0))
17 visited[curr] = True
18 while q:
19 curr, dist = q.popleft()
20 has_child = False
21 for nxt, di in mat[curr]:
22 if not visited[nxt]:
23 q.append((nxt, dist + di))
24 visited[nxt] = True
25 has_child = True
26 if not has_child:
27 if dist > max_dist:
28 max_dist = dist
29 last_node = curr
30 return max_dist, last_node
31
32visited = [False] * t
33visited[0] = True
34d, p = bfs(0)
35
36visited = [False] * t
37d, p = bfs(p)
38print((21 + d) * d // 2)
826. 单链表 | 原题链接
数据结构基础。需要注意，$k$ 是指第 $k$ 个插入的元素而非链表中的第 $k$ 个元素。
1class Node:
2
3 def __init__(self, val, seq):
4 self.val = val
5 self.seq = seq
6 self.nxt = None
7
8 def __repr__(self):
9 return self.val
10
11
12class LinkedList:
13
14 def __init__(self):
15 self.head = None
16
17 def __repr__(self):
18 curr = self.head
19 l = list()
20 while curr is not None:
21 l.append(str(curr))
22 curr = curr.nxt
23 return ' '.join(l)
24
25
26t = int(input().strip())
27linked_list = LinkedList()
28seq = 0
29for _ in range(t):
30 ops = input().strip().split()
31
32 if ops[0] == 'H':
33 seq += 1
34 node = Node(ops[1], seq)
35 node.nxt = linked_list.head
36 linked_list.head = node
37
38 elif ops[0] == 'D':
39 if ops[1] == '0':
40 linked_list.head = linked_list.head.nxt
41 else:
42 curr = linked_list.head
43 while curr is not None:
44 if curr.seq == int(ops[1]):
45 if curr.nxt is not None:
46 curr.nxt = curr.nxt.nxt
47 break
48 curr = curr.nxt
49
50 elif ops[0] == 'I':
51 seq += 1
52 curr = linked_list.head
53 while curr is not None:
54 if curr.seq == int(ops[1]):
55 node = Node(ops[2], seq)
56 node.nxt = curr.nxt
57 curr.nxt = node
58 break
59 curr = curr.nxt
60
61print(linked_list)
额……这样做能通过 8/10 个测试点然后超时，因为每一次需要访问某个节点时，程序都会从 head 迭代到目标节点，这样效率很低。我们还可以在字典中存储 seq -> Node 的信息，这样需要访问第 k 个插入的节点时可以直接访问。
1class Node:
2
3 def __init__(self, val, seq):
4 self.val = val
5 self.seq = seq
6 self.nxt = None
7
8 def __repr__(self):
9 return self.val
10
11
12class LinkedList:
13
14 def __init__(self):
15 self.head = None
16 self.seq = dict()
17
18 def __repr__(self):
19 curr = self.head
20 l = list()
21 while curr is not None:
22 l.append(str(curr))
23 curr = curr.nxt
24 return ' '.join(l)
25
26
27t = int(input().strip())
28linked_list = LinkedList()
29seq = 0
30for _ in range(t):
31 ops = input().strip().split()
32
33 if ops[0] == 'H':
34 seq += 1
35 node = Node(ops[1], seq)
36 node.nxt = linked_list.head
37 linked_list.head = node
38 linked_list.seq[seq] = node
39
40 elif ops[0] == 'D':
41 if ops[1] == '0':
42 linked_list.head = linked_list.head.nxt
43 else:
44 curr = linked_list.seq[int(ops[1])]
45 if curr.nxt is not None:
46 curr.nxt = curr.nxt.nxt
47
48 elif ops[0] == 'I':
49 seq += 1
50 curr = linked_list.seq[int(ops[1])]
51 node = Node(ops[2], seq)
52 linked_list.seq[seq] = node
53 node.nxt = curr.nxt
54 curr.nxt = node
55
56print(linked_list)