Zero2Leetcode

大厂真题 / 蚂蚁

蚂蚁 4.2 笔试真题 - 研发岗

本场考试概述

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

考点分析：

  1. 第一题：GCD验证（难度中等）
  2. 第二题：按位分解+前缀和（难度中等）
  3. 第三题：字符串哈希（难度中等偏难）

建议策略：

  1. 第一题纯验证题，优先拿满分
  2. 第二题需要想到按位分解，找到规律后实现不难
  3. 第三题字符串哈希是模板知识点，提前背好模板可快速AC

第一题：也许互质序列

题目描述

给定一个长度为 n 的整数数列 a 和正整数 k，判断它是否同时满足：

  1. 对所有 i，gcd(a[i], a[i+1]) = 1（相邻两项互质）；
  2. 对所有 i，gcd(a[i], a[i+k]) > 1（下标相差 k 的两项不互质）；
  3. 对所有 i ≠ j，a[i] ≠ a[j]（所有数字两两不同）。

样例

输入

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

输出

Yes
Yes
No

题解：GCD验证

本题是纯验证问题，依次检查三个条件，任一不满足立即返回 No。条件一遍历相邻对检查 gcd == 1，条件二遍历距离为 k 的对检查 gcd > 1，条件三用集合判重。

时间复杂度：O(n log V)，其中 V 为最大元素值。 空间复杂度：O(n)。

import sys
from math import gcd
input = sys.stdin.readline

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(n - 1):
        if gcd(a[i], a[i + 1]) != 1:
            return "No"
    for i in range(n - k):
        if gcd(a[i], a[i + k]) <= 1:
            return "No"
    if len(set(a)) != n:
        return "No"
    return "Yes"

T = int(input())
out = []
for _ in range(T):
    out.append(solve())
print("\n".join(out))

第二题：按位与权值和

题目描述

给定一个长度为 n 的整数数组 a。选择一个分割点 p（1 ≤ p < n），将数组切分为前缀 B = a[1..p] 与后缀 C = a[p+1..n]。定义权值和 S(p) = Σ(B[i] & C[j])，对所有 i ∈ B, j ∈ C。选择 p 使得 S(p) 最大。

样例

输入

1
4
5 2 7 1

输出

8

题解：按位分解+前缀和

暴力枚举后双重循环求和为 O(n^2)，n 可达 10^5 会超时。核心观察：b & c 逐位判断，各位之间互不影响，因此 S(p) 可拆成 27 个位分别计算再相加。

对第 b 位，一对 (i, j) 仅当两者第 b 位都为 1 时贡献 2^b。设 B 中有 cnt_B 个数第 b 位为 1，C 中有 cnt_C 个，第 b 位总贡献为 2^b × cnt_B × cnt_C。维护前缀计数从左到右枚举分割点即可。

时间复杂度：O(27n)。 空间复杂度：O(27)。

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    total = [0] * 27
    for x in a:
        for b in range(27):
            if (x >> b) & 1:
                total[b] += 1

    prefix = [0] * 27
    best = 0
    for p in range(1, n):
        for b in range(27):
            if (a[p - 1] >> b) & 1:
                prefix[b] += 1
        val = 0
        for b in range(27):
            right = total[b] - prefix[b]
            val += (1 << b) * prefix[b] * right
        best = max(best, val)
    print(best)

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

第三题：平方串

题目描述

给定若干字符串 s，可以在字符串的头部与尾部添加任意字符，使得新串能被分成两个相同的子串（平方串，形如 t+t）。求每个字符串最少需要添加多少字符。

样例

输入

5
abab
abc
aaaea
abe
abca

输出

0
3
3
3
2

题解：字符串哈希

设 L = len(s)，目标串长度为 2k（2k ≥ L），需添加 2k - L 个字符。

判定 k 合法：目标串长 2k，两半相同意味着 s 中被两半同时覆盖的部分必须对应字符相等，等价于 s[0..L-k-1] == s[k..L-1]。两端添加的字符可自由赋值。

从 k = ⌈L/2⌉ 开始递增枚举，用字符串哈希 O(1) 比较前缀与后缀，第一个匹配的 k 给出最小添加数 2k - L。若直到 k = L-1 都不满足，取 k = L 必然合法。

时间复杂度：O(L)。 空间复杂度：O(L)。

import sys
input = sys.stdin.readline

MOD = 1_000_000_007
BASE = 131

def solve(s):
    L = len(s)
    h = [0] * (L + 1)
    pw = [0] * (L + 1)
    pw[0] = 1
    for i in range(L):
        h[i + 1] = (h[i] * BASE + ord(s[i])) % MOD
        pw[i + 1] = pw[i] * BASE % MOD

    def get_hash(l, r):
        return (h[r + 1] - h[l] * pw[r - l + 1]) % MOD

    for k in range((L + 1) // 2, L):
        left_hash = get_hash(0, L - k - 1)
        right_hash = get_hash(k, L - 1)
        if left_hash == right_hash:
            return 2 * k - L
    return L

T = int(input())
out = []
for _ in range(T):
    s = input().strip()
    out.append(str(solve(s)))
print("\n".join(out))

小结

  • 第一题 GCD 验证是纯验证题，依次检查三个条件即可，O(n log V) 线性通过
  • 第二题按位分解 + 前缀和，将按位与的求和拆成各位独立计算，是位运算题的经典套路
  • 第三题字符串哈希是模板知识点，关键在于推导出前缀与后缀匹配条件，再用哈希 O(1) 比较