2024.4.28 美团笔试复盘
算法
美团0427笔试
1 小美换团
小美拿到了一个字符串，她准备把其中所有的"mei"子串替换为"tuan"子串，你能帮帮她吗？
输入描述
一个仅由小写字母组成的字符串。长度不超100000
输出描述
修改后的字符串。
示例 1
输入
meituan
输出
tuantuan
思路与代码
打卡题。直接模拟即可。
s = input().replace("mei","tuan")
print(s)2 小美的特殊矩形
小美拿到了一个字符矩阵，她定义一个矩形区域是“特殊的”，当且仅当这个矩形区域中没有两个相同的字符。 现在小美想知道，有多少个2行2列的矩阵区域是特殊的？
输入描述
第一行输入两个正整数n,m，代表矩阵的行数和列数。
接下来的n行，每行输入一个长度为m的、仅由小写字母组成的字符串，代表小美拿到的字符矩阵。
1<=n,m<=200
输出描述
一个整数，代表"特殊的"矩形区域的数量。
示例 1
输入
2 3
abb
aac输出
0
思路与代码
模拟题。 直接枚举所有的2*2的子矩阵，判断是否存在重复的字符即可。
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
输入
4 4
2 3 4 5输出
4
说明
可能得到的数组有：[5,4,5]、[9,5]、[5,9]、[14]这四种。
思路与代码
动态规划。
对于每一个数字来说，如果当前和是小于k的，那么只能选择合并；否则的话，合并和不合并都可以。
f[i,j]考虑i往后的数字，当前和是p，组成满足条件的方案数有多少。
推导如下：
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]]# 读取输入的整数 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
输入
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进行运算即可。
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 次操作，每次操作是以下之一：
- 删除第 i 条边。
- 询问从 u 号点到 v 号点的最短路径上所有边的边权异或和。
小苯希望你帮他处理完所有的操作，并对所有操作 2 ，输出对应的异或和。
输入描述
第一行两个正整数 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
输入
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
0
0
-1说明
样例的树如图所示，前三次询问的结果分别为：
1 号点到 2 号点路径异或和为：1
1 号点到 4 号点路径异或和为：1 ^ 2 ^ 3 = 0
4 号点到 5 号点路径异或和为：3 ^ 3 = 0
第五步操作删除第 2 条边，即变为下图：
接着询问 1 好点到 4 号点的路径异或和，由于无法到达，因此输出 -1。思路与代码
lca（最近公共祖先）+倍增优化+并查集+逆向思维。
tip1：树上的最短路其实就是两个点的路径。 tip2：异或运算符合交换律。
思路如下： 1.对于删除的边，我们可以使用并查集+逆向遍历来判断是否连通。 2.对于连通的点，我们使用lca算法来检查两个节点之间的最近公共祖先，并且记录路径的异或和的值。
# 读取输入的整数 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)))
这题不看了，遇到基本做不出来。