程序员基德

03-11 20:15 中国科学技术大学 C++ 发布于浙江

关注

【2025春招真题改编】03.07-饿了么春招-算法岗

✅ 春招备战指南 ✅

💡 学习建议：

先尝试独立解题（建议用时：90分钟/套）
对照解析查漏补缺
配套练习题库

互联网必备刷题宝典🔗

01. 数据特征最大化

题目内容

小基是一个数据分析师，他最近获得了一个长度为 $n$ 的数组 $a$ 。作为一名分析师，他定义了两个重要的数据特征函数：

$f(a) = a_1 \oplus a_2 \oplus ... \oplus a_n$ （所有元素的按位异或和） $g(a) = gcd(a_1, a_2, ..., a_n)$ （所有元素的最大公约数）

为了寻找数据中的关键信息，小基需要从数组 $a$ 中选择一个非空连续子数组 $b$ ，使得该子数组的 $f(b) \cdot g(b)$ 值尽可能大。请帮助小基计算这个最大可能值。

输入描述

第一行一个正整数 $T(1 \leq T \leq 1000)$ ，表示测试数据的组数。

接下来对于每组测试数据，输入包含两行：

第一行一个正整数 $n(1 \leq n \leq 2 \times 10^5)$ ，表示数组 $a$ 的长度。
第二行 $n$ 个整数 $a_i(0 \leq a_i \leq 10^9)$ ，表示数组 $a$ 的元素。

保证所有测试数据中 $n$ 的总和不超过 $3 \times 10^5$ 。

输出描述

对于每组测试数据，输出一行一个整数表示最大的 $f(b) \cdot g(b)$ 值。

样例1

输入：

1
4
1 1 1 1

输出：

题解

这道题看似需要枚举所有可能的子数组并计算特征值，但通过分析可以发现一个重要性质：对于任意单元素子数组，其异或值和最大公约数都等于元素本身，因此乘积就是元素的平方。

关键发现：

单元素子数组的 $f$ 值就是元素本身
单元素子数组的 $g$ 值也是元素本身
对于多元素子数组， $g$ 值不会超过子数组中的最小元素

通过数学证明可知，数组中最大元素的平方就是问题的最优解。时间复杂度为 $O(n)$ ，只需遍历一次数组找出最大值即可。

参考代码

Python

def solve_case():
    # 读取输入
    size = int(input())
    nums = list(map(int, input().split()))
    
    # 查找最大值
    get_max = lambda x: max(x)
    peak = get_max(nums)
    
    # 返回平方值
    return peak * peak

def main():
    # 处理多组测试
    cases = int(input())
    for _ in range(cases):
        res = solve_case()
        print(res)

if __name__ == "__main__":
    main()

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

long long solve_case() {
    int size;
    cin >> size;
    
    // 记录最大值
    long long peak = 0;
    
    // 内联函数更新最大值
    auto update_peak = [&peak](long long val) {
        peak = max(peak, val);
    };
    
    // 读取并处理数组
    for(int i = 0; i < size; ++i) {
        long long val;
        cin >> val;
        update_peak(val);
    }
    
    return peak * peak;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int cases;
    cin >> cases;
    
    while(cases--) {
        cout << solve_case() << "\n";
    }
    
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    // 查找最大值的辅助方法
    private static long findPeak(long[] nums) {
        long peak = 0;
        for(long val : nums) {
            peak = Math.max(peak, val);
        }
        return peak;
    }
    
    // 处理单个测试用例
    private static long solveCase(Scanner sc) {
        int size = sc.nextInt();
        
        // 读取数组
        long[] nums = new long[size];
        for(int i = 0; i < size; i++) {
            nums[i] = sc.nextLong();
        }
        
        // 找出最大值
        long peak = findPeak(nums);
        
        return peak * peak;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt();
        
        for(int i = 0; i < cases; i++) {
            System.out.println(solveCase(sc));
        }
        
        sc.close();
    }
}

02. 同质接龙字符串

题目内容

小柯是一位语言学家，他正在研究一种特殊的字符串序列，称为"同质接龙序列"。他手中有一个长度为 $3$ 的初始字符串 $s[1]$ 。

小柯希望基于这个初始字符串，构造出总共 $n$ 个字符串 $s[1], s[2], ..., s[n]$ 组成的序列，要求如下：

对于任意 $i \in [2,n]$ ，必须满足 $s[i]$ 的首字母等于 $s[i-1]$ 的末字母。
序列中每个字符串都与初始字符串 $s[1]$ 包含完全相同的字母种类和数量。

输入描述

第一行输入一个整数 $T(1 \leq T \leq 10)$ ，表示测试数据的组数。

接下来对于每组测试数据，输入一个长度为 $3$ 且仅由小写字母构成的字符串 $s[1]$ 和一个整数 $n(1 \leq n \leq 10^5)$ 。

输出描述

对于每组测试数据，输出一行一个整数，表示不同的方案总数，结果对 $10^9+7$ 取模后输出。

样例1

输入：

2
abc 2
abc 1

输出：

2
1

题解

这道题考察动态规划与记忆化搜索。关键是找到状态定义和转移方式。

核心思路：

每个字符串必须是初始字符串的排列
相邻字符串之间有"接龙"要求
使用状态压缩优化存储

定义状态 dp[pos][x][y][z] 表示：在位置 pos，当前字符串字符为 x,y,z 时的方案数。通过编码可以将状态压缩为 dp[pos][state]。

时间复杂度： $O(n \times k)$ ，其中 k 为字符组合数（常数）。空间复杂度： $O(n \times k)$ 。

参考代码

Python

def calc_ways(txt, num):
    # 字符映射
    ch_map = {}
    idx = 0
    for c in txt:
        if c not in ch_map:
            ch_map[c] = idx
            idx += 1
    
    # 缓存数组
    memo = [{} for _ in range(num+1)]
    
    def count_seq(pos, c1, c2, c3):
        if pos == 1:
            return 1
            
        # 状态编码
        state = c1 + c2*3 + c3*9
        
        if state in memo[pos]:
            return memo[pos][state]
        
        # 计算方案数
        total = 0
        if c1 != c2:
            total = (count_seq(pos-1, c3, c1, c2) +
                     count_seq(pos-1, c3, c2, c1)) % MOD
        else:
            total = count_seq(pos-1, c3, c1, c2)
            
        memo[pos][state] = total
        return total
    
    # 初始状态
    return count_seq(num, ch_map[txt[0]], ch_map[txt[1]], ch_map[txt[2]])

def main():
    cases = int(input())
    for _ in range(cases):
        txt, num = input().split()
        print(calc_ways(txt, int(num)))

if __name__ == "__main__":
    MOD = 10**9 + 7
    main()

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

const int MOD = 1e9 + 7;

// 状态编码
inline int encode(int a, int b, int c) {
    return a + (b << 2) + (c << 4);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int cases;
    cin >> cases;
    
    while(cases--) {
        string txt;
        int num;
        cin >> txt >> num;
        
        // 字符映射
        unordered_map<char, int> ch_map;
        int next_id = 0;
        
        for(char c : txt) {
            if(ch_map.find(c) == ch_map.end()) {
                ch_map[c] = next_id++;
            }
        }
        
        // 状态缓存
        vector<unordered_map<int, int>> memo(num + 1);
        
        // 递归计算
        function<int(int, int, int, int)> calc = [&](int pos, int c1, int c2, int c3) -> int {
            if(pos == 1) 
                return 1;
                
            int key = encode(c1, c2, c3);
            
            if(memo[pos].count(key)) 
                return memo[pos][key];
            
            int res;
            if(c1 == c2) {
                res = calc(pos - 1, c3, c1, c2);
            } else {
                res = calc(pos - 1, c3, c1, c2);
                res = (res + calc(pos - 1, c3, c2, c1)) % MOD;
            }
            
            memo[pos][key] = res;
            return res;
        };
        
        // 计算结果
        cout << calc(num, ch_map[txt[0]], ch_map[txt[1]], ch_map[txt[2]]) << endl;
    }
    
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    
    // 状态编码
    private static int encode(int a, int b, int c) {
        return a | (b << 4) | (c << 8);
    }
    
    private static int calcWays(String txt, int num) {
        // 字符映射
        Map<Character, Integer> chMap = new HashMap<>();
        int nextId = 0;
        
        for(char c : txt.toCharArray()) {
            if(!chMap.containsKey(c)) {
                chMap.put(c, nextId++);
            }
        }
        
        // 状态缓存
        List<Map<Integer, Integer>> memo = new ArrayList<>(num + 1);
        for(int i = 0; i <= num; i++) {
            memo.add(new HashMap<>());
        }
        
        // 递归计算
        return countSeq(num, 
                      chMap.get(txt.charAt(0)), 
                      chMap.get(txt.charAt(1)), 
                      chMap.get(txt.charAt(2)), 
                      memo);
    }
    
    private static int countSeq(int pos, int c1, int c2, int c3, 
                               List<Map<Integer, Integer>> memo) {
        if(pos == 1) {
            return 1;
        }

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

互联网刷题笔试宝典文章被收录于专栏

互联网刷题笔试宝典，这里涵盖了市面上大部分的笔试题合集，希望助大家春秋招一臂之力