阿里笔试,都是数学题(0401春招实习笔试真题解析)

3
5 4 7
3 10 6
100 100 100

6
5
0

#include <iostream>
#include <numeric>

using namespace std;
typedef long long ll;

void solve() {
    ll a, d, m;
    cin >> a >> d >> m;
    ll g = std::gcd(d, m);
    // 直接计算并输出结果
    cout << m - g + (a % g) << "\n";
}

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

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

第二题

在线做题链接：https://niumacode.com/

题意

我们称一个括号序列为“平衡的括号序列”，当且仅当满足以下归纳定义：

1. 空串是平衡的；
2. 若字符串 A 是平衡的，则“(A)”是平衡的；
3. 若字符串 A 与 B 均是平衡的，则“AB”（连接）是平衡的。 例如：括号序列()与(())是平衡的；而)、)()、(不是。

给定一个只由(与)组成、长度为 n 的字符串 s (n 为偶数)。你可以进行若干次如下操作： 选择一个下标 i (1 <= i <= n)，将字符 s_i 的“类型”镜像翻转：若 s_i = '(' 则变为 ')'；若 s_i = ')' 则变为 '('。其余位置保持不变。

请你计算使 s 变为平衡括号序列所需的最少操作次数，并输出任意一组达到最少次数的操作下标序列。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T (1 <= T <= 10^5) 表示数据组数。每组测试数据描述如下： 第一行输入一个偶数 n (2 <= n <= 2 * 10^5)； 第二行输入一个长度为 n 的字符串 s (仅包含字符'('与')')。 保证所有测试中 n 的总和不超过 2 * 10^5。

输出描述

对于每组测试数据，输出两行： 第一行输出一个整数 k，表示最少操作次数； 第二行输出 k 个整数 p1, p2, ..., pk (1 <= pj <= n)，表示依次在位置 pj 处进行单点镜像翻转。若 k = 0，第二行留空即可。 若存在多组最优方案，输出任意一组。

示例1：

输入：

3
2
)(
4
()()
4
))((

输出：

6
5
0

说明： 样例一：依次翻转位置 1, 2，)( -> ()，最少 2 次。 样例二：s 已是平衡串，k = 0，第二行留空。 样例三：翻转位置 1 与 4，))(( -> ()()，最少 2 次。

思路与代码

采用“栈模拟 + 贪心”的策略。首先利用栈剔除掉原串中已经合法匹配的括号对。 剔除完毕后，残留的无效序列必定呈现 "))))(((((" 的极端形态（左半段全为右括号，右半段全为左括号）。 为保证用最少操作次数达到整体平衡，我们只需贪心地将左半侧前一半的 ')' 进行翻转， 并将右半侧后一半的 '(' 进行翻转。将这些位置的索引提取出来即可。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void solve() {
    int len;
    string str;
    cin >> len >> str;

    vector<int> stk, R_fail;
    // 线性遍历，抵消合法括号
for (int i = 0; i < len; ++i) {
if (str[i] == '(') {
            stk.push_back(i + 1);
        } else {
if (!stk.empty()) {
                stk.pop_back();
            } else {
                R_fail.push_back(i + 1);
            }
        }
    }

    vector<int> ans;
    // 处理剩余的右括号（取前一半向上取整）
    int r_sz = R_fail.size();
for (int i = 0; i < (r_sz + 1) / 2; ++i) {
        ans.push_back(R_fail[i]);
    }

    // 处理剩余的左括号（取后一半向上取整）
    int l_sz = stk.size();
    int l_half = (l_sz + 1) / 2;
for (int i = l_sz - l_half; i < l_sz; ++i) {
        ans.push_back(stk[i]);
    }

    // 格式化输出
    cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); ++i) {
        cout << ans[i] << (i == ans.size() - 1 ? "" : " ");
    }
    cout << "\n";
}

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

    int tc;
if (cin >> tc) {
for (int i = 0; i < tc; ++i) {
            solve();
        }
    }
return 0;
}

第三题

在线做题链接：https://niumacode.com/

题意

在多元宇宙的中心，存在着一个名为“时空枢纽”的巨大网络。这个网络由 n 个时空节点组成，它们通过稳定的因果律路径连接，构成了一棵宏伟的宇宙树。通常，整个网络以创世节点（节点 1）为根进行校准。 然而，来自“混沌象限”的观察者们拥有改变宇宙视界的能力。他们可以任意指定一个时空节点作为临时的“观测奇点”，从而使整个宇宙树的因果流向以该节点为根重新定向。作为时空枢纽的守护者，你必须能够在这种动态的重构中，迅速定位任意两个节点在新的因果结构下的最近共同起源。

给定一个由 n 个节点构成的树。你需要处理 q 次查询。对于每次查询，给定三个节点 (r, u, v)。你需要回答：如果将节点 r 作为整棵树的根，那么节点 u 和 v 的最近公共祖先是哪个节点？

【名词解释】 树：指这样的一张图，其由 n 个节点和 n-1 条边构成，其上的任意两个点都连通，且不存在环。 最近公共祖先：在一棵有根树中，节点 u 和 v 的最近公共祖先指同时位于“根到 u 的路径”和“根到 v 的路径”上的节点中，距离根节点最远的一个。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T (1 <= T <= 2 * 10^5) 代表数据组数，每组测试数据描述如下： 第一行输入两个整数 n, q (1 <= n, q <= 2 * 10^5)，分别代表节点数和查询数。 此后 n-1 行，第 i 行输入两个整数 xi, yi (1 <= xi, yi <= n, xi != yi)，表示树上第 i 条边连接节点 xi 和 yi。 此后 q 行，第 i 行输入三个整数 ri, ui, vi (1 <= ri, ui, vi <= n)，代表第 i 次查询。 除此之外，保证单个测试文件的 n 之和、q 之和均不超过 2 * 10^5。

输出描述

对于每组测试数据，输出 q 行，第 i 行输出一个整数，代表第 i 次查询的答案。

示例：

输入：

1
7 5
1 2
1 3
2 4
2 5
3 6
3 7
1 4 7
4 1 7
2 4 5
5 1 2
6 4 7

输出：

1
1
2
2
3

说明： 对于第一组测试数据，树的结构如下： 1 / 
2   3 / \ / 
4 5 6 7 对于第一次查询，将节点 1 作为根： 从节点 4 到根 1 的路径是 4 -> 2 -> 1。 从节点 7 到根 1 的路径是 7 -> 3 -> 1。 两条路径在节点 1 处汇合，因此 1 是它们的最近公共祖先。输出 1。 对于第二次查询，将节点 4 作为根： 从节点 1 到根 4 的路径是 1 -> 2 -> 4。 从节点 7 到根 4 的路径是 7 -> 3 -> 1 -> 2 -> 4。 在这个新的结构中，节点 1 位于节点 7 到根 4 的路径上，因此 1 是 7 的祖先。输出 1。

思路与代码

考察树的动态换根最近公共祖先（LCA）技巧。由于实际重构树状结构代价极高， 我们的做法是：始终保持以节点 1 为固定根，并在初始时利用 DFS 预处理出全局的深度与倍增表。 当需要查询以新节点 r 为根时 u 和 v 的 LCA，可以通过在原树中分别求出： LCA(u, v)、LCA(u, r) 以及 LCA(v, r)。这三个返回值中，在原树里深度值最大的那一个节点， 必定是新树拓扑结构下真正的最近公共祖先。

#include <iostream>
#include <vector>

using namespace std;

const int N = 200005;
vector<int> G[N];       // 邻接表
int dep[N], fa[N][20];  // 深度与倍增祖先数组

// DFS 预处理原树信息
void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u][0] = p;
for (int i = 1; i < 20; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
for (int v : G[u]) {
if (v != p) {
            dfs(v, u);
        }
    }
}

// 标准倍增求 LCA
int get_lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
    // 先将较深的节点向上跳到同一深度
for (int i = 19; i >= 0; --i) {
if (dep[fa[x][i]] >= dep[y]) {
            x = fa[x][i];
        }
    }
if (x == y) return x;
    // 两节点一起向上跳，直到 LCA 的子节点
for (int i = 19; i >= 0; --i) {
if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
return fa[x][0];
}

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

    // 初始化清空
for (int i = 1; i <= n; ++i) {
        G[i].clear();
    }

    // 建树
for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dep[0] = 0;
    dfs(1, 0); // 始终以 1 为基准根

    // 处理每次换根查询
while (q--) {
        int r, u, v;
        cin >> r >> u >> v;

        int lca1 = get_lca(u, v);
        int lca2 = get_lca(u, r);
        int lca3 = get_lca(v, r);

        // 寻找三个结果中深度最大的点
        int ans = lca1;
if (dep[lca2] > dep[ans]) ans = lca2;
if (dep[lca3] > dep[ans]) ans = lca3;

        cout << ans << "\n";
    }
}

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

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

我们是一个针对技术岗（前后端开发、测试、测开、大数据开发、大模型、ai等相关岗位）校招一对一进阶提高的工作室。我们从2020年2月份开始，迄今整整六年的时间，带领900+学员斩获4000+中大厂offer，参加活动的同学人均5个中大厂offer以上，以下是我们活动内容的介绍！

万诺coding

我们主要是针对有一定基础的同学提供全程一对一笔试、面试辅导，针对每个同学不同的情况定制内容，包括但不限于“笔试及面试算法”/“基础八股/“项目及实习梳理”/“面试技巧”/“面试复盘”等内容。

摸底测试：如果有兴趣深入了解我们的活动，需要先参加我们的“摸底测试”（类似面试），方便我们了解你的具体情况（主要是code能力和计算机素养），定制出相应的辅导计划。摸底测试后，我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。 

承诺保offer：通过摸底测试后，我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。

有兴趣的同学可以扫码添加我们的微信（whynotlab）