【春招笔试】2024-04-29-阿里国际-三语言题解

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

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

💻 ACM银牌🥈| 多次AK大厂笔试

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

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

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

问题描述

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

输入格式

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

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

输出格式

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

样例输入

7
aeiobcd

样例输出

4

数据范围

题解

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

参考代码

• Python

def longest_subsequence_without_adjacent_vowels(n, s):
    vowels = set("aeiou")
    max_length = 0
    current_length = 0
    prev_vowel = False
    
    for i in range(n):
        if s[i] in vowels:
            if prev_vowel:
                current_length = 1  # 重置，因为前一个是元音
            else:
                current_length += 1
            prev_vowel = True
        else:
            current_length += 1
            prev_vowel = False
        
        max_length = max(max_length, current_length)
    
    return max_length

# 读取输入数据
n = int(input().strip())
s = input().strip()

# 输出最长子序列长度
print(longest_subsequence_without_adjacent_vowels(n, s))

• Java

import java.util.*;

public class Main {
    public static int longestSubsequenceWithoutAdjacentVowels(int n, String s) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
        int max_length = 0;
        int current_length = 0;
        boolean prev_vowel = false;

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (vowels.contains(c)) {
                if (prev_vowel) {
                    current_length = 1;  // Reset because previous character was a vowel
                } else {
                    current_length += 1;
                }
                prev_vowel = true;
            } else {
                current_length += 1;
                prev_vowel = false;
            }
            max_length = Math.max(max_length, current_length);
        }

        return max_length;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine(); // Consume newline
        String s = scanner.nextLine();

        System.out.println(longestSubsequenceWithoutAdjacentVowels(n, s));
    }
}

• Cpp

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

int longest_subsequence_without_adjacent_vowels(int n, const string& s) {
    set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
    int max_length = 0;
    int current_length = 0;
    bool prev_vowel = false;

    for (int i = 0; i < n; ++i) {
        if (vowels.count(s[i])) {
            if (prev_vowel) {
                current_length = 1;  // Reset because previous character was a vowel
            } else {
                current_length += 1;
            }
            prev_vowel = true;
        } else {
            current_length += 1;
            prev_vowel = false;
        }
        max_length = max(max_length, current_length);
    }

    return max_length;
}

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

    cout << longest_subsequence_without_adjacent_vowels(n, s) << endl;
    return 0;
}

💓 02.K小姐的魔法药水

题目描述

K小姐是一位魔法师，她发明了一种神奇的魔法药水。这种药水的效果取决于配方中的魔法材料。每种材料都有一个魔力值 ，药水的最终魔力等于所有材料魔力值的乘积，即 ，其中 。

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

输入格式

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

第二行包含 个正整数 ，表示每种魔法材料的魔力值。

输出格式

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

样例输入

3
1 2 3

样例输出

12

数据范围

题解

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

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

具体步骤如下：

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

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

import sys
from collections import Counter

def main():
    mod = 10 ** 9 + 7
    n = 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 = 0
                while x % i == 0:
                    cnt += 1