每日一题 2.17-2.23
文章目录
题目来自 AcWing
AcWing 6122. 农夫约翰的奶酪块 | 原题链接
最容易想到的是开一个三维数l组用于记录方块状态，如果此时需要判断是否有一整个 $1\times1\times N$ 的区域被挖空，则对三个方向分别求前缀和，当 $(N,y,z)=0$ 或 $(x,N,z)=0$ 或 $(z,y,N)=0$ 时，可以填充的砖块方案数 $+1$。
这样看来，能否填充砖块实际上只与 $x=N$ 或 $y=N$ 或 $z=N$ 处的前缀和有关，因此做出优化：用三个二维数组分别表示三个维度的前缀和，或者说对应位置的剩余方块数量，例如 yz_projection[0][1] 就表示 $y=0,\space z=1$ 区域中剩余方块数量。当一个区域中剩余方块数为 0 时，可以填充的砖块方案数 $+1$。
1n, q = map(int, input().strip().split(" "))
2yz_projection = [[n for _ in range(n)] for _ in range(n)]
3xz_projection = [[n for _ in range(n)] for _ in range(n)]
4xy_projection = [[n for _ in range(n)] for _ in range(n)]
5
6count = 0
7for _ in range(q):
8 x, y, z = map(int, input().split(" "))
9
10 yz_projection[y][z] -= 1
11 if yz_projection[y][z] == 0:
12 count += 1
13
14 xz_projection[x][z] -= 1
15 if xz_projection[x][z] == 0:
16 count += 1
17
18 xy_projection[x][y] -= 1
19 if xy_projection[x][y] == 0:
20 count += 1
21
22 print(count)
6123. 哞叫时间 | 原题链接
这道题的要求是匹配 abb 形式且出现过至少 $f$ 次的字符串。但是题目的变数就在于原字符串中允许有一个字符的变化，在变化后能够满足要求的子串也会被统计。
首先最容易想到的就是暴力枚举。将原字符串中的每一个字符串按照字母表的顺序遍历一遍，然后再遍历新字符串查找 abb 字符串。这样做的时间复杂度是 $O(n\cdot15^n)$，题目给出的 $n$ 上限为 20000，这种做法肯定会超时。
将字符串中每一个位置都用全部字母试一遍显然不靠谱，因此可以换一种思路。在第一遍遍历原字符串时，分别记录满足 abb ?bb a?b ab? 格式字串的数量；对于可能有字符变化的子串，同时记录其待修改位置的字符。当遍历完时，足够数量的 abb 格式字串可以直接添加到结果中，随后处理可能有字符变化的字串时，如果某种字符刚好出现了 $f-1$ 次，那么说明其有可能是目标子串。这时需要将字串代回原字符串判断：将原字符串中对应的 abb 子串挖掉，如果剩余部分还可以出现 ?bb 或 a?b 或 ab? 子串，则其为目标子串。代码实现如下：
1n, f = map(int, input().strip().split())
2s = input().strip()
3chars = "abcdefghijklmnopqrstuvwxyz"
4moo = set()
5visited = dict()
6
7abb = dict()
8for i in range(1, n - 1):
9 if s[i] == s[i + 1] and s[i] != s[i - 1]:
10 count = abb.get(s[i - 1 : i + 2], 0)
11 count += 1
12 abb[s[i - 1 : i + 2]] = count
13 if count == f:
14 moo.add(s[i - 1 : i + 2])
15 visited[s[i - 1 : i + 2]] = True
16
17_bb, a_b, ab_ = dict(), dict(), dict()
18for i in range(1, n - 1):
19 if s[i] == s[i + 1]:
20 pos = _bb.get(s[i : i + 2], list())
21 pos.append(s[i - 1])
22 _bb[s[i : i + 2]] = pos
23 if s[i - 1] != s[i + 1]:
24 pos = a_b.get(s[i - 1] + s[i + 1], list())
25 pos.append(s[i])
26 a_b[s[i - 1] + s[i + 1]] = pos
27 if s[i - 1] != s[i]:
28 pos = ab_.get(s[i - 1 : i + 1], list())
29 pos.append(s[i + 1])
30 ab_[s[i - 1 : i + 1]] = pos
31
32for pat in _bb.keys():
33 mat = _bb[pat]
34 for ch in chars:
35 if ch == pat[0]:
36 continue
37 if mat.count(ch) == f - 1:
38 w = ch + pat
39 if visited.get(w, False):
40 continue
41 s_ = list(s)
42 for i in range(n - 2):
43 if s[i : i + 3] == w:
44 s_[i : i + 3] = [" ", " ", " "]
45 for i in range(n - 2):
46 if s_[i] != " " and s_[i + 1] == w[1] and s_[i + 2] == w[2]:
47 moo.add(w)
48 visited[w] = True
49 break
50
51for pat in a_b.keys():
52 mat = a_b[pat]
53 if mat.count(pat[-1]) == f - 1:
54 w = pat + pat[-1]
55 if visited.get(w, False):
56 continue
57 s_ = list(s)
58 for i in range(n - 2):
59 if s[i : i + 3] == w:
60 s_[i : i + 3] = [" ", " ", " "]
61 for i in range(n - 2):
62 if s_[i] == w[0] and s_[i + 1] != " " and s_[i + 2] == w[2]:
63 moo.add(w)
64 visited[w] = True
65 break
66
67for pat in ab_.keys():
68 mat = ab_[pat]
69 if mat.count(pat[-1]) == f - 1:
70 w = pat + pat[-1]
71 if visited.get(w, False):
72 continue
73 s_ = list(s)
74 for i in range(n - 2):
75 if s[i : i + 3] == w:
76 s_[i : i + 3] = [" ", " ", " "]
77 for i in range(n - 2):
78 if s_[i] == w[0] and s_[i + 1] == w[1] and s_[i + 2] != " ":
79 moo.add(w)
80 visited[w] = True
81 break
82
83print(len(moo))
84print(*sorted(list(moo)), sep="\n")
这段代码可以 AC，但是感觉思路有些绕。可以通过两层循环构造 abb 子串，而不是在原字符串中遍历得到。直接构造的时间复杂度为 $O(25\times26\times n)$，同样能够接受。当 $f>1$ 时，两层循环同样也不需要遍历全部 $26$ 个字母，因为被改变的原字符和目标字符都一定存在于原字符串中。
1n, f = map(int, input().strip().split())
2s = input().strip()
3
4if f > 1:
5 chars = tuple(set(s))
6else:
7 chars = "abcdefghijklmnopqrstuvwxyz"
8
9moo = set()
10for ci in chars:
11 for cj in chars:
12 if ci == cj:
13 continue
14 w = ci + cj + cj
15 cnt = 0
16 for i in range(n - 2):
17 if s[i : i + 3] == w:
18 cnt += 1
19 if cnt >= f:
20 moo.add(w)
21 break
22
23 if cnt >= f:
24 continue
25 elif cnt < f - 1:
26 continue
27 else:
28 s_ = list(s)
29 for i in range(n - 2):
30 if s[i : i + 3] == w:
31 s_[i : i + 3] = [" ", " ", " "]
32 for i in range(n - 2):
33 if (
34 (s_[i] == w[0] and s_[i + 1] == w[1] and s_[i + 2] != " ")
35 or (s_[i] == w[0] and s_[i + 1] != " " and s_[i + 2] == w[2])
36 or (s_[i] != " " and s_[i + 1] == w[1] and s_[i + 2] == w[2])
37 ):
38 moo.add(w)
39 break
40
41print(len(moo))
42print(*sorted(list(moo)), sep="\n")
6118. 蛋糕游戏 | 原题链接
我们称吃两边的奶牛为 A，吃中间的奶牛为 B。题目要求两头牛都走最优策略，那么最优策略是什么呢？对于先手 B 而言，其最优策略是保证自己合成的蛋糕不被 A 吃掉，所以每次都合成最中间的蛋糕；而对于 A 而言，只要 B 只合成最中间的蛋糕，那么他肯定吃不到合成的大蛋糕，所以他最好是吃当下能吃到的最大蛋糕（贪心）。不难看出，B 只要合并最中间的两个蛋糕就行，而 A 要考虑的就多了。找规律发现，A 可以吃 $\frac{n}{2}-1$ 个蛋糕，B 可以吃 $\frac{n}{2}+1$ 个蛋糕。A 要想吃掉最多的蛋糕，就是要让前 $i$ 个蛋糕和最后 $j$ 个蛋糕的和最大，且 $i+j=\frac{n}{2}-1$。A 吃尽可能多，就只能委屈 B 吃尽可能少，因此问题可以转换成找中间连续 $\frac{n}{2}+1$ 个数和的最小值，故利用前缀和来解决。
1t = int(input().strip())
2while t > 0:
3 n = int(input().strip())
4 cakes = list(map(int, input().strip().split()))
5 prefix_sum = [0] * (n + 1)
6 for i in range(1, n + 1):
7 prefix_sum[i] = prefix_sum[i - 1] + cakes[i - 1]
8 Bessie = float("inf")
9 for i in range(n // 2):
10 Bessie = min(Bessie, prefix_sum[i + n // 2 + 1] - prefix_sum[i])
11 Elsie = prefix_sum[-1] - Bessie
12 print(Bessie, Elsie)
13 t -= 1
6134. 哞叫时间II | 原题链接
这道题目的要求是在字符串中找到形如“abb”的字串，当然字串可以不连续。数据范围在 $10^6$，枚举三个字符的时间复杂度为 $O(n^3)$ 肯定会超时，而按照数据范围，最终设计出的算法时间复杂度应为 $O(n)$。我们不妨从暴力枚举开始一步步优化。
首先不难发现，最后两个字符相同。最外层循环确定最后一个字符时，如果还要从头开始遍历数组以确定第二个字符的位置，那么时间开销太大，并且重复而不必要。不难想到，一个简单快捷的方法就是将每一个字符的位置存储到字典中，这样可以节约一部分查找字符的时间。
此时还面临另一个问题：确定好最后两个 b 时，如何不重不漏地找到 a。例如对于 122122 这一序列，满足条件的 122 总共出现了 7 次，但是总计只有一种满足“abb”格式的字串。一种常见消除重复项的方法是使用集合。如果使用集合，算法仍然会有 $O(n^2k)$ 的时间复杂度，$k$ 为出现最多字符的次数。然而对于这道题来说，只考虑某一字符出现的最后两次最作为重复的 b 显然是更优选择，再考虑这一字符倒数第二次出现前共有多少不重复的字符，同时单独用一个数组记录在位置 i 时共有多少个不重复的字符。这些不重复的字符就是对于确定的 b，所有 abb 的个数。当然，如果某一个 b 出现了不只两次，还要在前面的统计中减去它自身。
1from collections import defaultdict
2
3n = int(input().strip())
4nums = tuple(map(int, input().strip().split()))
5num_pos = defaultdict(list)
6diff_cnt = [0] * n
7
8for i in range(n):
9 num_pos[nums[i]].append(i)
10 if len(num_pos[nums[i]]) == 1:
11 diff_cnt[i] = diff_cnt[i - 1] + 1
12 else:
13 diff_cnt[i] = diff_cnt[i - 1]
14
15count = 0
16for i in num_pos.keys():
17 if len(num_pos[i]) == 2:
18 pos = num_pos[i][0]
19 if pos > 0:
20 count += diff_cnt[pos - 1]
21 elif len(num_pos[i]) > 2:
22 pos = num_pos[i][-2]
23 count += diff_cnt[pos - 1] - 1
24
25print(count)
对于这些设计低时间复杂度算法的题目，可以从暴力枚举入手，找到暴力做法中重复且无用的操作，然后空间换时间降低时间复杂度。
6135. 奶牛体检 | 原题链接
这道题还是与序列有关的问题。题目给出一个数字序列，允许翻转一次其中一段连续子序列，记录新的序列与原序列有多少重合。最普通最暴力的做法是定义两个指针分别代表 l 和 r，从左到右遍历 l 与 r，将 l r 中间的部分翻转得到一个新的子序列，最后遍历新序列并于目标序列做比较。这种做法的时间复杂度为 $O(n^3)$。
最容易想到的优化是，在得到新的序列后，没有必要将新序列整体重新遍历，而是只用遍历改变了的部分（即 l r 之间）即可。通过创建前缀和数组，可以轻松获取l 到 r 区间内原序列与目标序列相同段的数量。用初始值减去这一数量再加上新序列这一段与目标序列相同的数量就是要求的数量。不过这样做的时间复杂度还是 $O(n^3)$。
降低算法时间复杂度的方法是找到算法中重复执行或者无效执行的部分。对于上面这种算法来讲，例如当 $l=3,r=4$ 时，区间 $[3,4]$ 会被翻转一次；当 $l=2,r=5$ 时，区间 $[3,4]$ 还会被翻转一次；当 $l=1,r=6$ 时，区间 $[3,4]$ 又会被翻转，而每次翻转同一区间得到的结果总是相同，所以这就是算法中重复计算的部分。优化的思路是，使用从中间向两侧的方式遍历 l r 指针，每次只翻转并且比较指针指向的两个元素，翻转后不还原，下一轮翻转的结果直接通过当前翻转的结果计算。
到这里算法就大体成型了。让一个中间指针遍历整个数组，然后 l r 指针从中间指针出发向两端移动。需要注意子序列长度为奇数与偶数的情况要分别讨论。实际操作时不需要真的翻转序列，只用计算两端的元素互换后多了少了哪些元素。这样时间复杂度为 $O(n^2)$
1from collections import defaultdict
2
3n = int(input().strip())
4original = tuple(map(int, input().strip().split()))
5expected = tuple(map(int, input().strip().split()))
6
7base = 0
8for i in range(n):
9 if original[i] == expected[i]:
10 base += 1
11
12count = defaultdict(int)
13for i in range(n):
14 l, r = i, i
15 changed = 0
16 while l >= 0 and r < n:
17 if l == r:
18 count[base] += 1
19 else:
20 if original[l] == expected[l]:
21 changed -= 1
22 if original[r] == expected[r]:
23 changed -= 1
24 if original[l] == expected[r]:
25 changed += 1
26 if original[r] == expected[l]:
27 changed += 1
28 count[base + changed] += 1
29 l -= 1
30 r += 1
31
32 l, r = i, i + 1
33 changed = 0
34 while l >= 0 and r < n:
35 if original[l] == expected[l]:
36 changed -= 1
37 if original[r] == expected[r]:
38 changed -= 1
39 if original[l] == expected[r]:
40 changed += 1
41 if original[r] == expected[l]:
42 changed += 1
43 count[base + changed] += 1
44 l -= 1
45 r += 1
46
47for i in range(n + 1):
48 print(count[i])