四季读书网
四季读书网

【笔试突围】4月2日蚂蚁研发岗真题解析+在线刷题

四季读书网 3 0
【笔试突围】4月2日蚂蚁研发岗真题解析+在线刷题
【笔试突围】4月2日蚂蚁研发岗真题解析+在线刷题 第1张

🔗刷题网址: bishipass.com

27届实习提前批秋招汇总，持续更新，建议收藏，欢迎分享https://docs.qq.com/smartsheet/DRHVEc05MbE5CYUZa?tab=sc_JGxFAj

蚂蚁-2026.04.02-研发岗

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

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

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

1. LYA 的序列互检

问题描述

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

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

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

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

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

输入格式

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

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

输出格式

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

  • >
    如果序列通过检查，输出 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()


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

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

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

returnTrue


defsolve():
    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>
usingnamespacestd;

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

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

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

returntrue;
}

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

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

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

cout << (checkSeq(a, k) ? "Yes" : "No") << '\n';
    }
return0;
}
  • >
    Java
import java.io.*;
import java.util.*;

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

privatestaticbooleancheck(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]) {
returnfalse;
            }
        }

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

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

returntrue;
    }

publicstaticvoidmain(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 = newlong[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);
    }

privatestaticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

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

longnextLong()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;
        }

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

2. K小姐的切分按位值

问题描述

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

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

  • >
    左段 ；
  • >
    右段 。

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

其中  表示按位与运算。

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

输入格式

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

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

输出格式

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

样例输入

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


defsolve():
    t = int(input())
    out = []

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

# rt[b] 记录当前分割点右侧，第 b 位为 1 的元素个数。
        rt = [0] * BITS
for x in arr:
for b in range(BITS):
                rt[b] += (x >> b) & 1

# lf[b] 记录当前分割点左侧，第 b 位为 1 的元素个数。
        lf = [0] * BITS
        ans = 0

for i in range(n - 1):
            x = arr[i]
# 把 a[i] 从右边集合挪到左边集合。
for b in range(BITS):
if (x >> b) & 1:
                    lf[b] += 1
                    rt[b] -= 1

            cur = 0
# 这一位能形成 lf[b] * rt[b] 对有效跨界配对。
for b in range(BITS):
                cur += (1 << b) * lf[b] * rt[b]

if cur > ans:
                ans = cur

        out.append(str(ans))

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


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

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

constint BITS = 31;
int t;
cin >> t;
while (t--) {
int n;
cin >> n;

vector<int> a(n);
vector<longlong> left(BITS, 0), right(BITS, 0);
for (int i = 0; i < n; ++i) {
cin >> a[i];
// 先把全部元素都放在右侧计数里。
for (int b = 0; b < BITS; ++b) {
                right[b] += (a[i] >> b) & 1;
            }
        }

longlong ans = 0;
for (int i = 0; i + 1 < n; ++i) {
// 当前元素跨过分割点，从右边移到左边。
for (int b = 0; b < BITS; ++b) {
if ((a[i] >> b) & 1) {
                    ++left[b];
                    --right[b];
                }
            }

longlong cur = 0;
// 第 b 位的贡献 = 2^b * 左侧 1 的个数 * 右侧 1 的个数。
for (int b = 0; b < BITS; ++b) {
                cur += (1LL << b) * left[b] * right[b];
            }
            ans = max(ans, cur);
        }

cout << ans << '\n';
    }
return0;
}
  • >
    Java
import java.io.*;

publicclassMain{
publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();
finalint BITS = 31;
int t = fs.nextInt();

while (t-- > 0) {
int n = fs.nextInt();
int[] arr = newint[n];
long[] left = newlong[BITS];
long[] right = newlong[BITS];

for (int i = 0; i < n; i++) {
                arr[i] = fs.nextInt();
// 初始时所有元素都还在分割点右边。
for (int b = 0; b < BITS; b++) {
                    right[b] += (arr[i] >> b) & 1;
                }
            }

long ans = 0;
for (int i = 0; i + 1 < n; i++) {
// arr[i] 被划进左半段后，更新左右两侧的位计数。
for (int b = 0; b < BITS; b++) {
if (((arr[i] >> b) & 1) == 1) {
                        left[b]++;
                        right[b]--;
                    }
                }

long cur = 0;
// 这一位左边和右边各取一个 1，就能贡献一个 2^b。
for (int b = 0; b < BITS; b++) {
                    cur += (1L << b) * left[b] * right[b];
                }
if (cur > ans) {
                    ans = cur;
                }
            }

            sb.append(ans).append('\n');
        }

        System.out.print(sb);
    }

privatestaticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

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

longnextLong()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;
        }

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

3. 卢小姐的平方串补边

问题描述

卢小姐在调一个字符串拼接模板。

给定若干个仅由小写字母组成的非空字符串 。你只能在字符串的头部和尾部添加字符，不能在中间插入字符。设补完后的新串为 。

如果存在一个字符串 ，使得：

那么称  是一个平方串。

请你计算，对每个给定的字符串，最少需要添加多少个字符，才能把它变成一个平方串。允许一个字符都不添加。

输入格式

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

  • >
    第一行输入一个整数 ，表示数据组数。
  • >
    接下来  行，每行输入一个非空字符串 。

输出格式

输出  行，每行一个整数，表示最少需要添加的字符数量。

样例输入

5
abab
abc
aaaaa
abe
abca

样例输出

0
3
1
3
2

数据范围

  • >
  • >
  • >
    所有测试数据中，字符串长度之和不超过 
  • >
    字符串仅由小写字母组成
样例
解释说明
样例 1
abab
 本身就是平方串。abc 需要补成 abcabc。aaaaa 只需再补一个 a。abe 可以补成 abeabe。abca 可以补成 abcabc。

题解

如果最终串是 uu，那么最省字符的情况一定是让原串尽量跨在两个 u 的交界处。

这样，原串的前面一段会落在前一个 u 的后缀里，后面一段会落在后一个 u 的前缀里。

要让这件事成立，原串必须拿出一段“前后相同”的内容来重叠。也就是说，需要找一个长度为  的 border：

  • >
    长度为  的前缀；
  • >
    同时也是长度为  的后缀。

并且这个重叠不能超过一半，所以还要满足：

这里的 border 是字符串题里很常见的术语，意思是：

  • >
    它是整个字符串的前缀；
  • >
    它也是整个字符串的后缀；
  • >
    但不能等于整个字符串本身。

例如 abca 的 border 只有空串。
abcabc 的 border 有 abc。
aaaaa 的 border 有 a、aa、aaa、aaaa，但这题真正能拿来用的只能是长度不超过一半的那些。

#为什么只看 border

设最终平方串是：

原串  被放进  中间以后，假设它跨过了两个半串的分界线。

那么：

  • >
     左边那一段，必须和右半边开头对应的字符完全一样；
  • >
     右边那一段，必须和左半边结尾对应的字符完全一样。

换句话说，原串自己必须提供一段“前后能对上”的重叠，这段重叠就是一个 border。

如果一段前后对不齐，那就不可能靠只在首尾补字符把它塞进 uu 的结构里。

#为什么答案是 

如果已经找到这样的最长 border，设它的长度为 。

那么可以把最终半串的长度取成：

这样整个平方串长度就是：

原串长度是 ，所以需要补的字符总数就是：

显然， 越大，需要补的字符越少。所以只要找到满足条件的最大 border 即可。

可以直接看一个例子：

  • >
    s = abca
  • >
    它的最长可用 border 是 a，长度 
  • >
    于是答案是 

对应的一种构造就是把它补成 abcabc。
此时两个半串都是 abc，而原串 abca 正好跨在中间。

所以前缀函数给出的 ，可以理解成“原串内部有多少字符已经能在左右两边对齐”，这部分一共能省掉  个补字符。

#怎么在线性时间找到它

KMP 的前缀函数正好可以求每个位置的最长 border。

先算出整串的前缀函数，拿到整串的最长 border 长度 pi[n-1]。这个值表示：

  • >
    整个字符串的最长 border 有多长。

如果它已经超过了一半，就不能直接拿来用，因为两个半串的重叠会发生交叉。
这时继续沿着前缀函数往前跳：

  • >
    pi[k-1] 表示当前这个 border 自己的最长 border。

所以不断令：

k = pi[k-1]

就等价于“按长度从大到小，枚举所有可能的 border”。
找到第一个满足  的值，就已经是可用的最大 border 了。

最后把它代入公式：

就得到答案。

#复杂度分析

对每个字符串，前缀函数的计算复杂度是 。

因此总复杂度是所有字符串长度之和的线性级别，也就是 ，空间复杂度是 。

参考代码

  • >
    Python
import sys

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


defneed(s):
    n = len(s)
# pi[i] 表示 s[0..i] 这个前缀的最长 border 长度。
    pi = [0] * n

for i in range(1, n):
        j = pi[i - 1]
# 当前字符接不上时，沿着 border 链继续回退。
while j and s[i] != s[j]:
            j = pi[j - 1]
# 接上以后，最长 border 长度加一。
if s[i] == s[j]:
            j += 1
        pi[i] = j

# 先从整串的最长 border 开始尝试。
    k = pi[-1]
# 超过一半的 border 不能直接用于跨中线重叠，需要继续回跳。
while k > n // 2:
        k = pi[k - 1]

# 能省掉的重叠部分是 2*k，所以补边数是 n - 2*k。
return n - 2 * k


defsolve():
    t = int(input())
    out = []

for _ in range(t):
        s = input()
        out.append(str(need(s)))

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


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

intneed(conststring& s){
int n = (int)s.size();
// pi[i] 记录前缀 s[0..i] 的最长 border 长度。
vector<int> pi(n, 0);

for (int i = 1; i < n; ++i) {
int j = pi[i - 1];
// 失配时沿 border 链回退。
while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
// 匹配成功就把当前 border 延长一位。
if (s[i] == s[j]) {
            ++j;
        }
        pi[i] = j;
    }

// 从整串最长 border 出发，寻找不超过一半的最大可用值。
int k = pi[n - 1];
while (k > n / 2) {
        k = pi[k - 1];
    }
// 公式：答案 = n - 2 * k。
return n - 2 * k;
}

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

int t;
cin >> t;
while (t--) {
string s;
cin >> s;
cout << need(s) << '\n';
    }
return0;
}
  • >
    Java
import java.io.*;

publicclassMain{
privatestaticintneed(String s){
int n = s.length();
// pi[i] 是前缀 s[0..i] 的最长 border 长度。
int[] pi = newint[n];

for (int i = 1; i < n; i++) {
int j = pi[i - 1];
// 如果当前位置接不上，就顺着前缀函数继续回退。
while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = pi[j - 1];
            }
// 接上以后，把 border 长度加一。
if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }

// 先取整串的最长 border，再回跳到第一个不超过一半的值。
int k = pi[n - 1];
while (k > n / 2) {
            k = pi[k - 1];
        }
// 能重叠掉的部分共有 2*k 个字符。
return n - 2 * k;
    }

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

while (t-- > 0) {
            String s = fs.next();
            sb.append(need(s)).append('\n');
        }

        System.out.print(sb);
    }

privatestaticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

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

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

            StringBuilder sb = new StringBuilder();
while (c > ' ') {
                sb.append((char) c);
                c = read();
            }
return sb.toString();
        }

intnextInt()throws IOException {
return Integer.parseInt(next());
        }
    }
}

✨ 写在最后：

网站最近上线了八股和选额的功能啦。

最近卡片刷题已经全员开放了，八股和选择题都能直接刷。 我自己还挺喜欢这种刷法的，先看题、自己想，再翻面看答案，会比一直往下看题库更有“在准备面试”的感觉一点。 如果你最近也在刷八股，准备面试、可以来bishipass试试看哦。

【笔试突围】4月2日蚂蚁研发岗真题解析+在线刷题 第2张
【笔试突围】4月2日蚂蚁研发岗真题解析+在线刷题 第3张
【笔试突围】4月2日蚂蚁研发岗真题解析+在线刷题 第4张
【笔试突围】4月2日蚂蚁研发岗真题解析+在线刷题 第5张

文章来源： 四季读书网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至23467321@qq.com举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！

上一个【2021年重庆市中考思想品德B卷试卷及答案中考真题电子版word版PDF版免费下载

下一个2026北京中考提前招生录取变化:贯通项目调整至统招

相关文章

抱歉，评论功能暂时关闭!