2025春季算法练习——Week 4
文章目录
题目来自 AcWing
842. 排列数字 | 原题链接
做做板子。
1n = int(input().strip())
2
3nums = [i + 1 for i in range(n)]
4used = [False] * (n + 1)
5used[0] = True
6res = list()
7
8
9def dfs(path):
10 if all(used):
11 res.append(path)
12 return
13
14 for num in nums:
15 if not used[num]:
16 used[num] = True
17 dfs(path + [num])
18 used[num] = False
19
20
21dfs(list())
22for arr in res:
23 print(*arr)
或者
1from itertools import permutations
2
3n = int(input().strip())
4perm = tuple(permutations(range(1, n + 1), n))
5for p in perm:
6 print(*p)
843. n-皇后问题 | 原题链接
这题做过：[USACO1.5] 八皇后 Checker Challenge。
1n = int(input().strip())
2col = [False] * n
3diag = [False] * (2 * n - 1)
4anti_diag = [False] * (2 * n - 1)
5ans = list()
6
7
8def dfs(depth, path):
9 if depth == n:
10 ans.append(path)
11 return
12
13 for i in range(n):
14 if not col[i] and not diag[i + depth] and not anti_diag[i - depth + n - 1]:
15 col[i] = True
16 diag[i + depth] = True
17 anti_diag[i - depth + n - 1] = True
18 dfs(depth + 1, path + [i])
19 col[i] = False
20 diag[i + depth] = False
21 anti_diag[i - depth + n - 1] = False
22
23
24dfs(0, list())
25for perm in ans:
26 for pos in perm:
27 line = ["."] * n
28 line[pos] = "Q"
29 print(*line, sep="")
30 print()
844. 走迷宫 | 原题链接
还是板子。
1import sys
2from collections import deque
3
4data = sys.stdin.read().strip().splitlines()
5n, m = map(int, data[0].strip().split())
6maze = [[-1 for _ in range(m)] for _ in range(n)]
7for i in range(1, n + 1):
8 for j, k in enumerate(map(int, data[i].strip().split())):
9 maze[i - 1][j] = k if k else -1
10
11directions = ((-1, 0), (1, 0), (0, 1), (0, -1))
12q = deque()
13maze[0][0] = 0
14q.append((0, 0))
15while q:
16 x, y = q.popleft()
17 if x == n - 1 and y == m - 1:
18 break
19 for dx, dy in directions:
20 nx, ny = x + dx, y + dy
21 if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == -1:
22 maze[nx][ny] = maze[x][y] + 1
23 q.append((nx, ny))
24print(maze[-1][-1])
845. 八数码 | 原题链接
定义每一种状态为一个节点，如果某种状态能够通过一次移动转移到另一种状态，则两种状态的节点之间有一条连接。再使用字典存储从初始状态到每种状态的最短路径。
1from collections import defaultdict, deque
2
3original = input().strip().split()
4oris = "".join(original)
5dest = "12345678x"
6if oris == dest:
7 print(0)
8 exit()
9
10directions = (-3, -1, 1, 3)
11status = defaultdict(lambda: -1)
12status[oris] = 0
13x = original.index("x")
14q = deque()
15q.append((oris, x))
16while q:
17 curr, x = q.popleft()
18 if curr == dest:
19 break
20 for dx in directions:
21 nx = x + dx
22 if 0 <= nx < 9:
23 if abs(dx) == 3 or (dx == 1 and x % 3 != 2) or (dx == -1 and x % 3 != 0):
24 l = list(curr)
25 l[x], l[nx] = l[nx], l[x]
26 news = "".join(l)
27 if status[news] == -1:
28 q.append((news, nx))
29 status[news] = status[curr] + 1
30print(status[dest])
如果原始数据中逆序对数量为奇数（不算 x），那么一定无法通过合法移动达到目标状态。判断逆序对数量可以在代码中加入一段
1count = 0
2for i in range(9):
3 for j in range(i + 1, 9):
4 if original[i] != "x" and original[j] != "x" and original[i] > original[j]:
5 count += 1
6if count % 2 == 1:
7 print(-1)
8 exit()
也可以用788. 逆序对的数量中的方法求逆序对数量：
1from collections import defaultdict, deque
2
3original = input().strip().split()
4oris = "".join(original)
5dest = "12345678x"
6if oris == dest:
7 print(0)
8 exit()
9
10
11def merge_sort(nums):
12 if len(nums) <= 1:
13 return nums, 0
14
15 mid = len(nums) // 2
16 l, lcnt = merge_sort(nums[:mid])
17 r, rcnt = merge_sort(nums[mid:])
18
19 tmp = list()
20 i = j = 0
21 cnt = 0
22 while i < len(l) and j < len(r):
23 if l[i] <= r[j]:
24 tmp.append(l[i])
25 i += 1
26 else:
27 tmp.append(r[j])
28 j += 1
29 cnt += len(l) - i
30
31 tmp.extend(l[i:])
32 tmp.extend(r[j:])
33 return tmp, cnt + lcnt + rcnt
34
35
36nums = [int(d) for d in original if d != "x"]
37if merge_sort(nums)[-1] % 2 != 0:
38 print(-1)
39 exit()
40
41
42directions = (-3, -1, 1, 3)
43status = defaultdict(lambda: -1)
44status[oris] = 0
45x = original.index("x")
46q = deque()
47q.append((oris, x))
48while q:
49 curr, x = q.popleft()
50 if curr == dest:
51 break
52 for dx in directions:
53 nx = x + dx
54 if 0 <= nx < 9:
55 if abs(dx) == 3 or (dx == 1 and x % 3 != 2) or (dx == -1 and x % 3 != 0):
56 l = list(curr)
57 l[x], l[nx] = l[nx], l[x]
58 news = "".join(l)
59 if status[news] == -1:
60 q.append((news, nx))
61 status[news] = status[curr] + 1
62print(status[dest])
1106. 山峰和山谷 | 原题链接
这道题还是典型的洪水填充，唯一需要做出修改的是，每次都要判断某一片地周围是否有更高以及更低的地方（分别用 has_higher 和 has_lower 记录）。另外所有地高度相同的情况需要特判。
1from collections import deque
2
3n = int(input().strip())
4field = [[0 for _ in range(n)] for _ in range(n)]
5for i in range(n):
6 line = list(map(int, input().strip().split()))
7 field[i] = line
8
9directions = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
10
11peak = 0
12valley = 0
13visited = set()
14for i in range(n):
15 for j in range(n):
16 if (i, j) not in visited:
17 has_higher = False
18 has_lower = False
19 q = deque()
20 q.append((i, j))
21 visited.add((i, j))
22 while q:
23 x, y = q.popleft()
24 for dx, dy in directions:
25 nx, ny = x + dx, y + dy
26 if 0 <= nx < n and 0 <= ny < n:
27 if (nx, ny) not in visited and field[nx][ny] == field[x][y]:
28 q.append((nx, ny))
29 visited.add((nx, ny))
30 elif field[nx][ny] > field[x][y]:
31 has_higher = True
32 elif field[nx][ny] < field[x][y]:
33 has_lower = True
34 if has_higher and not has_lower:
35 valley += 1
36 if has_lower and not has_higher:
37 peak += 1
38
39if peak == valley == 0:
40 print(1, 1)
41else:
42 print(peak, valley)
Python 不出意外地 TLE 了（21/22）……
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <queue>
5
6using namespace std;
7
8int field[1000][1000] = { 0 };
9bool visited[1000][1000] = { false };
10int directions[16] = { -1, -1, -1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 0, 1, 1 };
11int n;
12
13int main() {
14 scanf("%d", &n);
15 for (int i = 0; i < n; i++) {
16 for (int j = 0; j < n; j++) {
17 scanf("%d", &field[i][j]);
18 }
19 }
20
21 int peak = 0, valley = 0;
22 for (int i = 0; i < n; i++) {
23 for (int j = 0; j < n; j++) {
24 if (!visited[i][j]) {
25 bool has_higher = false;
26 bool has_lower = false;
27 queue<pair<int, int>> q;
28 q.push(make_pair(i, j));
29 visited[i][j] = true;
30 while (!q.empty()) {
31 int x = q.front().first;
32 int y = q.front().second;
33 q.pop();
34 for (int k = 0; k < 16; k += 2) {
35 int nx = x + directions[k];
36 int ny = y + directions[k + 1];
37 if (0 <= nx and nx < n and 0 <= ny and ny < n) {
38 if (!visited[nx][ny] and field[nx][ny] == field[x][y]) {
39 q.push(make_pair(nx, ny));
40 visited[nx][ny] = true;
41 }
42 else if (field[nx][ny] > field[x][y]) {
43 has_higher = true;
44 }
45 else if (field[nx][ny] < field[x][y]) {
46 has_lower = true;
47 }
48 }
49 }
50 }
51 if (has_higher && !has_lower) {
52 valley++;
53 }
54 if (has_lower && !has_higher) {
55 peak++;
56 }
57 }
58 }
59 }
60 if (peak == 0 and valley == 0) {
61 puts("1 1");
62 return 0;
63 }
64 printf("%d %d", peak, valley);
65 return 0;
66}
846. 树的重心 | 原题链接
关于树的重心：【知识总结】浅谈关于树的重心及其求法
我掐指一算，这道题用 Python 肯定过不了，就直接交的 Java。
这道题用到了树形 DP，令 dp[i] 表示以节点 i 为根节点的子树的节点数量，因此 dp[i] = sum(dp[children]) + 1。当删掉某一节点时，所有子树的联通节点数就是这一子树的节点数，而父节点所在树的联通节点数为总结点数减去当前节点所在子树的节点数，将每个删除每个节点时剩余联通节点最大值记为 max_cnt，所以有 max_cnt = n - dp[i]，而答案要求的就是所有 max_cnt 中的最小值。
1import java.util.*;
2
3public class Main {
4 static HashMap<Integer, ArrayList<Integer>> tree;
5 static int[] size;
6 static int min_cnt;
7 static int N;
8
9 public static void main(String[] args) {
10 Scanner sc = new Scanner(System.in);
11 N = sc.nextInt();
12 int n = N;
13 tree = new HashMap<>();
14 size = new int[n + 1];
15 min_cnt = Integer.MAX_VALUE;
16 while (n-- > 1) {
17 int u = sc.nextInt();
18 int v = sc.nextInt();
19
20 ArrayList<Integer> uNodes, vNodes;
21 if (tree.containsKey(u)) {
22 uNodes = tree.get(u);
23 } else {
24 uNodes = new ArrayList<>();
25 }
26 uNodes.add(v);
27 tree.put(u, uNodes);
28
29 if (tree.containsKey(v)) {
30 vNodes = tree.get(v);
31 } else {
32 vNodes = new ArrayList<>();
33 }
34 vNodes.add(u);
35 tree.put(v, vNodes);
36 }
37 sc.close();
38 dfs(-1, 1);
39 System.out.println(min_cnt);
40 }
41
42 public static void dfs(int last, int curr) {
43 int max_cnt = Integer.MIN_VALUE;
44 size[curr] += 1;
45 for (int next : tree.get(curr)) {
46 if (next != last) {
47 dfs(curr, next);
48 size[curr] += size[next];
49 max_cnt = Math.max(max_cnt, size[next]);
50 }
51 }
52 max_cnt = Math.max(max_cnt, N - size[curr]);
53 min_cnt = Math.min(min_cnt, max_cnt);
54 }
55}
847. 图中点的层次 | 原题链接
注意这是个有向图。
1import sys
2from collections import defaultdict, deque
3
4data = sys.stdin.read().strip().splitlines()
5graph = defaultdict(list)
6n, m = map(int, data[0].strip().split())
7nodes = [-1 for _ in range(n + 1)]
8for i in range(1, m + 1):
9 u, v = map(int, data[i].strip().split())
10 graph[u].append(v)
11
12nodes[1] = 0
13q = deque()
14q.append(1)
15while q:
16 node = q.popleft()
17 if node == n:
18 break
19 for nxt in graph[node]:
20 if nodes[nxt] == -1:
21 nodes[nxt] = nodes[node] + 1
22 q.append(nxt)
23print(nodes[n])
5. 多重背包问题 II | 原题链接
需要二进制优化的多重背包，注意优化后的每一组物品当作 01 背包处理，如果用滚动数组优化，那么 j 需要倒序遍历。
1import sys
2
3data = sys.stdin.read().strip().splitlines()
4N, V = map(int, data[0].strip().split())
5dp = [0 for _ in range(V + 1)]
6for i in range(1, N + 1):
7 vi, wi, si = map(int, data[i].strip().split())
8 k = 1
9 while si >= k:
10 for j in range(vi * k, V + 1)[::-1]:
11 dp[j] = max(dp[j], dp[j - k * vi] + k * wi)
12 si -= k
13 k <<= 1
14 if si > 0:
15 for j in range(vi * si, V + 1)[::-1]:
16 dp[j] = max(dp[j], dp[j - si * vi] + si * wi)
17print(dp[-1])
AcWing 9. 分组背包问题 | 原题链接
分组背包问题的遍历顺序：组、背包容量（倒序）、组内物品。先遍历背包容量再遍历物品，得到的就是某一背包容量下，组内物品的最大价值（如果有新的最大值会覆盖）。
1from collections import defaultdict
2
3N, V = map(int, input().strip().split())
4dp = [0 for _ in range(V + 1)]
5for _ in range(N):
6 items = list()
7 k = int(input().strip())
8 for __ in range(k):
9 v_, w_ = map(int, input().strip().split())
10 items.append((v_, w_))
11 for j in range(V + 1)[::-1]:
12 for v_, w_ in items:
13 if j >= v_:
14 dp[j] = max(dp[j],dp[j - v_] + w_)
15print(dp[-1])
8. 二维费用的背包问题 | 原题链接
1import sys
2
3data = sys.stdin.read().strip().splitlines()
4n, v, m = map(int, data[0].strip().split())
5dp = [[0 for _ in range(m + 1)] for _ in range(v + 1)]
6for i in range(1, n + 1):
7 vi, mi, wi = map(int, data[i].strip().split())
8 for v_ in range(vi, v + 1)[::-1]:
9 for m_ in range(mi, m + 1)[::-1]:
10 dp[v_][m_] = max(dp[v_][m_], dp[v_ - vi][m_ - mi] + wi)
11print(dp[-1][-1])