06-29 09:56 已编辑北京理工大学算法工程师发布于浙江

关注

【春招笔试】2024-04-27-美团-三语言题解

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新美团近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导

👏 感谢大家的订阅➕ 和喜欢💗

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

alt

🍓 01. 小A的字符串替换

问题描述

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

输入格式

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

输出格式

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

样例输入

meiluan

样例输出

tuanluan

数据范围

$1 \leq |S| \leq 100000$

题解

本题考查字符串的基本操作，难度不大。只需要遍历整个字符串，找到所有的 mei 子串，并将其替换为 tuan 子串即可。

具体实现时，可以直接使用各个语言提供的字符串替换函数，如 Python 的 replace() 函数、Java 的 replaceAll() 函数等。这些函数可以直接将字符串中所有指定的子串替换为新的子串，非常方便。

如果不使用语言提供的函数，也可以手动实现替换操作。具体思路是：从前往后扫描字符串，每次找到一个 mei 子串，就将其替换为 tuan，并将扫描的下标移动到替换后的子串的末尾，继续搜索。重复这个过程，直到扫描完整个字符串。

本题的时间复杂度为 $O(|S|)$ ，空间复杂度为 $O(|S|)$ 。其中 $|S|$ 表示字符串 $S$ 的长度。

参考代码

Python

s = input()
print(s.replace('mei', 'tuan'))

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(s.replaceAll("mei", "tuan"));
    }
}

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    
    int pos = 0;
    while ((pos = s.find("mei", pos)) != string::npos) {
        s.replace(pos, 3, "tuan");
        pos += 4;
    }
    
    cout << s << 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

样例输出

样例输入

2 3
abc
cdb

样例输出

数据范围

$1 \leq n, m \leq 200$

题解

我们可以枚举每个 $2 \times 2$ 的正方形区域，判断其中的四个字符是否互不相同。

具体地，我们可以枚举正方形区域的左上角位置 $(i, j)$ ，其中 $0 \leq i < n-1$ , $0 \leq j < m-1$ 。对于每个位置，我们取出其中的四个字符，判断它们是否互不相同，可以用 set 实现。如果互不相同，就将答案加 1。

最后输出答案即可。

时间复杂度 $O(nm)$ ，空间复杂度 $O(1)$ 。

参考代码

Python

n, m = map(int, input().split())
a = [input() for _ in range(n)]

res = 0
for i in range(n - 1):
    for j in range(m - 1):
        if len(set(a[i][j:j+2] + a[i+1][j:j+2])) == 4:
            res += 1

print(res)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        String[] a = new String[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.next();
        }
        
        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                Set<Character> set = new HashSet<>();
                for (int k = i; k <= i + 1; k++) {
                    for (int p = j; p <= j + 1; p++) {
                        set.add(a[k].charAt(p));
                    }
                }
                if (set.size() == 4) {
                    res++;
                }
            }
        }
        System.out.println(res);
    }
}

#include <iostream>
#include <string>
#include <set>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    string a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int res = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m - 1; j++) {
            set<char> st;
            for (int k = i; k <= i + 1; k++) {
                for (int p = j; p <= j + 1; p++) {
                    st.insert(a[k][p]);
                }
            }
            if (st.size() == 4) {
                res++;
            }
        }
    }
    cout << res << endl;
    return 0;
}

🍍 03.卢小姐的糖果合并

问题描述

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

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

输入格式

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

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

输出格式

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

样例输入

4 4
2 3 4 5

样例输出

数据范围

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

题解

本题可以使用动态规划来解决。设 $dp[i][j]$ 表示当前处理到第 $i$ 个糖果,且上一次合并后的糖果大小为 $j$ 时的方案数。

对于每个 $dp[i][j]$ ,可以选择将当前的糖果 $a[i]$ 直接合并到上一次合并后的糖果中,也可以选择将 $a[i]$ 作为一个新的合并开始。因此,状态转移方程为:

dp[i][j] = dp[i-1][j+a[i]] + (j \geq k) \times dp[i-1][a[i]]

其中, $(j \geq k)$ 为示性函数,当 $j \geq k$ 时值为 $1$ ,否则为 $0$ 。

最终的答案即为 $\sum_{j=0}^{n \times 200} dp[n][j]$ 。

时间复杂度 $O(n ^ 2 \times 200)$ ,空间复杂度 $O(n ^ 2 \times 200)$ 。s

参考代码

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
int main (){
    int n, k; cin >> n >> k; 
    vector<int> a(n);
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    vector<vector<int>> dp(n + 1, vector<int>(n * 201, -1));
    auto dfs = [&](auto dfs, int u, int last) -> int{
        if(u == n)
            return last >= k;
        if(dp[u][last] != -1) return dp[u][last];
        int res = dfs(dfs, u + 1, last + a[u]);
        if(last >= k)
            res += dfs(dfs, u + 1, a[u]);
        res %= mod;
        dp[u][last] = res;
        return res;
    };
    cout << dfs(dfs, 0, 0) % mod << "\n";
    return 0;
}

Python

mod = 10 ** 9 + 7

def dfs(u, last):
    if u == n:
        return int(last >= k)
    if dp[u][last] != -1:
        return dp[u][last]
    res = dfs(u + 1, last + a[u]) 
    if last >= k:
        res += dfs(u + 1, a[u])
    res %= mod
    dp[u][last] = res
    return res

n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = [[-1] * (n * 201) for _ in range(n + 1)]
print(dfs(0, 0) % mod)

Java

import java.util.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static int n, k;
    static int[] a;
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        dp = new int[n + 1][n * 201];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], -1);
        }
        System.out.println(dfs(0, 0));
    }

    public static int dfs(int u, int last) {
        if (u == n) {
            return last >= k ? 1 : 0;
        }
        if (dp[u][last] != -1) {
            return dp[u][last];
        }
        int res = dfs(u + 1, last + a[u]);
        if (last >= k) {
            res += dfs(u + 1, a[u]);
        }
        res %= MOD;
        dp[u][last] = res;
        return res;
    }
}

🍑 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

样例输出

数据范围

$1 \leq n \leq 10^5$

题解

本题可以使用 DFS 结合质因数分解来解决。

首先,我们可以通过 DFS 遍历整棵树,找出所有的红色连通块。对于每个红色连通块,我们需要计算其所有节点编号乘积的因子数量。

为了高效地计算乘积的因子数量,我们可以对每个节点的编号进行质因数分解。将每个质因数及其指数存储在一个 map 中。对于一个红色连通块,将其所有节点的质因数指数累加到 map 中。最后,将 map 中所有质因数的指数加 $1$ 后相乘,即可得到该红色连通块的权值。

遍历完所有的红色连通块后,将它们的权值相加即可得到最终答案。

时间复杂度 $O(n \log n)$ ,空间复杂度 $O(n)$ 。

参考代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    vector<vector<int>> g(n + 1);
    string color; cin >> color;
    color = " " + color;
        
    vector<bool> vis(n + 1, false);
    for(int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    map<int, int> mp;
    function<void(int, int)> dfs = [&](int u, int fa) {
        vis[u] = true;
        int x = u;
        for(int i = 2; i <= x / i; i++) {
            if(u % i == 0) {
                int cnt = 0;
                while(x % i == 0) x /= i, cnt++;
                mp[i] += cnt;
            }
        }
        if(x > 1) mp[x]++;
        
        for(int v : g[u]) {
            if(v != fa && !vis[v] && color[v] == 'R') {
                vis[v] = true;
                dfs(v, u);
            }
        }
    };
    
    LL res = 0;
    for(int i = 1; i <= n; i++) {
        if(!vis[i] && color[i] == 'R') {
            mp.clear();
            dfs(i, -1);
            LL t = 1;
            for(auto [_, cnt] : mp) {
                t = t * (cnt + 1) % MOD;
            }
            res = (res + t) % MOD; 
        }
    }
    cout << res << "\n";
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static List<List<Integer>> g = new ArrayList<>();
    static String color;
    static boolean[] vis;
    static Map<Integer, Integer> mp = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        color = " " + sc.next();
        vis = new boolean[n + 1];
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            g.get(a).add(b);
            g.get(b).add(a);
        }

        long res = 0;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && color.charAt(i) == 'R') {
                mp.clear();
                dfs(i, -1);
                long t = 1;
                for (int cnt : mp.values()) {
                    t = t * (cnt + 1) % MOD;
                }
                res = (res + t) % MOD;
            }
        }
        System.out.println(res);
    }

    static void dfs(int u, int fa) {
        vis[u] = true;
        int x = u;
        for (int i = 2; i <= x / i; i++) {
            if (u % i == 0) {
                int cnt = 0;
                while (x % i == 0) {
                    x /= i;
                    cnt++;
                }
                mp.put(i, mp.getOrDefault(i, 0) + cnt);
            }
        }
        if (x > 1) {
            mp.put(x, mp.getOrDefault(x, 0) + 1);
        }

        for (int v : g.get(u)) {
            if (v != fa && !vis[v] && color.charAt(v) == 'R') {
                vis[v] = true;
                dfs(v, u);
            }
        }
    }
}

Python

from collections import defaultdict

MOD = 10 ** 9 + 7

def dfs(u, fa):
    vis[u] = True
    x = u
    i = 2
    while i * i <= x:
        if x % i == 0:
            cnt = 0
            while x % i == 0:
                x //= i
                cnt += 1
            mp[i] += cnt
        i += 1
    if x > 1:
        mp[x] += 1
    
    for v in g[u]:
        if v != fa and not vis[v] and color[v] == 'R':
            vis[v] = True
            dfs(v, u)

n = int(input())
color = ' ' + input()
vis = [False] * (n + 1)
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

res = 0
for i in range(1, n + 1):
    if not vis[i] and color[i] == 'R':
        mp = defaultdict(int)
        dfs(i, -1)
        t = 1
        for cnt in mp.values():
            t = t * (cnt + 1) % MOD
        res = (res + t) % MOD
print(res)

05.LYA 的城市之旅

问题描述

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

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

封锁编号为 $i$ 的道路。🫧
询问从城市 $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 \neq 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 \neq v)$ ,表示询问从城市 $u$ 到城市 $v$ 的最短路径上所有道路魅力值的异或和。

输出格式

对于每次询问,输出一个整数表示答案。如果城市 $u$ 和城市 $v$ 之间没有路径,则输出 $-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,计算出每个城市到根城市路径上的异或值,记为 $xor[i]$ 。这样对于一个询问 $(u,v)$ ,答案就是 $xor[u] \oplus xor[v]$ 。

然后处理封锁道路的操作。可以用并查集来维护城市之间的连通性。一开始先读入所有 $q$ 次操作,对于封锁道路的操作,我们标记出要封锁的道路编号。然后从后往前处理询问,同时在并查集中连接之前标记的被封锁的道路。这样对于一个 $(u,v)$ 询问,判断 $u,v$ 所在的集合是否相同,如果相同则输出答案,否则输出 $-1$ 。

总的时间复杂度为 $O(n+q \log n)$ ,空间复杂度为 $O(n+q)$ 。

参考代码

Python

def find(x, p):
    if p[x] != x:
        p[x] = find(p[x], p)
    return p[x]

def merge(x, y, p):
    fx = find(x, p)
    fy = find(y, p)
    if fx == fy:
        return
    p[fy] = fx

def same(x, y, p):
    return find(x, p) == find(y, p)

n, q = map(int, input().split())
p = [i for i in range(n + 1)]
g = [[] for _ in range(n + 1)]
edge = []
v_or = [0] * (n + 1)

for _ in range(n - 1):
    a, b, c = map(int, input().split())
    edge.append((a, b, c))
    g[a].append((b, c))
    g[b].append((a, c))

def dfs(u, pre, num, g, v_or):
    for i, w in g[u]:
        if i != pre:
            v_or[i] = num ^ w
            dfs(i, u, v_or[i], g, v_or)

dfs(1, -1, 0, g, v_or)

op = []
ned_del = set()
for _ in range(q):
    c, *rest = map(int, input().split())
    if c == 1:
        u, = rest
        u -= 1
        ned_del.add(u)
    else:
        u, v = rest
    op.append((c, u, v))

for i in range(n - 1):
    if i not in ned_del:
        merge(edge[i][0], edge[i][1], p)

ans = []
for c, u, v in reversed(op):
    if c == 1:
        merge(edge[u][0], edge[u][1], p)
    else:
        if same(u, v, p):
            ans.append(v_or[u] ^ v_or[v])
        else:
            ans.append(-1)

for a in reversed(ans):
    print(a)

Java

import java.util.*;

public class Main {
    static int[] p;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        p = new int[n + 1];
        for (int i = 1; i <= n; i++) p[i] = i;

        List<List<int[]>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());

        int[][] edge = new int[n - 1][3];
        for (int i = 0; i < n - 1; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            edge[i][0] = a;
            edge[i][1] = b;
            edge[i][2] = c;
            g.get(a).add(new int[]{b, c});
            g.get(b).add(new int[]{a, c});
        }

        int[] v_or = new int[n + 1];
        dfs(g, v_or, 1, -1, 0);

        List<int[]> op = new ArrayList<>();
        Set<Integer> ned_del = new HashSet<>();
        for (int i = 0; i < q; i++) {
            int c = scanner.nextInt();
            int u, v = -1;
            if (c == 1) {
                u = scanner.nextInt();
                u--;
                ned_del.add(u);
            } else {
                u = scanner.nextInt();
                v = scanner.nextInt();
            }
            op.add(new int[]{c, u, v});
        }

        for (int i = 0; i < n - 1; i++) {
            if (!ned_del.contains(i)) merge(edge[i][0], edge[i][1]);
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = q - 1; i >= 0; i--) {
            int[] o = op.get(i);
            int c = o[0], u = o[1], v = o[2];
            if (c == 1) merge(edge[u][0], edge[u][1]);
            else {
                if (same(u, v)) ans.add(v_or[u] ^ v_or[v]);
                else ans.add(-1);
            }
        }

        for (int i = ans.size() - 1; i >= 0; i--) System.out.println(ans.get(i));
    }

    static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    static void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        p[fy] = fx;
    }

    static boolean same(int x, int y) {
        return find(x) == find(y);
    }

    static void dfs(List<List<int[]>> g, int[] v_or, int u, int pre, int num) {
        for (int[] e : g.get(u)) {
            int i = e[0], w = e[1];
            if (i != pre) {
                v_or[i] = num ^ w;
                dfs(g, v_or, i, u, v_or[i]);
            }
        }
    }
}

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int p[200010];
int find(int x){
    if(p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if(fx == fy) return;
    p[fy] = fx;
}
bool same(int x, int y){
    return find(x) == find(y);
}
int main (){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i ++) p[i] = i;
    vector<vector<array<int, 2>>> g(n + 1);
    vector<array<int, 3>> edge(n - 1);
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b, c; cin >> a >> b >> c;
        edge[i] = {a, b, c};
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    vector<int> v_or(n + 1);
    auto dfs = [&](auto dfs, int u, int pre, int num) -> void{
        for(auto [i, w] : g[u])
            if(i != pre)
            {
                v_or[i] = num ^ w;
                dfs(dfs, i, u, v_or[i]);
            } 
    };
    dfs(dfs, 1, -1, 0);
    vector<array<int, 3>> op(q);
    set<int> ned_del;
    for(int i = 0; i < q; i ++)
    {
        int c; cin >> c;
        int u, v;
        v = -1;
        if(c == 1)
        {
        	cin >> u;
        	u -- ;
        	ned_del.insert(u);
        }
        else
            cin >> u >> v;
        op[i] = {c, u, v};
    }
    for(int i = 0; i < n - 1; i ++)
    {
        if(!ned_del.count(i))
            merge(edge[i][0], edge[i][1]);
    }
    vector<int> ans;
    for(int i = q - 1; i >= 0; i --)
    {
        auto [c, u, v] = op[i];
        if(c == 1)
        {
            merge(edge[u][0], edge[u][1]);
        }
        else
        { 
            if(same(u, v))
            {
                ans.push_back(v_or[u] ^ v_or[v]);
            }
            else
                ans.push_back(-1);
        }
    }
    int m = ans.size();
    for(int i = m - 1; i >= 0; i --)
        cout << ans[i] << "\n";
    return 0;
}

alt