✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

蚂蚁-2026.04.02-研发岗

这套题是标准的 3 道编程题。

第一题是数论判定，检查去重、相邻互质和间隔 的公因数条件。

第二题把跨分割点的按位与和拆到每一位上，做前后缀计数。

第三题是字符串前后缀题，答案取决于最长可用 border，线性做法用 KMP 即可。

1. 小基 的序列互检

问题描述

小基 正在整理一批按顺序记录的任务编号。

系统会用一套固定规则检查这批编号是否“结构正常”。给定一个长度为 的正整数序列 ，如果它同时满足下面三条规则，就称这组序列通过检查：

• 对所有 ，都有 。
• 对所有 ，都有 。
• 对所有 ，都有 。

这里 表示整数 和 的最大公约数。

请你判断每组数据是否通过检查。

输入格式

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

• 第一行输入一个整数 ，表示数据组数。
• 对于每组数据：
  • 第一行输入两个整数 。
  • 第二行输入 个正整数 。

输出格式

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

• 如果序列通过检查，输出 Yes。
• 否则输出 No。

样例输入

3
5 2
10 21 22 39 34
4 3
10 21 22 25
5 2
2 3 5 7 11

样例输出

Yes
Yes
No

数据范围

• 
• 
• 
• 单个测试文件内所有数据组的 之和不超过

样例	解释说明
样例 1	第 1 组相邻位置都互质，间隔 的位置公约数都大于 ，并且没有重复数字，所以输出 Yes。第 2 组只有一对间隔 的元素，，同样满足要求。第 3 组里 ，不满足第二条规则，所以输出 No。

题解

这题没有隐藏结构，直接把三条规则拆开检查就行。

第一条和第二条都只需要在原数组上顺序扫描：

• 相邻位置检查一次；
• 相差 的位置再检查一次。

剩下的一条“所有数字互不相同”也不复杂。做一份副本排序后，只要发现相邻两个数相等，就能立刻判掉。

所以整道题可以写成很直白的流程：

1. 复制数组并排序，检查是否有重复值。
2. 扫描所有相邻位置，判断公约数是否都是 。
3. 扫描所有相差 的位置，判断公约数是否都大于 。

只要中途有一条不满足，答案就是 No；全部通过就是 Yes。

复杂度分析

• 排序判重的复杂度是 。
• 两次线性扫描的复杂度都是 。

所以单组数据总复杂度是 ，空间复杂度是 。

参考代码

• Python

import math
import sys

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


def check(arr, k):
    # 排序后只要出现相邻相等，就说明原数组里有重复值。
    b = sorted(arr)
    for i in range(1, len(arr)):
        if b[i] == b[i - 1]:
            return False

    # 第一条规则：每一对相邻元素都要互质。
    for i in range(len(arr) - 1):
        if math.gcd(arr[i], arr[i + 1]) != 1:
            return False

    # 第二条规则：相差 k 的两个位置必须有公共因子。
    for i in range(len(arr) - k):
        if math.gcd(arr[i], arr[i + k]) == 1:
            return False

    return True


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

    for _ in range(t):
        _, k = map(int, input().split())
        arr = list(map(int, input().split()))
        out.append("Yes" if check(arr, k) else "No")

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


if __name__ == "__main__":
    solve()

• Cpp

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

bool checkSeq(const vector<long long>& a, int k) {
    vector<long long> b = a;
    // 排序后判重，比在 long long 数组上手写哈希更稳。
    sort(b.begin(), b.end());
    for (int i = 1; i < (int)b.size(); ++i) {
        if (b[i] == b[i - 1]) {
            return false;
        }
    }

    // 检查所有相邻位置是否互质。
    for (int i = 0; i + 1 < (int)a.size(); ++i) {
        if (std::gcd(a[i], a[i + 1]) != 1LL) {
            return false;
        }
    }

    // 检查所有相距 k 的位置是否存在公共因子。
    for (int i = 0; i + k < (int)a.size(); ++i) {
        if (std::gcd(a[i], a[i + k]) == 1LL) {
            return false;
        }
    }

    return true;
}

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

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;

        vector<long long> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }

        cout << (checkSeq(a, k) ? "Yes" : "No") << '\n';
    }
    return 0;
}

• Java

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

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

    private static boolean check(long[] arr, int k) {
        long[] b = arr.clone();
        // 先排序判重，重复值会直接破坏第三条规则。
        Arrays.sort(b);
        for (int i = 1; i < b.length; i++) {
            if (b[i] == b[i - 1]) {
                return false;
            }
        }

        // 逐对检查相邻位置是否互质。
        for (int i = 0; i + 1 < arr.length; i++) {
            if (gcd(arr[i], arr[i + 1]) != 1L) {
                return false;
            }
        }

        // 再检查所有相差 k 的位置。
        for (int i = 0; i + k < arr.length; i++) {
            if (gcd(arr[i], arr[i + k]) == 1L) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();
        int t = fs.nextInt();

        while (t-- > 0) {
            int n = fs.nextInt();
            int k = fs.nextInt();
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = fs.nextLong();
            }

            sb.append(check(arr, k) ? "Yes" : "No").append('\n');
        }

        System.out.print(sb);
    }

    private static class FastScanner {
        private final InputStream in;
        private final byte[] buf = new byte[1 << 16];
        private int ptr = 0;
        private int len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

        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 sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

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

        int nextInt() throws IOException {
            return (int) nextLong();
        }
    }
}

2. 小兰的切分按位值

问题描述

小兰拿到一段按时间顺序排好的特征值数组 。

她准备在某个位置切一刀，把数据拆成左右两段做对照分析。设分割点为 ，其中 ，切开后得到：

• 左段 ；
• 右段 。

定义这个分割点的数值为：

其中 表示按位与运算。

请你求出所有分割点中， 的最大值。

输入格式

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

• 第一行输入一个整数 ，表示数据组数。
• 对于每组数据：
  • 第一行输入一个整数 。
  • 第二行输入 个非负整数 。

输出格式

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

样例输入

3
4
5 2 7 1
5
1 1 1 1 1
3
8 1 8

样例输出

8
6
8

数据范围

• 
• 
• 
• 单个测试文件内所有数据组的 之和不超过

样例	解释说明
样例 1	第 1 组取 时，跨分割点的按位与和为 。第 2 组所有元素都是 ，最优切法是左右长度为 和 ，答案为 。第 3 组无论取哪个分割点，答案都是 。

题解

这题看起来是枚举一个分割点，然后把左右两边所有配对都算一遍。

如果真这么做，单个分割点就可能是平方级，显然不行。

真正能压下复杂度的地方在于：按位与可以按二进制位拆开。

每一位独立计算

固定某一位 。

只有当左边选到的数这一位是 ，右边选到的数这一位也是 时，这一对数才会给答案贡献 。

所以对当前分割点来说，这一位的贡献就是：

其中：

• 表示左边这一位为 的数有多少个；
• 表示右边这一位为 的数有多少个。

把所有二进制位的贡献加起来，就是这个分割点的总值。

这一步可以理解成“把所有跨界配对按位分桶”：

• 这一位左边有多少个 ；
• 这一位右边有多少个 ；
• 这两批数随便两两配，就得到 对有效贡献。

每一对都会贡献同一个 ，所以直接乘起来就行。

怎么枚举分割点

先统计整段数组中每一位一共有多少个 ，把它当作右边计数。

然后从左到右枚举分割点。每前进一步，相当于把一个新元素从右边移到左边：

• 这个元素在哪些位上是 ，就把对应的右边计数减一；
• 同时把左边计数加一。

更新完成后，就能用上面的公式算出当前分割点的值。

因为总共只有大约 个二进制位，所以每个分割点只要做一小段常数级统计。

复杂度分析

设有效二进制位数是 ，这里取 就够了。

• 统计初始计数的复杂度是 。
• 枚举所有分割点并计算答案的复杂度也是 。

总复杂度是 ，空间复杂度是 。

参考代码

• Python

import sys

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


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

    for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))

        # rt[b] 记录当前分割