【25届秋招】蚂蚁集团 0825算法岗笔试

⏰ 时间：2024/08/25
🔄 输入输出：ACM格式
⏳ 时长：100min

本试卷分为单选，多选，编程三部分，这里只展示编程题。

1. 第一题

题目描述

Alice 和 Bob 相识。

心动数组的定义为遇到一个人的缘分。Alice 有一个长度为 $n$ 的心动数组 $a$，Bob 有一个长度为 $n$ 的心动数组 $b$。月老认为两个人的缘分 $G$ 取决于：

$$G=\underset{1\le i,j\le n}{\max }(a_i\times b_j)$$

请帮助 Alice 和 Bob 求出缘分 $G$。

输入描述

第一行输入一个整数 $n$ $(1\le n\le 2\times 10^5)$，代表数组中元素的个数。
第二行输入 $n$ 个整数 $a_1,a_2,\dots ,a_n$ $(-10^6\le a_i\le 10^6)$，代表 Alice 的心动数组中的元素。
第三行输入 $n$ 个整数 $b_1,b_2,\dots ,b_n$ $(-10^6\le b_i\le 10^6)$，代表 Bob 的心动数组中的元素。

输出描述

在一行上输出一个整数，代表他们的缘分 $G$。

题解

本题要对四种情况取最大值。

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

max_a = max(a)
min_a = min(a)
max_b = max(b)
min_b = min(b)

ans = max(max_a * max_b, min_a * max_b, max_a * min_b, min_a * min_b)
print(ans)

2. 第二题

题目描述

支持向量机（SVM）是一种常见的分类算法，其基本思想是找到一个超平面，使得两个类别的样本被该超平面分开，并且距离超平面最近的样本点（即支持向量）到超平面的距离最远。在 SVM 的对偶问题中，我们需要求解一组拉格朗日乘数。在此题目中，我们将简化这个问题，仅考虑两类问题，并且所有数据都是线性可分的。我们将使用硬间隔 SVM，即不考虑噪声和异常点的影响。

请根据输入描述和输出描述中的要求，编程计算拉格朗日乘数。

输入描述

输入的数据集为一个二维 list，该二维 list 中每一个子 list 的前两个元素表示样本的两个特征值，最后一个元素表示样本的类别标签，其中 1 表示正类，-1 表示负类。例如：[[1.0, 2.0, 1], [2.0, 3.0, -1]]。所有的特征值都是浮点数。其中终端输入每行表示一个子 list，数字之间以空格间隔。

输出描述

假设 SVM 的对偶问题的解是唯一的。输出为一个一维 list，表示每个样本的拉格朗日乘数，保留两位小数，用字符串形式表示。例如：['0.20', '0.20']。

补充说明

1. 支持使用 Python 中的 numpy、scipy、pandas、scikit-learn 等库。
2. 在保留两位小数时，如果结果为 -0.00，应统一输出为 '0.00'。

题解

按照题目定义求解即可。

import sys
import numpy as np
from scipy.optimize import minimize

def svm_dual_problem_solver(data):
    X = np.array([d[:2] for d in data])
    y = np.array([d[2] for d in data])
    n_samples = len(y)
    
    def objective(alpha):
        return 0.5 * np.sum([
            alpha[i] * alpha[j] * y[i] * y[j] * np.dot(X[i], X[j])
            for i in range(n_samples) for j in range(n_samples)
        ]) - np.sum(alpha)

    cons = {'type': 'eq', 'fun': lambda alpha: np.dot(alpha, y)}
    bounds = [(0, 1e6) for _ in range(n_samples)]
    alpha0 = np.zeros(n_samples)
    solution = minimize(objective, alpha0, bounds=bounds, constraints=cons)
    alphas = solution.x
    formatted_alphas = [f"{max(0, round(alpha, 2)):.2f}" for alpha in alphas]

    return formatted_alphas

data = []
for line in sys.stdin:
    line = list(map(float, line.strip().split()))
    data.append(line)

print(svm_dual_problem_solver(data))

3. 第三题

题目描述

小菜面前有一排 $n$ 个格子，编号从 $1$ 到 $n$，每个格子上都有一个数字 $a_i$，最初所有格子都是白色的，他现在希望将所有格子都染红。具体的，他可以做任意多次下方的操作：

• 将他目前所在的格子染红，花费为 $a_i$；
• 从红色的 $i$ 号格子瞬移到任意一个红色格子 $j$，花费为 $0$；
• 从红色的 $i$ 号格子瞬移到任意一个白色格子 $j$，花费为最小公倍数 $\text{lcm}(a_i,a_j)$。

小菜初始时位于 $1$ 号格子，他想知道将所有的格子都染红，最少需要花费多少，请你帮助他吧。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T$ $(1\le T\le 1000)$ 表示数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n$ $(1\le n\le 2000)$，代表格子数。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 2000)$，代表每个格子上的数字。

除此外，保证所有的测试数据中 $n$ 的总和不超过 $2000$。

输出描述

对于每一组测试数据，在一行上输出一个整数，表示最少花费。

题解

我们可以将格子和它们之间的瞬移费用看作图中的节点和边。每个格子对应一个节点，节点之间的边的权重表示从一个红色格子瞬移到一个白色格子的费用。初始时，所有节点都是白色的。小菜从格子 $1$ 开始，所以他首先需要将这个格子染为红色，花费为 $a_1$。

接下来，我们的目标是最小化将所有格子染为红色的总费用。这个过程可以使用最小生成树的方法来解决。我们可以将每个格子视为图中的一个节点，而通过计算 $\text{lcm}(a_i,a_j)$ 的边连接所有的节点。图的边权为边的瞬移费用。

具体步骤如下：

1. 初始时，小菜染红格子 $1$，因此总花费增加 $a_1$。
2. 计算所有可能的格子之间的瞬移费用，即边的权重为 $\text{lcm}(a_i,a_j)$，并构建边的列表。
3. 利用并查集结构来处理节点的连接性，合并那些可以通过瞬移费用染红的格子。
4. 使用 Kruskal 或 Prim 算法构造最小生成树，从而求出最小总费用。对于每一条新边，如果连接的两个节点属于不同的集合，则将它们合并，并将瞬移费用加到总花费中。

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
const int MAXN = 2005;

class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }

    void unite(int x, int y) {
        parent[find(x)] = find(y);
    }
};

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

void solve() {
    int n;
    cin >> n;

    UnionFind uf(n + 1);
    vector<int> magic(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> magic[i];
    }

    vector<tuple<int, int, int>> edges;

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            edges.emplace_back(lcm(magic[i], magic[j]), i, j);
        }
    }

    sort(edges.begin(), edges.end());

    i64 total_magic_value = accumulate(magic.begin() + 1, magic.begin() + n + 1, 0LL);

    for (auto [cost, u, v] : edges) {
        if (uf.find(u) != uf.find(v)) {
            uf.unite(u, v);
            total_magic_value += cost;
        }
    }

    cout << total_magic_value << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}