【春招笔试】2024-04-28-阿里云-三语言题解

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

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

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

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

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

💌 01.K小姐的红蓝染色方案

问题描述

K小姐拿到了一个由 个正整数组成的数列 ，她准备将其中一些元素染成红色，另外一些元素染成蓝色。K小姐希望染色后红色元素之和与蓝色元素之和相等。

现在，K小姐想知道有多少种不同的染色方案。由于答案可能很大，请输出答案对 取模的结果。

输入格式

第一行包含一个正整数 ，表示数列的长度。

第二行包含 个正整数 ，表示数列中的元素。

输出格式

输出一个整数，表示不同染色方案的数量对 取模的结果。

样例输入

4
1 2 4 3

样例输出

6

数据范围

• 
• 

题解

本题可以使用记忆化搜索的方法来求解。

定义函数 表示当前考虑到第 个元素，已经选择的红色元素之和为 ，蓝色元素之和为 时，从第 个元素开始到最后一个元素的染色方案数量。

对于每个元素，我们有三种选择：

1. 不染色，直接考虑下一个元素，此时方案数为 。

2. 染成红色，此时方案数为 。

3. 染成蓝色，此时方案数为 。

最终的答案即为 。

为了避免重复计算，可以使用记忆化搜索，将已经计算过的状态保存下来。同时，s可以在搜索过程中进行剪枝，如果当前已经选择的红色元素之和或蓝色元素之和超过了数列元素和的一半，那么显然无法满足题目要求，可以直接返回 0。

时间复杂度 ，其中 表示数列元素之和。空间复杂度 。

参考代码

• Python

import sys
sys.setrecursionlimit(10**7)

def main():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    @lru_cache(None)
    def dfs(u, l, r):
        if u == n:
            return int(l == r != 0)
        if max(l, r) > sum(a) // 2:
            return 0
        res = dfs(u+1, l, r)
        res += dfs(u+1, l+a[u], r)
        res += dfs(u+1, l, r+a[u])
        return res % mod
    
    mod = 10**9 + 7
    print(dfs(0, 0, 0))

if __name__ == '__main__':
    main()

• Java

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int[] a;
    static int[][] memo;
    static final int MOD = (int)1e9 + 7;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        a = new int[n];
        String[] str = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(str[i]);
        }
        
        int sum = Arrays.stream(a).sum();
        memo = new int[n][sum+1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        
        System.out.println(dfs(0, 0, 0));
    }
    
    static int dfs(int u, int l, int r) {
        if (u == n) {
            return l == r && l != 0 ? 1 : 0;
        }
        if (Math.max(l, r) > Arrays.stream(a).sum() / 2) {
            return 0;
        }
        if (memo[u][l] != -1) {
            return memo[u][l];
        }
        int res = dfs(u+1, l, r);
        res = (res + dfs(u+1, l+a[u], r)) % MOD;
        res = (res + dfs(u+1, l, r+a[u])) % MOD;
        return memo[u][l] = res;
    }
}

• Cpp

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MOD = 1e9 + 7;

int n;
vector<int> a;
vector<vector<LL>> memo;

LL dfs(int u, int l, int r) {
    if (u == n) {
        return l == r && l != 0;
    }
    if (max(l, r) > accumulate(a.begin(), a.end(), 0) / 2) {
        return 0;
    }
    if (memo[u][l] != -1) {
        return memo[u][l];
    }
    LL res = dfs(u+1, l, r);
    res = (res + dfs(u+1, l+a[u], r)) % MOD;
    res = (res + dfs(u+1, l, r+a[u])) % MOD;
    return memo[u][l] = res;
}

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int sum = accumulate(a.begin(), a.end(), 0);
    memo.assign(n, vector<LL>(sum+1, -1));
    
    cout << dfs(0, 0, 0) << endl;
    
    return 0;
}

🎀 02.LYA的魔法操作

问题描述

LYA拥有一个长度为 的数组 ，他可以对数组进行任意次以下三种魔法操作：

1. 选择 ，将 和 合并为一个数字，结果为 （ 表示按位与运算）。
2. 选择 ，将 和 合并为一个数字，结果为 （ 表示按位或运算）。
3. 选择 ，将 和 交换位置。

（以上三种操作可以执行任意次，前提是数组长度 至少为 。每次操作执行完后， 都会减少 ，除了第三种操作）

LYA希望通过魔法操作使得数组的极差最大化，极差的定义为数组最大值与最小值之间的差值。请你帮助LYA求出可以得到的最大极差。

输入格式

第一行包含一个正整数 （），表示数组 的长度。

第二行包含 个整数 （），表示数组 的元素。

输出格式

输出一个整数，表示可以得到的最大极差。

样例输入

6
2 2 3 1 1 6

样例输出

7

数据范围

• 
• 

题解

本题可以使用前缀按位与和后缀按位或的思想来解决。

假设我们选择第 个位置进行划分，那么Left部分应该全部执行按位与操作，Right部分应该全部执行按位或操作。这样Left部分的结果一定小于等于Right部分的结果，才能使得极差最大。

因此，我们可以预处理出每个位置 右边部分执行按位或操作的结果 ，然后从左到右扫描数组，维护Left部分执行按位与操作的结果 ，并更新答案 。

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

参考代码

• Python

n = int(input())
a = list(map(int, input().split()))

f = [0] * (n + 1)
for i in rang