美团春招实习笔试题解(0427)

type

status

date

slug

summary

📝 主旨内容

小美换团(字符串)

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

输入描述

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

输出描述

修改后的字符串。

示例 1

输入

输出

💡

签到题，直接replace

小美的特殊矩形(模拟)

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

输入描述

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

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

1<=n,m<=200

输出描述

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

示例 1

输入

输出

💡

多关键字排序裸题，难点在如何比较后失球，这涉及到在比较规则中内嵌数组比较，其实只需要简单地把失球的下标存下来，然后依次从头到尾比较即可，如何让代码变得简洁可以参考入下的做法充分利用内置的比较规则(存储失球下标的相反数，就是逆序)

小美的数组合并(背包)

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

输入描述

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

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

1<=n,k,ai<=200

输出描述

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

示例 1

输入

输出

说明

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

💡

对于每一个数字来说，如果当前和是小于k的，那么只能选择合并；否则的话，合并和不合并都可以。f[i,j] 考虑i往后的数字，当前和是p，组成满足条件的方案数有多少。

小美的树上联通块(并查集，数学)

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

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

小美想知道，所有红色连通块的权值之和是多少？由于答案过大，请对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

输入

输出

💡

注意题目只求红色点形成的联通块，红色点和为染色点相连并不会染成红色

💡

看到联通块，直接梭哈并查集

💡

如果 N = p1^c1 * p2^c2 * ... *pk^ck 约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1) 约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

小苯的树上询问(LCA，思维)

小苯有一个 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

输入

输出

说明

💡

树上的最短路其实就是两个点的路径

💡

异或运算符合交换律

💡

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

🤗 总结归纳

后面的题目挺有难度的，笔试的时候大概率很难做出来

📝 主旨内容

小美换团(字符串)

小美的特殊矩形(模拟)

小美的数组合并(背包)

小美的树上联通块(并查集，数学)

小苯的树上询问(LCA，思维)

🤗 总结归纳

📎 参考文章