【笔试题汇总】美团笔试题题解 第五场 2024.4.27

本文主要是介绍【笔试题汇总】美团笔试题题解 第五场 2024.4.27，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024.04.27

01. 小A的字符串替换

问题描述

小A有一个仅由小写字母组成的字符串 $S$，长度不超过 $100000$。她准备把其中所有的 mei 子串替换为 tuan 子串，你能帮她完成这个任务吗？

输入格式

输入一个仅由小写字母组成的字符串 $S$，表示小A拥有的原始字符串。

输出格式

输出一个字符串，表示将 $S$ 中所有 mei 子串替换为 tuan 子串后得到的新字符串。

样例输入

meiluan

样例输出

tuanluan

数据范围

$1\le |S|\le 100000$

解题思路

这道题目要求将给定字符串中所有的 mei 子串替换为 tuan 子串。可以通过遍历字符串的每个字符，检查当前位置开始的子串是否为 mei，如果是，则将其替换为 tuan。

cpp

#include <iostream>
#include <string>using namespace std;int main() {string S;cin >> S;string result;for (int i = 0; i < S.length(); ++i) {if (S.substr(i, 3) == "mei") { // 检查是否为 "mei" 子串result += "tuan"; // 如果是，则替换为 "tuan"i += 2; // 跳过 "mei" 的长度，避免重复处理} else {result += S[i]; // 如果不是，则保持原样}}cout << result << endl;return 0;
}

02.方格纸上的四字成语

题目描述

K小姐喜欢在方格纸上写四字成语。有一天，她在一张 $n\times m$ 的方格纸上填写了 $n$ 行四字成语，其中第 $i$ 行的四字成语为 $a_i$。

现在，K小姐想知道，在这张方格纸上，有多少个 $2\times 2$ 的正方形区域，其中的四个字分别不相同。

输入格式

第一行包含两个正整数 $n$ 和 $m$，表示方格纸的行数和列数。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示 K小姐 写的四字成语。保证每个字符都是小写字母。

输出格式

输出一个整数，表示满足条件的 $2\times 2$ 正方形区域的数目。

样例输入

2 3
abb
aac

样例输出

0

样例输入

2 3
abc
cdb

样例输出

1

数据范围

$1\le n,m\le 200$

【题目解析】

我们可以遍历方格纸上的每个 $2\times 2$ 区域，然后判断这个区域内的四个字是否都不相同，如果不相同则计数加一。

cpp

#include <iostream>
#include <vector>
#include <string>
#include <set>using namespace std;int countDistinctWords(const vector<string>& grid, int n, int m, int row, int col) {set<char> uniqueChars;uniqueChars.insert(grid[row][col]);uniqueChars.insert(grid[row][col + 1]);uniqueChars.insert(grid[row + 1][col]);uniqueChars.insert(grid[row + 1][col + 1]);return uniqueChars.size();
}int main() {int n, m;cin >> n >> m;vector<string> grid(n);for (int i = 0; i < n; ++i) {cin >> grid[i];}int count = 0;for (int i = 0; i < n - 1; ++i) {for (int j = 0; j < m - 1; ++j) {if (countDistinctWords(grid, n, m, i, j) == 4) {count++;}}}cout << count << endl;return 0;
}

03.卢小姐的糖果合并

问题描述

卢小姐有一串由 $n$ 个正整数组成的糖果串。她每次可以选择相邻的两颗糖果合并,得到一颗新的糖果,新糖果的大小为合并前两颗糖果的大小之和。通过不断地合并,最终糖果串中只剩下一颗糖果。

如果最后剩下的这颗糖果的大小不小于 $k$,那么卢小姐就可以请她的朋友们吃这颗大糖果。卢小姐想知道,一共有多少种不同的合并方式,使得最后剩下的糖果大小不小于 $k$。由于答案可能很大,请对 $10^9+7$ 取模后输出。

输入格式

第一行包含两个正整数 $n$ 和 $k$,表示糖果串的长度以及糖果大小的限制。

第二行包含 $n$ 个正整数,表示初始的糖果串。

输出格式

输出一个整数,表示合并方式的数目对 $10^9+7$ 取模后的结果。

样例输入

4 4
2 3 4 5

样例输出

4

数据范围

$1\le n\le 200$
$1\le k\le 40000$
$1\le a_i\le 200$

【题目解析】

这个问题可以通过动态规划来解决。我们可以定义一个状态数组 $dp$，其中 $dp[i]$ 表示剩余糖果大小为 $i$ 时的合并方式数目。然后，我们从左到右遍历糖果串，每次更新 $dp$ 数组，以计算出剩余糖果大小为 $i$ 时的合并方式数目。最终，$dp[k]$ 即为所求的答案。

cpp

#include <iostream>
#include <vector>using namespace std;const int MOD = 1e9 + 7;int main() {int n, k;cin >> n >> k;vector<int> candies(n);for (int i = 0; i < n; ++i) {cin >> candies[i];}vector<long long> dp(k + 1, 0);dp[0] = 1; // 初始化剩余糖果大小为 0 的合并方式数目为 1for (int i = 0; i < n; ++i) {for (int j = k; j >= candies[i]; --j) {dp[j] = (dp[j] + dp[j - candies[i]]) % MOD;}}cout << dp[k] << endl;return 0;
}

04.卢小姐的红色连通块

问题描述

卢小姐拿到一棵由 $n$ 个节点组成的树。其中有一些节点被染成了红色。

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

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

输入格式

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

第二行输入一个长度为 $n$ 的字符串,其中第 $i$ 个字符表示第 $i$ 号节点的颜色。R 表示红色,W 表示白色。

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

输出格式

一个整数,代表所有红色连通块的权值之和对 $10^9+7$ 取模后的结果。

样例输入

3
WRR
1 2
2 3

样例输出

4

数据范围

$1\le n\le 10^5$

【题目解析】

首先，需要理解红色连通块的权值定义：即所有节点编号乘积的因子数量。对于树这种特殊的图结构，可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来遍历树，并在遍历的过程中计算每个连通块的权值。

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>using namespace std;const int MOD = 1e9 + 7;vector<vector<int>> adj;
vector<bool> visited;
vector<int> factors;// Function to calculate factors of a number
void calculateFactors(int n) {for (int i = 1; i <= sqrt(n); ++i) {if (n % i == 0) {factors.push_back(i);if (n / i != i) {factors.push_back(n / i);}}}
}// DFS to calculate factor count in a connected component
int dfs(int node, const vector<char>& colors) {visited[node] = true;int product = 1;for (int neighbor : adj[node]) {if (!visited[neighbor] && colors[neighbor] == 'R') {product *= dfs(neighbor, colors);product %= MOD;}}calculateFactors(product); // Calculate factors of productreturn product;
}int main() {int n;cin >> n;// Read node colorsvector<char> colors(n);for (int i = 0; i < n; ++i) {cin >> colors[i];}// Initialize adjacency listadj.resize(n);visited.assign(n, false);// Read edgesfor (int i = 0; i < n - 1; ++i) {int u, v;cin >> u >> v;u--; // Adjust to 0-based indexingv--;adj[u].push_back(v);adj[v].push_back(u);}long long totalWeight = 0;// DFS to find connected components and calculate their weightsfor (int i = 0; i < n; ++i) {if (!visited[i] && colors[i] == 'R') {factors.clear(); // Clear factors for each connected componentint componentWeight = dfs(i, colors);for (int factor : factors) {totalWeight += factor;totalWeight %= MOD;}}}cout << totalWeight << endl;return 0;
}

05.LYA 的城市之旅

问题描述

LYA 是一名旅行家,她计划游览一个有 $n$ 个城市的国家。这些城市由 $n-1$ 条道路连接,形成了一棵树的结构。每条道路都有一个魅力值 $w$。

LYA 准备进行 $q$ 次旅行,每次旅行都有两种选择:

1. 封锁编号为 $i$ 的道路。
2. 询问从城市 $u$ 到城市 $v$ 的最短路径上所有道路魅力值的异或和。

LYA 希望你能帮她计算出每次询问的结果。

输入格式

第一行包含两个正整数 $n,q$ $(1\le n,q\le 2\times 10^5)$,表示城市数量和旅行次数。

接下来 $n-1$ 行,每行包含三个正整数 $u_i,v_i,w_i$ $(1\le u_i,v_i\le n,u_i\ne v_i,1\le w_i\le 10^9)$,表示一条连接城市 $u_i$ 和 $v_i$ 的道路,魅力值为 $w_i$。

接下来 $q$ 行,每行表示一次旅行:

• 如果第一个数是 $1$,后面会有一个正整数 $i$ $(1\le i\le n-1)$,表示要封锁编号为 $i$ 的道路。
• 如果第一个数是 $2$,后面会有两个正整数 $u,v$ $(1\le u,v\le n,u\ne v)$,表示询问从城市 $u$ 到城市 $v$ 的最短路径上所有道路魅力值的异或和。

输出格式

对于每次询问,输出一个整数表示答案。如果城市 $u$ 和城市 $v$ 之间没有路径,则输出 $-1$。

样例输入

5 5
1 2 1
1 3 2
2 4 3
2 5 3
2 1 2
2 1 4
2 4 5
1 2
2 1 4

样例输出

1
0
0
-1

数据范围

• $1\le n,q\le 2\times 10^5$
• $1\le u_i,v_i\le n$
• $1\le w_i\le 10^9$

【题目解析】

这个问题涉及到树的最短路径以及路径上的魅力值异或和。可以使用树的深度优先搜索（DFS）来求解。在DFS过程中记录每个节点到根节点的路径上的魅力值的异或和。首先构建一个树的数据结构，并使用深度优先搜索（DFS）计算了每个节点到根节点的路径上的魅力值的异或和。然后，使用二叉上溯法（binary lifting）预计算了每个节点的祖先，以便快速找到两个节点的最低公共祖先（LCA）。在处理查询时，它根据查询类型执行相应的操作：对于类型1，即封锁道路，直接输出-1；对于类型2，即查询最短路径上的道路魅力值异或和，首先找到两个节点的LCA，然后计算从两个节点到LCA的路径上的魅力值异或和并输出。

cpp

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;struct TreeNode {int val;vector<pair<int, int>> children; 
};void dfs(const vector<TreeNode>& tree, int node, int parent, vector<int>& xorSum, int currentXor) {xorSum[node] = currentXor;for (auto [child, charm] : tree[node].children) {if (child != parent) {dfs(tree, child, node, xorSum, currentXor ^ charm);}}
}int findLCA(const vector<vector<int>>& parent, const vector<int>& depth, int u, int v) {while (u != v) {if (depth[u] > depth[v]) {u = parent[u][0];} else if (depth[u] < depth[v]) {v = parent[v][0];} else {u = parent[u][0];v = parent[v][0];}}return u;
}int main() {int n, q;cin >> n >> q;vector<TreeNode> tree(n + 1); vector<vector<int>> parent(n + 1, vector<int>(1, 0)); vector<int> depth(n + 1, 0); for (int i = 1; i < n; ++i) {int u, v, w;cin >> u >> v >> w;tree[u].children.push_back({v, w});tree[v].children.push_back({u, w});}vector<int> xorSum(n + 1, 0); // 1-based indexingdfs(tree, 1, 0, xorSum, 0);for (int j = 1; (1 << j) <= n; ++j) {for (int i = 1; i <= n; ++i) {parent[i].push_back(parent[parent[i][j - 1]][j - 1]);}}while (q--) {int type;cin >> type;if (type == 1) {int edge;cin >> edge;cout << -1 << endl;} else {int u, v;cin >> u >> v;int lca = findLCA(parent, depth, u, v);int xorSumUV = xorSum[u] ^ xorSum[v] ^ xorSum[lca];cout << xorSumUV << endl;}}return 0;
}

整理试题不易，你的关注是我更新的最大动力！关注博主 带你看更多面试及竞赛试题和实用算法。

这篇关于【笔试题汇总】美团笔试题题解 第五场 2024.4.27的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---