【笔试题汇总】美团笔试题题解 第五场 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 的合并方式数目为 1

    for (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 product
    return product;
}

int main() {
    int n;
    cin >> n;

    // Read node colors
    vector<char> colors(n);
    for (int i = 0; i < n; ++i) {
        cin >> colors[i];
    }

    // Initialize adjacency list
    adj.resize(n);
    visited.assign(n, false);

    // Read edges
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        u--; // Adjust to 0-based indexing
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    long long totalWeight = 0;

    // DFS to find connected components and calculate their weights
    for (int i = 0; i < n; ++i) {
        if (!visited[i] && colors[i] == 'R') {
            factors.clear(); // Clear factors for each connected component
            int 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 indexing
    dfs(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;
}

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