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

✨ 本系列打算持续跟新阿里国际近期的春秋招笔试题汇总～

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

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

📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。

⌚️ 春招笔试也是接近尾声，没有拿到offer的小伙伴们抓紧啦～

💞 01.卢小姐的连续音节挑战

问题描述

卢小姐最近在学习外语，她注意到在某些语言中，元音不能连续出现。现在，她有一串由不同字母组成的字符序列，她想找出一个最长的连续子序列，使得在这个子序列中没有两个相邻的元音。元音定义为 “a”, “e”, “i”, “o”, “u” 这五个字母，其他所有字母都被视为辅音。

输入格式

第一行包含一个正整数 $n$，代表卢小姐拿到的字符序列的长度。

第二行包含一个长度为 $n$ 的字符串，代表卢小姐拿到的字符序列。

输出格式

输出一个整数，代表卢小姐可以得到的最长子序列的长度。

样例输入

7
aeiobcd

样例输出

3

数据范围

$1\le n\le 200000$

题解

可以遍历整个字符串，同时跟踪当前连续子序列的长度。当遇到元音时，需要检查前一个字符是否也是元音。如果是，就重置当前子序列的长度；如果不是，就继续增加当前子序列的长度，并更新最大长度。

参考代码

• Python

python">def is_vowel(char):return char.lower() in 'aeiou'def max_consecutive_substring(s):max_length = 0current_length = 0for i in range(len(s)):if is_vowel(s[i]):if i > 0 and is_vowel(s[i-1]):current_length = 0else:current_length += 1max_length = max(max_length, current_length)else:current_length += 1return max_lengthn = int(input().strip())
s = input().strip()
print(max_consecutive_substring(s))

• Java

java">import java.util.Scanner;public class Main {public static boolean isVowel(char ch) {return "aeiou".indexOf(Character.toLowerCase(ch)) != -1;}public static int maxConsecutiveSubstring(String s) {int max_length = 0, current_length = 0;for (int i = 0; i < s.length(); i++) {if (isVowel(s.charAt(i))) {if (i > 0 && isVowel(s.charAt(i - 1))) {current_length = 0;} else {current_length++;max_length = Math.max(max_length, current_length);}} else {current_length++;}}return max_length;}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();in.nextLine(); // Consume newline left-overString s = in.nextLine();System.out.println(maxConsecutiveSubstring(s));in.close();}
}

• Cpp

#include <iostream>
#include <string>
using namespace std;bool isVowel(char ch) {string vowels = "aeiou";return vowels.find(tolower(ch)) != string::npos;
}int maxConsecutiveSubstring(string s) {int max_length = 0, current_length = 0;for (int i = 0; i < s.length(); i++) {if (isVowel(s[i])) {if (i > 0 && isVowel(s[i - 1])) {current_length = 0;} else {current_length++;max_length = max(max_length, current_length);}} else {current_length++;}}return max_length;
}int main() {int n;cin >> n;string s;cin >> s;cout << maxConsecutiveSubstring(s) << endl;return 0;
}

💓 02.K小姐的魔法药水

题目描述

K小姐是一位魔法师，她发明了一种神奇的魔法药水。这种药水的效果取决于配方中的魔法材料。每种材料都有一个魔力值 $a_i$，药水的最终魔力等于所有材料魔力值的乘积，即 $f(a_1)\times f(a_2)\times \dots \times f(a_n)$，其中 $f(x)=x^x$。

现在，K小姐准备了 $n$ 种魔法材料，她想知道最终药水的魔力有多少种不同的因子。由于答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行包含一个正整数 $n$，表示魔法材料的种类数。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots ,a_n$，表示每种魔法材料的魔力值。

输出格式

输出一个整数，表示最终药水魔力的因子个数对 $10^9+7$ 取模的结果。

样例输入

3
1 2 3

样例输出

12

数据范围

$1\le n\le 2\times 10^5$
$1\le a_i\le 2\times 10^5$

题解

本题可以通过分解质因数的方法来求解。

首先，对于每个魔力值 $a_i$，计算 $f(a_i)=a_i^{a_i}$。然后将所有的 $f(a_i)$ 进行质因数分解，统计每个质因子的指数之和。最终答案等于所有质因子指数加一的乘积。

具体步骤如下：

1. 遍历每个魔力值 $a_i$：
   • 对 $a_i$ 进行质因数分解，对于每个质因子 $p$，计算 $a_i$ 中 $p$ 的指数 $cnt$，将 $cnt\times a_i$ 累加到 $p$ 的总指数中。
2. 将所有质因子的总指数加一，并累乘得到最终答案。
3. 将答案对 $10^9+7$ 取模。

时间复杂度为 $O(n\sqrt{a_i})$，空间复杂度为 $O(a_i)$。

参考代码

• Python

python">import sys
from collections import Counterdef main():mod = 10 ** 9 + 7n = int(sys.stdin.readline())a = list(map(int, sys.stdin.readline().split()))factors = Counter()for x in a:for i in range(2, int(x ** 0.5) + 1):if x % i == 0:cnt = 0while x % i == 0:cnt += 1x //= ifactors[i] += cnt * xif x > 1:factors[x] += xres = 1for exp in factors.values():res = res * (exp + 1) % modprint(res)if __name__ == '__main__':main()

• Java

java">import java.io.*;
import java.util.*;public class Main {private static final int MOD = (int) 1e9 + 7;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();Map<Integer, Integer> factors = new HashMap<>();for (int x : a) {for (int i = 2; i <= Math.sqrt(x); i++) {if (x % i == 0) {int cnt = 0;while (x % i == 0) {cnt++;x /= i;}factors.put(i, factors.getOrDefault(i, 0) + cnt * x);}}if (x > 1) {factors.put(x, factors.getOrDefault(x, 0) + x);}}long res = 1;for (int exp : factors.values()) {res = res * (exp + 1) % MOD;}System.out.println(res);}
}

• Cpp

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
using ll = long long;const int MOD = 1e9 + 7;int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}unordered_map<int, long long> factors;for (int x : a) {for (int i = 2; i * i <= x; i++) {if (x % i == 0) {int cnt = 0;while (x % i == 0) {cnt++;x /= i;}factors[i] +=1ll * cnt * x;}}if (x > 1) {factors[x] += x;}}ll res = 1;for (auto [p, exp] : factors) {res = res * (exp + 1) % MOD;}cout << res << endl;return 0;
}

💖 03.彩色项链

题目描述

LYA 有一条由 $n$ 个珠子组成的项链,每个珠子都有一个颜色,用一个大写字母表示。现在 LYA 想知道,在这条项链上一共有多少种不同的简单路径,恰好包含 $k$ 种颜色的珠子。

一个简单路径指的是项链上的一段连续的珠子序列,且任意两个珠子之间至多只有一条边相连。

输入格式

第一行包含两个正整数 $n$ 和 $k$,分别表示项链的珠子数和需要的颜色数。

第二行是一个长度为 $n$ 的字符串,表示项链上每个珠子的颜色。

接下来 $n-1$ 行,每行两个整数 $u,v$,表示编号为 $u$ 和 $v$ 的珠子之间有一条边相连。

输出格式

输出一个整数,表示满足条件的简单路径的数目。

样例输入

3 2
RBG
1 2
2 3

样例输出

2

数据范围

• $1\le n\le 10^3$
• $1\le k\le 26$
• 字符串中只包含大写字母
• 数据保证给出的是一棵树

题解

本题可以用 DFS 来解决。我们从每个点出发,进行一次 DFS 遍历,过程中维护当前路径上出现的颜色种类数。如果超过了 $k$ 种,就直接返回;如果恰好为 $k$ 种,就将答案加 $1$。

注意到每条路径都会被计算两次,因为它的两个端点都会作为起点进行一次 DFS。所以最后的答案需要除以 $2$。特殊地,如果 $k=1$,不需要除以 $2$。

时间复杂度 $O(n^2)$,空间复杂度 $O(n)$。

参考代码

• Python

python">import sys
input = lambda: sys.stdin.readline().strip()
from collections import Counterdef dfs(u: int, pre: int, s: Counter):global resif len(s) > k:returnif len(s) == k:res += 1for i in g[u]:if i != pre:s[color[i-1]] += 1dfs(i, u, s)s[color[i-1]] -= 1if s[color[i-1]] == 0:del s[color[i-1]]n, k = map(int, input().split())
color = input()
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):cnt = Counter()cnt[color[i-1]] = 1dfs(i, -1, cnt)if k != 1:res //= 2
print(res)

• Java

java">import java.io.*;
import java.util.*;public class Main {static int n, k;static String color;static List<Integer>[] g;static int res;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] str = br.readLine().split(" ");n = Integer.parseInt(str[0]);k = Integer.parseInt(str[1]);color = br.readLine();g = new List[n+1];for (int i = 1; i <= n; i++) {g[i] = new ArrayList<>();}for (int i = 0; i < n-1; i++) {str = br.readLine().split(" ");int a = Integer.parseInt(str[0]);int b = Integer.parseInt(str[1]);g[a].add(b);g[b].add(a);}for (int i = 1; i <= n; i++) {Map<Character, Integer> cnt = new HashMap<>();cnt.put(color.charAt(i-1), 1);dfs(i, -1, cnt);}if (k != 1) {res /= 2;}System.out.println(res);}static void dfs(int u, int pre, Map<Character, Integer> cnt) {if (cnt.size() > k) {return;}if (cnt.size() == k) {res++;}for (int i : g[u]) {if (i != pre) {char c = color.charAt(i-1);cnt.put(c, cnt.getOrDefault(c, 0)+1);dfs(i, u, cnt);cnt.put(c, cnt.get(c)-1);if (cnt.get(c) == 0) {cnt.remove(c);}}}}
}

• Cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;int n, k;
string color;
vector<int> g[N];
int res;void dfs(int u, int pre, unordered_map<char, int>& cnt) {if (cnt.size() > k) {return;}if (cnt.size() == k) {res++;}for (int i : g[u]) {if (i != pre) {char c = color[i-1];cnt[c]++;dfs(i, u, cnt);if (--cnt[c] == 0) {cnt.erase(c);}}}
}int main() {cin >> n >> k;cin >> color;for (int i = 0; i < n-1; i++) {int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);}for (int i = 1; i <= n; i++) {unordered_map<char, int> cnt;cnt[color[i-1]] = 1;dfs(i, -1, cnt);}if (k != 1) {res /= 2;}cout << res << endl;return 0;
}

写在最后

📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。