✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

阿里云-2026.04.01-研发岗-第二套

这套题分成三块：同余类、括号失配、换根 LCA。

1. 小基 的循环余数观测

问题描述

小基 在调试一台循环计数器。第 次采样得到的原始数值为：。

系统不会直接保存这个原始数值，而是只保留它对 取模后的结果，也就是 ，其取值范围始终在 内。

现在给定 、 和 。请你在所有 中，求出 的最大可能值。

输入格式

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

• 第一行输入一个整数 ，表示数据组数。
• 对于每组测试数据，输入一行三个整数 。

输出格式

对于每组测试数据，输出一行一个整数，表示能够取得的最大模值。

样例输入

3
5 4 7
3 10 6
100 100 100

样例输出

6
5
0

数据范围

• 
• 
• 

样例	解释说明
样例1 第 1 组	数列是 。对 取模后会出现 ，最大值是 。

题解

这题看起来像要在无穷多个位置里枚举最大值，但真正决定结果的不是项数，而是步长在模 意义下能走出哪些余数。

先记：。

为什么只会落在同一个余数类里

数列中任意两项之差都是 。因为 同时整除 和 ，所以它也整除所有的 。这意味着所有 在模 意义下都和 同余。

也就是说，所有可达余数一定长成下面这个样子：。

其中：。

为什么这些值又都真的能取到

裴蜀定理说明，模 下由不断加上 产生的循环，步长本质上等价于加上 。因此所有与 同余、并且落在 内的数都会被某一项命中。

所以可达集合恰好就是：。

其中最后一个数仍然必须小于 。

最大值怎么直接写出来

最后一个可达值一定是离 最近、同时又和 同余的那个数。

因为 ，所以答案就是：。

把 代回去，得到最终公式：。

整题只需要求一次最大公约数，之后直接代公式即可。

复杂度分析

• 时间复杂度：，主要来自求 。
• 空间复杂度：。

参考代码

• Python

import math
import sys

input = lambda: sys.stdin.readline().strip()


def solve() -> None:
    t = int(input())
    out = []

    for _ in range(t):
        a, d, m = map(int, input().split())

        # 可达余数的步长在模 m 意义下等价于 gcd(d, m)。
        g = math.gcd(d, m)

        # 所有可达余数都与 a % g 同余，最大那个就是 m-g+r。
        r = a % g
        out.append(str(m - g + r))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

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

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

    int t;
    cin >> t;
    while (t--) {
        long long a, d, m;
        cin >> a >> d >> m;

        // 模 m 下的有效步长会收缩成 gcd(d, m)。
        long long g = std::gcd(d, m);

        // 所有可达值都与 a % g 同余，取不超过 m-1 的最大那个。
        long long r = a % g;
        cout << m - g + r << '\n';
    }
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    static class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }

            long val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sgn;
        }
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

        int t = (int) fs.nextLong();
        while (t-- > 0) {
            long a = fs.nextLong();
            long d = fs.nextLong();
            long m = fs.nextLong();

            // 可达余数的间隔由 gcd(d, m) 决定。
            long g = gcd(d, m);

            // 先算出最小的那个同余类代表，再直接跳到不超过 m-1 的最大值。
            long r = a % g;
            out.append(m - g + r).append('\n');
        }

        System.out.print(out);
    }
}

2. 小兰的括号紧急修复

问题描述

小兰 收到了一段只由 ( 和 ) 组成的括号脚本。她希望通过尽量少的修改，把这段脚本修复成平衡括号序列。

一个括号序列被称为平衡的，当且仅当满足下面的递归定义：

• 空串是平衡的。
• 如果字符串 是平衡的，那么 (A) 也是平衡的。
• 如果字符串 和 都是平衡的，那么它们的拼接 也是平衡的。

例如，() 和 (()) 是平衡括号序列，而 )、)()、( 不是。

现在给定一个长度为偶数的字符串 。你可以进行若干次操作，每次选择一个位置 ，把该位置的括号翻转：

• ( 变成 )。
• ) 变成 (。

请输出把 变成平衡括号序列所需的最少操作次数，并给出任意一组最优操作位置。

输入格式

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

• 第一行输入一个整数 ，表示数据组数。
• 对于每组测试数据：
  • 第一行输入一个偶数 。
  • 第二行输入一个长度为 的字符串 ，只包含 ( 和 )。

保证所有测试数据中， 的总和不超过 。

输出格式

对于每组测试数据输出两行：

• 第一行输出一个整数 ，表示最少操作次数。
• 第二行输出 个整数，表示要翻转的位置。

如果 ，第二行留空即可。若存在多组最优方案，输出任意一组。

样例输入

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

样例输出

2
1 2
0

2
1 4

数据范围

• 
• 
• 是偶数
• 只包含 ( 和 )
• 所有测试数据中， 的总和不超过

样例	解释说明
样例1 第 1 组	把位置 都翻转后，)( 会变成 ()。
样例1 第 2 组	原串已经平衡，不需要任何操作。
样例1 第 3 组	把位置 和 翻转后，))((' 会变成 ()()。

题解

这题的关键不是直接想“每次翻哪一个最赚”，而是先把原串里本来就合法的部分全部消掉。

第一步：把已经能配对的括号全部抵消

从左到右扫描字符串：

• 遇到 (，把它的位置压进栈。
• 遇到 ) 时：
  • 如果栈里还有没匹配的 (，就把这一对直接抵消。
  • 否则，这个 ) 只能暂时算作“多出来的右括号”，把它的位置记下来。

扫描结束后：

• 栈里剩下的都是没被匹配掉的 (。
• 额外记录的数组里都是没被匹配掉的 )。

第二步：剩余结构一定是“前面全是右括号，后面全是左括号”

为什么会这样？

• 任何还能配对的 ( 和 ) 在扫描时都已经被消掉了。
• 因此剩下的 ) 不可能出现在某个未匹配 ( 的右边，否则它们还能继续配。

所以剩下的无效部分一定等价于：。

也就是前半段全是多余的右括号，后半段全是多余的左括号。

第三步：最少翻多少个

设：

• 未匹配的右括号个数为 。
• 未匹配的左括号个数为 。

把两个连续的 ) 翻成 ()，就能修好一对问题；奇数个时会多剩一个，因此右括号这边最少需要 次翻转。

左括号那边完全对称，最少需要 次翻转。

因此最优答案就是：。

第四步：怎么输出一组最优方案

• 对未匹配的右括号，翻转最前面的 个。
• 对未匹配的左括号，翻转最后面的 个。

这样改完以后，左边会尽量补出需要的 (，右边会尽量补出需要的 )，正好可以拼成平衡结构。

复杂度分析

设一组数据长度为 。

• 时间复杂度：。
• 空间复杂度：。

而所有测试数据的总长度不超过 ，因此可以轻松通过。

参考代码

• Python

import sys

input = lambda: sys.stdin.readline().strip()


def solve() -> None:
    t = int(input())
    out = []

    for _ in range(t):
        n = int(input())
        s = input()

        stk = []
        bad = []

        for i, ch in enumerate(s, start=1):
            if ch == '(':
                # 记录还没配对的左括号位置。
                stk.append(i)
            elif stk:
                # 当前右括号能和最近的左括号配对，直接抵消。
                stk.pop()
            else:
                # 没法配对时，它就是多出来的右括号。
                bad.append(i)

        ans = []

        # 右括号这边取前半部分进行翻转。
        rc = (len(bad) + 1) // 2
        ans.extend(bad[:rc])

        # 左括号这边取后半部分进行翻转。
        lc = (len(stk) + 1) // 2
        if lc:
            ans.extend(stk[-lc:])

        out.append(str(len(ans)))
        out.append(" ".join(map(str, ans)))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

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

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;

        vector<int> stk;
        vector<int> bad;

        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') {
                // 还没有被匹配的左括号位置。
                stk.push_back(i + 1);
            } else if (!stk.empty()) {
                // 当前右括号可以和最近的左括号抵消。
                stk.pop_back();
            } else {
                // 只能留下来作为多余的右括号。
                bad.push_back(i + 1);
            }
        }

        vector<int> ans;

        // 翻转最前面的 ceil(r / 2) 个未匹配右括号。
        int rc = (static_cast<int>(bad.size()) + 1) / 2;
        for (int i = 0; i < rc; ++i) {
            ans.push_back(bad[i]);
        }

        // 翻转最后面的 ceil(l / 2) 个未匹配左括号。
        int lc = (static_cast<int>(stk.size()) + 1) / 2;
        for (int i = static_cast<int>(stk.size()) - lc; i < (int)stk.size(); ++i) {
            if (i >= 0) {
                ans.push_back(stk[i]);
            }
        }

        cout << ans.size() << '\n';
        for (int i = 0; i < (int)ans.size(); ++i) {
            if (i) {
                cout << ' ';
            }
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    static class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }