2024.4.28 美团笔试复盘

算法

美团0427笔试

美团笔试，上强度了！（0427春招实习笔试真题解析）

1 小美换团

小美拿到了一个字符串，她准备把其中所有的"mei"子串替换为"tuan"子串，你能帮帮她吗？

输入描述

一个仅由小写字母组成的字符串。长度不超100000

输出描述

修改后的字符串。

示例 1

输入

meituan

输出

tuantuan

思路与代码

打卡题。直接模拟即可。

1
2
s = input().replace("mei","tuan")
print(s)

2 小美的特殊矩形

小美拿到了一个字符矩阵，她定义一个矩形区域是“特殊的”，当且仅当这个矩形区域中没有两个相同的字符。 现在小美想知道，有多少个2行2列的矩阵区域是特殊的？

输入描述

第一行输入两个正整数n,m，代表矩阵的行数和列数。

接下来的n行，每行输入一个长度为m的、仅由小写字母组成的字符串，代表小美拿到的字符矩阵。

1<=n,m<=200

输出描述

一个整数，代表"特殊的"矩形区域的数量。

示例 1

输入

1
2
3
4
2 3
abb
aac

输出

0

思路与代码

模拟题。 直接枚举所有的2*2的子矩阵，判断是否存在重复的字符即可。

1
2
3
4
5
6
7
8
9
10
11
12
n,m = list(map(int,input().split()))
matrix = [list(input()) for _ in range(n)]
res = 0
for i in range(n-1):
    for j in range(m-1):
        s = set()
        for x in range(2):
            for y in range(2):
                s.add(matrix[i+x][j+y])
        if len(s) == 4:
            res += 1
print(res)

3 小美的数组合并

小美拿到了一个数组，她每次操作可以将两个相邻元素ai合并为一个元素，合并后的元素为原来两个元素之和。小美希望最终数组的最小值不小于k。她想知道有多少种不同的合并结果？

输入描述

第一行输入两个正整数n,k，代表数组大小和数组的最大值。

第二行输入个正整数ai，代表小美拿到的数组。

1<=n,k,ai<=200

输出描述

输出一个整数，代表小美可以得到多少种不同的结果。由于结果可能很大，输出对10^9+7取模的结果。

示例 1

输入

1
2
4 4
2 3 4 5

输出

4

说明

可能得到的数组有：[5,4,5]、[9,5]、[5,9]、[14]这四种。

思路与代码

动态规划。

对于每一个数字来说，如果当前和是小于k的，那么只能选择合并；否则的话，合并和不合并都可以。

f[i,j]考虑i往后的数字，当前和是p，组成满足条件的方案数有多少。

推导如下：

1
2
3
4
if j>=k: 
	f[i,j] += f[i+1,j+a[i]] + f[i+1,a[i]] 
else:  
	f[i,j] = f[i+1,j+a[i]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 读取输入的整数 n 和 k
n, k = list(map(int, input().split()))
# 读取输入的数组 arr，并将其转换为整数列表
arr = list(map(int, input().split()))

# 定义一个常量 MOD，用于在计算过程中取模以避免整数溢出
MOD = 10 ** 9 + 7

# 初始化动态规划数组 dp，其大小为 (n+1) x (sum(arr)+1)，所有值初始化为 -1
# dp[i][j] 表示在考虑前 i 个数，当前取到的总和为 j 时的方法数
dp = [[-1] * (sum(arr) + 1) for _ in range(n + 1)]

# 定义深度优先搜索函数 dfs，参数 i 表示当前考虑的数组元素索引，参数 p 表示当前的累计和
def dfs(i, p):
    # 如果已经到达数组末尾，则根据当前累计和 p 是否大于等于 k 来返回 1 或 0
    if i == n:
        return 1 if p >= k else 0

    # 如果当前状态已经计算过，则直接返回结果
    if dp[i][p] != -1:
        return dp[i][p]

    # 初始化方法数 cnt 为 0
    cnt = 0

    # 如果当前累计和 p 大于等于 k，则可以选择取当前元素，或者不取
    if p >= k:
        cnt += dfs(i + 1, arr[i])  # 不取当前元素的情况
        cnt += dfs(i + 1, p + arr[i])  # 取当前元素的情况
    # 如果当前累计和 p 小于 k，则只能选择取当前元素
    else:
        cnt += dfs(i + 1, p + arr[i])

    # 在计算过程中，为了减少计算量，每次加和后都进行取模操作
    cnt %= MOD
    # 将当前状态的计算结果存储在 dp 数组中，以便后续使用
    dp[i][p] = cnt
    # 返回当前状态的方法数
    return dp[i][p]

# 调用 dfs 函数，从索引 0 开始，初始累计和为 0，并打印结果
print(dfs(0, 0))

这个的终结条件还是比较难想出来的。看最后一个的结果，然后进行回收。重点是中间进行递归的条件，如果当前累计和 p 大于等于 k，则可以选择取当前元素，或者不取；如果当前累计和 p 小于 k，则只能选择取当前元素。

这个动态规划的数组大小也是比较重要的一个，dp[i][j] 表示在考虑前 i 个数，当前取到的总和为 j 时的方法数。

4 小美的树上联通块

小美拿到了一棵树，其中有一些节点被染成红色。

小美定义一个红色连通块的权值为：所有节点编号乘积的因子数量。

小美想知道，所有红色连通块的权值之和是多少？由于答案过大，请对10^9+7取模。

输入描述

第一行输入一个正整数n，代表节点数量。

第二行输入一个长度为n的、仅由’R’和’W’组成的字符串，第i个字符为’R’代表i号节点被染成红色，'W’代表未被染色。保证至少有一个节点被染成红色。

接下来的n-1行，每行输入2个正整数u,v，代表u号节点和v号节点有一条边连接。

1<=n<=10^5

1<=u,v<=n

输出描述

一个整数，代表所有红色连通块的权值之和。

示例 1

输入

1
2
3
4
3
WRR
1 2
2 3

输出

4

说明

只有一个红色连通块，权值为6的因子数量：1、2、3、6共4个。

思路与代码

树的遍历+因子定理。

公式1：因子计算，算乘积的因子数(k1+1)×(k2+1)×…×(kr+1)，其中k1,k2,…,kr 是各个质因数的总幂次。

所以我们dfs遍历每一个红色的节点，然后分解每一个节点的质因子，统计当前连通块的质因子的数量，使用公式1进行运算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from collections import defaultdict

# 读取输入的整数 n，表示节点的数量
n = int(input())
# 读取输入的字符串 colors，表示每个节点的颜色，'R' 表示红色，'W' 表示白色
colors = input()
# 初始化邻接表 graph，表示图中的边
graph = [[] for _ in range(n + 1)]

# 读取 n-1 行输入，构建树的邻接表
for _ in range(n - 1):
    u, v = list(map(int, input().split()))
    graph[u].append(v)
    graph[v].append(u)

# 定义一个大数 MOD，用于在计算过程中取模
MOD = 10 ** 9 + 7

# 定义 get_factors 函数，用于求一个数的所有质因子
def get_factors(n):
    prime_factors = []
    # 将 n 除以 2，直到 n 为奇数
    while n % 2 == 0:
        prime_factors.append(2)
        n //= 2
    # 从 3 开始到 n 的平方根，每次增加 2（跳过偶数），检查每个数是否是 n 的质因子
    for i in range(3, int(n ** 0.5) + 1, 2):
        while n % i == 0:
            prime_factors.append(i)
            n //= i
    # 如果 n 大于 2，说明 n 是质数，将其加入质因子列表
    if n > 2:
        prime_factors.append(n)
    return prime_factors

# 初始化一个布尔数组 vst，用于标记节点是否已访问
vst = [False] * (n + 1)

# 定义 dfs 函数，用于深度优先搜索图中的节点，并计算质因子的个数
def dfs(u, f, factors):
    vst[u] = True  # 标记节点 u 为已访问
    primes = get_factors(u)  # 获取节点 u 的质因子
    for p in primes:  # 对每个质因子进行计数
        factors[p] += 1
    for v in graph[u]:  # 遍历节点 u 的所有邻居节点
        if v == f or colors[v - 1] == 'W':  # 如果是父亲节点或颜色为白色，则跳过
            continue
        dfs(v, u, factors)  # 对邻居节点进行深度优先搜索
    return factors  # 返回质因子计数

res = 0  # 初始化结果变量
# 从 1 到 n 遍历每个节点
for i in range(1, n + 1):
    if colors[i - 1] == 'R' and not vst[i]:  # 如果节点颜色为红色且未访问
        factors = dfs(i, -1, defaultdict(int))  # 从节点 i 开始进行深度优先搜索，并计算质因子个数
        ans = 1  # 初始化答案变量
        for p in factors:  # 对每个质因子进行处理
            ans = ans * (factors[p] + 1) % MOD  # 更新答案
        res = (res + ans) % MOD  # 更新结果变量

# 打印最终结果
print(res)

首先，这个就得先理解题意，红色连通块的权值为所有节点编号乘积的因子数量。也就是节点编号相乘，之后再求因子数量。例如，4的因子为2、2，也就是获取对应的质因子数目。

这个因子定理是挺需要记住的，他的核心逻辑就是先统计每个因子的数目，例如2有k1个、3有个k2个，以此类推。最终，乘积的因子数(k1+1)×(k2+1)×…×(kr+1)，其中k1,k2,…,kr 是各个质因数的总幂次。

这里还有一个记录是否访问过的数组，如果访问过了就代表这个节点在这个联通块中，在刚才的计算中以及考虑进去了，就不需要重新考虑了。也就可以跳过。

5 小苯的树上询问

小苯有一个 n 个节点的无向树，每条边都有权重 wi，他将进行 q 次操作，每次操作是以下之一：

  1. 删除第 i 条边。
  2. 询问从 u 号点到 v 号点的最短路径上所有边的边权异或和。

小苯希望你帮他处理完所有的操作，并对所有操作 2 ，输出对应的异或和。

输入描述

1
2
3
4
5
6
7
第一行两个正整数 n,q (1<=q<=n<=2*10^5)。
接下来 n-1 行，每行三个正整数 ui,vi,wi(1<=ui,vi<=n), (ui != vi), (1<=wi<=10^9)，表示 ui 到 vi 连了一条权重为 wi 的边。
接下来 q 行，每行代表一次操作，首先输入一个正整数 op(1<=op<=2) 表示操作种类。
如果 op=1，则再输入一个正整数 i 表示删除第 i 条边。（保证每条边最多被删除一次）
如果 op=2，则再输入两个正整数 u,v(1<=u,v<=n)，表示询问 u 号点到 v 号点的最短路径中，所有边权的异或和。
（注意：如果从 u 没法到达 v，则输出 -1。）

输出描述

输出包含若干行。

每行一个整数，对于每次操作 2，输出 u 到 v 的最短路径上所有边权的异或和，路径不存在输出 -1。

示例 1

输入

1
2
3
4
5
6
7
8
9
10
11
5 5
1 2 1
2 3 2
3 4 3
3 5 3
2 1 2
2 1 4
2 4 5
1 2
2 1 4

输出

1
2
3
4
5
1
0
0
-1

说明

1
2
3
4
5
6
7
样例的树如图所示，前三次询问的结果分别为：
1 号点到 2 号点路径异或和为：1
1 号点到 4 号点路径异或和为：1 ^ 2 ^ 3 = 0
4 号点到 5 号点路径异或和为：3 ^ 3 = 0
第五步操作删除第 2 条边，即变为下图：

接着询问 1 好点到 4 号点的路径异或和，由于无法到达，因此输出 -1。

思路与代码

lca（最近公共祖先）+倍增优化+并查集+逆向思维。

tip1：树上的最短路其实就是两个点的路径。 tip2：异或运算符合交换律。

思路如下： 1.对于删除的边，我们可以使用并查集+逆向遍历来判断是否连通。 2.对于连通的点，我们使用lca算法来检查两个节点之间的最近公共祖先，并且记录路径的异或和的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
# 读取输入的整数 n 和 q
n, q = list(map(int, input().split()))

# 初始化邻接表 G，表示图中的边
G = [[] for _ in range(n + 1)]

# 初始化边的列表 edges，用于存储所有的边
edges = []

# 读取 n-1 行输入，构建图的邻接表和边的列表
for _ in range(n - 1):
    u, v, w = list(map(int, input().split()))
    edges.append((u, v, w))
    G[u].append((v, w))
    G[v].append((u, w))

# 初始化操作列表 ops，用于存储 q 个操作
ops = []
for _ in range(q):
    ops.append(list(map(int, input().split())))

# 定义常量 N，表示节点的总数加 1
N = n + 1

# 初始化全局变量
# pre 数组，用于存储到达每个节点的路径上的异或和
# par 数组，用于存储重根路径上的父节点
# bit 数组，用于存储深度的二进制表示中每一位的值
# f 数组，用于存储重根路径上的祖先节点
# depth 数组，用于存储每个节点的深度
pre = [0] * N
par = [0] * N
bit = [0] * 30
f = [[0] * 30 for _ in range(N)]
depth = [0] * N

# 定义 dfs 函数，用于深度优先搜索，计算每个节点的深度和重根路径上的祖先节点
def dfs(u, parent):
    depth[u] = depth[parent] + 1
    f[u][0] = parent
    i = 1
    # 利用二进制提升，计算更高层次的祖先节点
    while i < 30 and bit[i] <= depth[u]:
        f[u][i] = f[f[u][i - 1]][i - 1]
        i += 1
    # 遍历节点 u 的所有邻居节点
    for v, w in G[u]:
        if v != parent:
            dfs(v, u)

# 定义 lca 函数，用于计算两个节点的最近公共祖先
def lca(x, y):
    # 确保 x 的深度小于等于 y 的深度
    if depth[x] < depth[y]:
        x, y = y, x
    # 从高层次到低层次，检查两个节点的祖先节点是否相同
    for i in range(29, -1, -1):
        if depth[x] - depth[y] >= bit[i]:
            x = f[x][i]
    # 如果 x 和 y 相等，则它们是同一个节点，返回 x
    if x == y:
        return x
    # 从高层次到低层次，将 x 和 y 同时上溯，直到它们的祖先节点不相同
    for i in range(29, -1, -1):
        if f[x][i] != f[y][i]:
            x = f[x][i]
            y = f[y][i]
    # 返回 x 和 y 的最近公共祖先
    return f[x][0]

# 定义 dfs_xor 函数，用于计算到达每个节点的路径上的异或和
def dfs_xor(u, fa):
    par[u] = fa
    for v, w in G[u]:
        if v != fa:
            pre[v] = pre[u] ^ w
            dfs_xor(v, u)

# 从节点 1 开始进行深度优先搜索，计算深度和重根路径上的祖先节点
dfs(1, -1)

# 计算到达每个节点的路径上的异或和
dfs_xor(1, -1)

# 初始化并查集的 parent 数组，用于存储节点的父节点
parent = [i for i in range(n + 1)]

# 定义 find 函数，用于查找节点 x 的根节点
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

# 定义 union 函数，用于合并两个节点的集合
def union(x, y):
    x, y = find(x), find(y)
    if x == y:
        return
    parent[x] = y

# 初始化删除边的集合 del_edges
del_edges = set()
for op in ops:
    if op[0] == 1:
        del_edges.add(op[1])

# 逆向遍历边的列表 edges，将未被删除的边加入到并查集中
for i, edge in enumerate(edges):
    if i + 1 not in del_edges:
        union(edge[0], edge[1])

# 逆向遍历操作列表 ops，处理每个操作
ops.reverse()
ans = []
for op in ops:
    if op[0] == 1:
        # 如果是删除边的操作，将对应的边加入到并查集中
        u, v, w = edges[op[1] - 1]
        union(u, v)
    else:
        # 如果是查询操作，计算并返回两个节点的异或和
        u, v = op[1], op[2]
        if find(u) != find(v):
            ans.append(-1)
        else:
            p = lca(u, v)
            c = par[p]
            ans.append(pre[u] ^ pre[p] ^ pre[v] ^ pre[c])

# 逆向遍历答案列表 ans，输出每个操作的结果
ans.reverse()
print('\n'.join(map(str, ans)))

这题不看了，遇到基本做不出来。

2024.4.28 美团笔试复盘
https://fulequn.github.io/2024/04/Article202404281/
作者
Fulequn
发布于
2024年4月28日
许可协议