大厂真题 / 蚂蚁

蚂蚁 4.16 笔试真题 - 研发岗

本场考试概述

考试时间：2026年4月16日 考试岗位：研发岗 难度评级：中等偏难

考点分析：

第一题：构造 + 数学分析（难度中等）
第二题：有序集合 + 最大间隔维护（难度中等）
第三题：容斥原理 + 二分答案（难度困难）

建议策略：

第一题核心是分类讨论找规律，按奇偶性分情况构造即可，优先拿满分
第二题有序集合 + multiset 是标准做法，熟悉 SortedList 可快速 AC
第三题需要质因子分组 + 容斥计数 + 二分答案，预处理量大，考场上能想到框架就很不错

第一题：仅含1和合数的数组

题目描述

给定一个正整数 n，找到一个长度至少为 2 的数组，使得数组中仅包含 1 和合数（大于 1 且有非平凡因子的正整数，如 4、6、8、9 等），且所有元素之和为 n。如果有多个满足条件的数组，输出长度最短的；如果有多个长度最短的，输出任意一个。

多组测试数据，第一行输入 T，每组输入一个正整数 n。

样例

输入

输出

思路分析

第一步：明确可用元素

数组中每个元素只能是 1 或合数。注意 2 和 3 是质数，不是合数，不能出现在数组中。因此可用的元素为：1, 4, 6, 8, 9, 10, 12, …，最小的合数是 4。

第二步：目标——尽量用长度 2

我们希望数组尽量短。长度为 1 不满足”至少为 2”的要求，所以最优目标是长度 2：找到两个数 a、b（各为 1 或合数），使 a + b = n。

要凑出长度 2 的数组，组合只有三种形式：

[1, n-1]：需要 n-1 是合数
[合数 x, n-x]：需要 x 和 n-x 都是合数

第三步：发现偶数的关键性质

一个关键观察：任何 >= 4 的偶数一定是合数。因为它能被 2 整除，又大于 2，所以一定有非平凡因子。

利用这一点：

n 为奇数且 >= 7：取 [1, n-1]。n-1 是 >= 6 的偶数，一定是合数。长度 2。
n 为偶数且 >= 8：取 [4, n-4]。n-4 是 >= 4 的偶数，一定是合数。长度 2。

第四步：处理小数特殊情况

n = 2 到 6 需要逐个分析，因为上面的通用构造不适用：

n	长度 2 可行？	最短构造	长度
2	[1,1] ✓	[1, 1]	2
3	[1,2] ✗（2是质数）	[1, 1, 1]	3
4	[1,3] ✗ [4,0] ✗	[1, 1, 1, 1]	4
5	[1,4] ✓	[1, 4]	2
6	[1,5] ✗ [4,2] ✗	[1, 1, 4]	3

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    if n == 2:
        print(2)
        print(1, 1)
    elif n == 3:
        print(3)
        print(1, 1, 1)
    elif n == 4:
        print(4)
        print(1, 1, 1, 1)
    elif n == 5:
        print(2)
        print(1, 4)
    elif n == 6:
        print(3)
        print(1, 1, 4)
    elif n % 2 == 1:
        # n >= 7 奇数：n-1 是偶数且 >= 6，必为合数
        print(2)
        print(1, n - 1)
    else:
        # n >= 8 偶数：n-4 是偶数且 >= 4，必为合数
        print(2)
        print(4, n - 4)

T = int(input())
for _ in range(T):
    solve()

复杂度分析

时间复杂度：O(1) 每组数据，纯分支判断。 空间复杂度：O(1)，仅用常数变量。

第二题：剪绳子

题目描述

有一根绳子，上面从左到右均匀标记了 n 个点（编号 1 到 n，包括两端），相邻点之间距离为 1，绳子被分为 n-1 段。进行 Q 次操作，每次是以下两种之一：

操作 1 x：在点 x 处画一条红线（标记为切点）。
操作 2 k：假设把当前所有红线位置全部剪断，判断是否存在长度 >= k 的绳段。输出 YES 或 NO。

每次操作 2 只是假设性询问，不真的剪断绳子。

样例

输入

输出

YES
YES
NO
YES
NO

思路分析

第一步：理解问题本质

绳子有 n 个点（1 到 n），初始状态下只有两端点 1 和 n 是”边界”。每次操作 1 新增一个切点，操作 2 需要快速回答：当前所有切点把绳子分成的若干段中，最长段是否 >= k？

n 可以非常大（达 10^9），但操作次数 Q 相对较小。不能存储所有 n 个点，只需要维护已标记的切点集合。

第二步：建模为间隔序列

把所有切点（加上两端 1 和 n）从小到大排成一列，相邻两个切点之间的差就是一段绳子的长度。初始只有端点 1 和 n，唯一的段长度为 n - 1。

问题转化为：动态插入切点，随时查询所有段长度中的最大值。

第三步：选择数据结构——两个容器各管一件事

每次插入切点 x，找到它左右最近的已有切点 prev 和 next。原来 [prev, next] 是一整段（长度 next - prev），现在被 x 切成两段。

需要两个容器协同工作：

有序集合（SortedList）：存所有切点，支持 O(log n) 插入和查找邻居。
间隔长度多重集合（SortedList）：存所有段的长度，支持 O(log n) 增删和查询最大值。

插入切点 x 时：从间隔长度表中删除旧长度 (next - prev)，添加两个新长度 (x - prev) 和 (next - x)。查询时取间隔长度表的末尾元素 gaps[-1] 即为最大值。

第四步：实现要点

重复标记同一点时直接跳过（x in cuts 检测去重）
bisect_left 定位插入位置后，左右邻居分别是 cuts[idx-1] 和 cuts[idx]
SortedList 的 remove 删除一个指定值的出现，[-1] 取最大值，均为 O(log n)

以样例为例模拟：

初始：cuts = {1, 8}，gaps = {7}
操作 2 k=7：max(gaps) = 7 >= 7 → YES
操作 1 x=4：旧段 8-1=7 切成 4-1=3 和 8-4=4。gaps = {3, 4}
操作 2 k=4：max = 4 >= 4 → YES
操作 2 k=5：max = 4 < 5 → NO
操作 1 x=6：旧段 8-4=4 切成 6-4=2 和 8-6=2。gaps = {2, 2, 3}
操作 2 k=3：max = 3 >= 3 → YES
操作 2 k=4：max = 3 < 4 → NO

题解代码

import sys
from sortedcontainers import SortedList
input = sys.stdin.readline

def solve():
    n, q = map(int, input().split())
    # 有序集合存所有切点（含两端）
    cuts = SortedList([1, n])
    # 间隔长度多重集合，初始只有一段长 n-1
    gaps = SortedList([n - 1])
    out = []

    for _ in range(q):
        op, val = map(int, input().split())
        if op == 1:
            x = val
            if x in cuts:
                continue
            # 找到 x 在 cuts 中的插入位置，获取左右邻居
            idx = cuts.bisect_left(x)
            prev = cuts[idx - 1]
            nxt = cuts[idx]
            # 从间隔表中删除旧长度，添加两个新长度
            old_gap = nxt - prev
            gaps.remove(old_gap)
            gaps.add(x - prev)
            gaps.add(nxt - x)
            cuts.add(x)
        else:
            k = val
            out.append("YES" if gaps[-1] >= k else "NO")

    print("\n".join(out))

solve()

复杂度分析

时间复杂度：O(Q log Q)，每次插入、查找邻居、维护长度表均为 O(log Q)。 空间复杂度：O(Q)，有序集合和间隔长度表各存至多 Q + 2 个元素。

第三题：不互质元素下标

题目描述

给定由 n 个整数构成的数组 a（下标 1 到 n），有 q 次查询，每次给出 (p, k)。从位置 p 开始（包含 p），向右扫描每个位置，统计满足 gcd(a[i], a[p]) > 1 的元素。当计数达到 k 时，输出该位置下标；若扫描到末尾仍不足 k 个，输出 -1。

样例

输入

输出

3
2
-1

思路分析

第一步：理解”不互质”的含义

gcd(a[i], a[p]) > 1 意味着 a[i] 和 a[p] 至少共享一个质因子。例如 a[p] = 6 的质因子是 {2, 3}，那么所有能被 2 或 3 整除的 a[i] 都与它不互质。

暴力做法是对每个查询从 p 逐个算 gcd，但 n、q 都可能很大，O(nq) 会超时。需要利用质因子结构跳过不相关位置。

第二步：按质因子分组，预处理位置列表

核心转化：不逐一计算 gcd，而是预处理”哪些位置的元素能被某个因子（组合）整除”。

对数组中每个元素 a[i]，先做质因数分解得到质因子集合，然后枚举这些质因子的所有非空子集，计算子集乘积 d，将位置 i 加入 pos[d] 列表。

以 a[i] = 12（质因子 {2, 3}）为例：非空子集的乘积分别为 2、3、6，所以位置 i 被加入 pos[2]、pos[3]、pos[6] 三个列表中。

每个 pos[d] 列表按位置递增排列，天然支持二分查找。

第三步：容斥原理精确计数

查询时需要统计 [p, mid] 范围内与 a[p] 不互质的元素个数。设 a[p] 的质因子为 {p1, p2, …, pm}，直接统计”被 p1 整除的位置数”再加上”被 p2 整除的”会把同时被 p1 和 p2 整除的位置多算一次。

用容斥原理修正：

加上每个单因子对应的计数
减去每对双因子乘积对应的计数
加上每个三因子乘积对应的计数
……

具体来说：枚举质因子的所有非空子集，计算子集乘积 d。子集包含奇数个质因子时加上 pos[d] 在范围内的个数，偶数个时减去。

由于 10^5 以内的数最多有 5 个不同质因子，子集总数不超过 2^5 = 32，容斥枚举非常快。

第四步：二分答案定位第 k 个

现在可以 O(2^m · log n) 地计算 [p, mid] 中有多少个不互质元素。要找第 k 个，用二分答案：

二分位置 mid ∈ [p, n]
若 [p, mid] 中不互质元素个数 >= k，则答案 <= mid，收缩右边界
否则收缩左边界

先用容斥检查 [p, n] 总数，若不足 k 则直接返回 -1。

以样例 a = [2, 3, 4, 6, 5, 9]，查询 (1, 2) 为例：

a[1] = 2，质因子 = {2}
与 a[1] 不互质的位置：pos[2] 中 >= 1 的有 {1, 3, 4}（a[1]=2, a[3]=4, a[4]=6 都能被 2 整除）
共 3 个 >= k=2，二分找第 2 个 → 位置 3，输出 3 ✓

题解代码

import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict
input = sys.stdin.readline

def solve():
    n, q = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    max_val = max(a[1:])

    # 最小质因子筛
    spf = list(range(max_val + 1))
    for i in range(2, int(max_val**0.5) + 1):
        if spf[i] == i:
            for j in range(i * i, max_val + 1, i):
                if spf[j] == j:
                    spf[j] = i

    # 质因数分解
    def get_factors(x):
        factors = []
        while x > 1:
            p = spf[x]
            factors.append(p)
            while x % p == 0:
                x //= p
        return factors

    # 缓存每个位置的质因子
    fac = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        fac[i] = get_factors(a[i])

    # 为每个因子乘积建有序位置列表
    pos = defaultdict(list)
    for i in range(1, n + 1):
        fs = fac[i]
        m = len(fs)
        for mask in range(1, 1 << m):
            prod = 1
            for j in range(m):
                if mask & (1 << j):
                    prod *= fs[j]
            pos[prod].append(i)

    # 容斥计数：[left, right] 中与 base 不互质的元素个数
    def count_range(base_fac, left, right):
        bm = len(base_fac)
        total = 0
        for mask in range(1, 1 << bm):
            prod = 1
            bits = 0
            for j in range(bm):
                if mask & (1 << j):
                    prod *= base_fac[j]
                    bits += 1
            arr = pos.get(prod)
            if arr is None:
                continue
            cnt = bisect_right(arr, right) - bisect_left(arr, left)
            total += cnt if bits % 2 == 1 else -cnt
        return total

    out = []
    for _ in range(q):
        p, k = map(int, input().split())
        bf = fac[p]

        # 先检查 [p, n] 总数是否足够
        if count_range(bf, p, n) < k:
            out.append("-1")
            continue

        # 二分找最小的 mid 使得 [p, mid] 中不互质元素 >= k
        lo, hi = p, n
        while lo < hi:
            mid = (lo + hi) // 2
            if count_range(bf, p, mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        out.append(str(lo))

    print("\n".join(out))

solve()

复杂度分析

时间复杂度：预处理 O(V log log V + n · 2^m)，其中 V 为最大元素值，m 为最大不同质因子个数（V ≤ 10^5 时 m ≤ 5）；每次查询 O(2^m · log n)，总查询 O(q · 2^m · log n)。 空间复杂度：O(V + n · 2^m)，存储最小质因子表和所有因子乘积的位置列表。

小结

第一题是构造题，关键观察是”任何 >= 4 的偶数一定是合数”，利用这一性质对 n >= 7 可统一用长度 2 构造，n ≤ 6 逐一分析即可
第二题有序集合 + 间隔长度多重集合是经典的”动态维护最大间隔”模板，核心是每次插入切点只影响一段，增删操作都是 O(log n)
第三题难度较高，整合了最小质因子筛、容斥原理、二分答案三个知识点，核心转化是将”gcd > 1”翻译为”共享质因子”，再用容斥避免重复计数、二分定位第 k 个

这篇文章有帮助吗？

| GitHub 留言