✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

🤖 内容包含AI辅助生成，题解和代码均经过多轮验证，有问题欢迎评论

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

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

蚂蚁-2026.04.16-研发岗

题目总览

这套蚂蚁研发岗的节奏比较清楚。第一题是分类构造，第二题适合把动态过程倒过来看，第三题则是数论查询题，先把“非互质”拆成质因子命中，后面的结构就会清楚很多。

1. 小兰的合规拆分单

问题描述

本题是蚂蚁 2025.08.21-算法岗 第 1 题的原题。

小兰 要把一笔总量为 的资源拆成若干份登记到系统里。

系统只接受两类单份大小：

• 恰好等于 ；
• 合数，也就是大于 且不是质数的正整数。

现在需要构造一个长度至少为 的数组 ，满足：

• 数组中的每个元素都符合上面的登记规则；
• 数组所有元素之和恰好等于 。

如果存在多种可行方案，先要求数组长度最短；如果最短方案不唯一，输出任意一种即可。

输入格式

第一行输入一个整数 ，表示测试数据组数。

接下来 行，每行输入一个正整数 。

输出格式

对于每组数据：

• 第一行输出一个整数 ，表示构造出的数组长度；
• 第二行输出 个整数，表示这个数组中的元素。

如果最短方案不唯一，输出任意一种都可以。

样例输入

3
8
10
2

样例输出

2
4 4
2
4 6
2
1 1

数据范围

样例说明

• 样例 1：当 时，取 即可；当 时， 也是长度为 的合法方案；当 时，只能取 。

题解

先问自己，什么时候能做到长度为

如果答案长度是 ，那就相当于要把 拆成 ，并且 都必须是 或合数。

最自然的两种尝试是：

• 用 去凑，也就是看 能不能合法；
• 用一个固定的合数去凑，也就是看剩下那部分能不能合法。

奇数情况最简单

当 是奇数并且 时， 是一个不小于 的偶数。

任何不小于 的偶数都是合数，所以这时直接输出：

长度就是 。

偶数情况只要再分一类

当 是偶数时：

• 如果 ，那么 是一个不小于 的偶数，同样一定是合数；
• 所以这时可以直接输出 ，长度还是 。

这样一来，除了很小的几个数，其余情况都能两项解决。

小数值单独判断

剩下只需要把最小的几个值手工列出来：

• 时，只能是 ，长度为 ；
• 时，长度为 不可能，因为 里的 不是合法值，所以只能是 ；
• 时，长度为 不可能，长度为 也不可能，最短只能是 ；
• 时，长度为 的拆法只有 、，都不合法，所以最短是 。

算法流程

每组数据直接按下面的顺序判断：

1. 如果 ，输出 1 1。
2. 如果 ，输出 1 1 1。
3. 如果 ，输出 1 1 1 1。
4. 如果 ，输出 1 1 4。
5. 如果 是奇数，输出 1 和 n-1。
6. 否则输出 4 和 n-4。

复杂度分析

每组数据都只做常数次判断。

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

参考代码（Python）

import sys

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


def solve() -> None:
    # Read input in ACM mode and build the answer directly.
    t = int(input())
    out = []

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

        # 下面四个值是唯一需要单独特判的小范围答案。
        if n == 2:
            out.append("2")
            out.append("1 1")
            continue
        if n == 3:
            out.append("3")
            out.append("1 1 1")
            continue
        if n == 4:
            out.append("4")
            out.append("1 1 1 1")
            continue
        if n == 6:
            out.append("3")
            out.append("1 1 4")
            continue

        # 奇数且至少为 5 时，n-1 是不小于 4 的偶数，一定是合数。
        if n & 1:
            out.append("2")
            out.append(f"1 {n - 1}")
        else:
            # 偶数且不是 2、4、6 时，至少为 8，此时 n-4 也是合数。
            out.append("2")
            out.append(f"4 {n - 4}")

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


if __name__ == "__main__":
    # Standard ACM entry.
    solve()

2. 园子的警戒绳

问题描述

本题是蚂蚁 2025.05.08-研发岗 第 2 题的原题。

园子在一根长度为 的绳子上等距标了 个点，编号为 到 ，相邻两个点之间的距离都是 。

她会进行 次操作，每次操作属于下面两种之一：

• 1 x：在点 处画一条红线。
• 2 k：假设把当前所有画过红线的位置全部剪开，询问是否还存在长度至少为 的绳子段。

注意：

• 剪断只是假设，不会真的改变后续操作；
• 每次询问二都基于“当前已经画过的所有红线”独立计算。

输入格式

第一行输入两个整数 ，分别表示点的数量和操作次数。

接下来 行，每行输入一组操作：

• 如果操作类型为 1，则这一行是 1 x；
• 如果操作类型为 2，则这一行是 2 k。

输出格式

对于每个类型为 2 的询问：

• 如果存在长度至少为 的绳子段，输出 YES；
• 否则输出 NO。

样例输入

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

样例输出

YES
YES
NO
YES
NO

数据范围

样例说明

• 样例 1：初始时整根绳子的长度是 ，所以第一问是 YES。画上红线 以后，绳子被分成长度 和 的两段，所以对 回答 YES，对 回答 NO。再画上红线 后，三段长度分别是 ，于是最后两问分别是 YES 和 NO。

题解

正着做需要维护“当前最大段”

如果按照题目原顺序处理，操作只有“加红线”，没有“删红线”。

一条红线会把某一段绳子拆成两段，所以正着做通常会想到：

• 用有序集合维护所有红线位置；
• 用另一个结构维护所有段长的最大值。

这个思路本身没有问题，不过这里还有一个更适合三语言统一实现的做法。

反过来看，问题会简单很多

把所有操作倒过来考虑：

• 原来的“加一条红线”，在倒序里就变成“删掉一条红线”；
• 原来的询问，依然只是问当前最大段长是否至少为 。

删掉一条红线时会发生什么？

• 这条红线左右两边原本有两段绳子；
• 去掉以后，这两段会合并成一整段；
• 因此当前最大段长只会变大，不会变小。

这就带来了一个很关键的性质：

• 在倒序处理中，只需要维护一个变量 mx 表示当前最大段长；
• 每次删红线时，用合并后的新段长去更新 mx 即可；
• 不需要再维护“段长 multiset”这种会删除元素的结构。

怎么快速知道一条红线左右是谁

先把所有出现过的红线位置收集出来，再加上两端点 1 和 n，排序后记为数组 pts。

然后把这些点看成一条双向链表：

• left[i] 表示当前还保留的、pts[i] 左边最近的点；
• right[i] 表示当前还保留的、pts[i] 右边最近的点。

倒序删除位置 x 时：

1. 找到它在 pts 中的下标 id；
2. 设左右相邻点下标分别是 L、R；
3. 删除 x 后，新段长就是 pts[R] - pts[L]；
4. 用这个值更新 mx；
5. 再把链表改成 L <-> R。

为什么这样是对的

倒序某一时刻保留的红线集合，正好对应原顺序同一时刻已经画出的红线集合。

所以：

• 倒序里的当前绳段划分，和原题当前询问时的绳段划分完全一致；
• mx 就是这一时刻真正的最大段长；
• 对于询问 2 k，只需要判断 mx \ge k 即可。

还要注意重复画线

如果某个位置在输入里被多次执行了 1 x，倒序时不能每次都真的删掉它。

做法很简单：

• 先统计每个位置总共被画了多少次；
• 倒序遇到一次 就把计数减