24年秋招-蚂蚁-笔试真题卷(1)

整场笔试难度不高，考点分别为：贪心、模拟、贪心
第三题有点难度，但是由于数据范围原因，直接枚举行和列就可以ac。
大家可以在后台私信ak机加入25届校招交流群哦，也可以添加ak机的微信号：ak_coding加入校招交流群。可以在群里面讨论求职等相关内容，包括但不限于笔试算法的内容。
给大家安利一波ak机制作的大厂笔试基础课，全文共22万字，200+笔试算法题，并且根据考点对题目进行了汇总和梳理，并包含大量的算法讲解、文字、视频题解内容。含金量巨高，秋招将至，使用该题单进行刷题试用版链接：https://t6qoa9k7sz.feishu.cn/docx/PNn9dnWXeo04zYxEe9hc6bP4nIe
在线刷题网站：https://www.sspnote.com/ak
AK机决战大厂笔面试：https://t.zsxq.com/Lhjjb
第一题：最小操作数
在线测评链接：https://www.sspnote.com/oj/3/361
题目描述
薯条哥一开始有一个空串，每次操作可以在这个串的末尾添加任意一个字符。
另外最多有一次操作，可以复制当前字符串本身，然后粘贴到末尾。现在薯条哥想知道，最少经过多少次操作，可以得到目标字符串。
输入描述
第一行一个字符串$s$，表示目标字符串，长度不超过1000
输出描述
输出一个整数，表示最少操作次数。
样例
输入
ababababc
输出
6
题解：贪心+模拟
注意， 本题最多只有一次操作可以复制字符串本身，假设复制的字符串长度为$len$，则字符串$s$一定满足区间$[0,len-1]$构成的子串和区
间$[len,len\times 2-1]$构成的子串相同。
因此，我们可以从$1$开始枚举长度最大的$len$
如果没有一个满足条件的$len$，则答案为字符串$s$的长度$n$
如果有满足条件的$len$，则答案为$n-len+1$
C++
#include<bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int pos = -1;
    for(int i = 0; i < n / 2; i++){  //找到字符串中与开头字符重复的最长子串
        int len = i + 1;
        if(s.substr(0, len) == s.substr(len, len)){
            pos = i;
        }
    }
    int res;
    if(pos == -1){
        res = n;
    }
    else{
        res = n - pos;
    }
    cout << res << endl;
    return 0;
}
Java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int n = s.length();
        int pos = -1;
        for(int i = 0; i < n / 2; i++){  //找到字符串中与开头字符重复的最长子串
            String sub1 = s.substring(0, i + 1);
            String sub2 = s.substring(i + 1, 2 * (i + 1));
            if(sub1.equals(sub2)){
                pos = i;
            }
        }
        int res;
        if(pos == -1){
            res = n;
        }
        else{
            res = n - pos;
        }
        System.out.println(res);
    }
}
Python
s = input()
n = len(s)
pos = -1
for i in range(n // 2):  #找到字符串中与开头字符重复的最长子串
    if s[:i+1] == s[i+1:2*(i+1)]:
        pos = i
if pos == -1:
    res = n
else:
    res = n - pos
print(res)
第二题：操作奇偶数
在线测评链接：https://www.sspnote.com/oj/3/362
题目描述
薯条哥有一个长度为$n$的数组$a$，她希望在$a$上处理一些操作。具体如下：
操作1：将$a$中所有奇数都加上$x$。
操作2：将$a$中所有偶数都加上$x$。
操作3：查询数组$a$中所有数字的和
请你帮她处理所有的操作吧。
输入描述
输入包含$q+2$行。
第一行两个正整数$n,q(1\le n,q\le 2\times 10^5)$，表示数组的长度，和操作的个数。
第二行$n$个正整数$a_i(1\le a_i\le 10^5)$，表示数组的元素值。
接下来$q$行，每行一个操作，格式为：$op \;\;x\;\; y(1\le op,x\le 2,1\le y\le 10^5)$。
如果$op=1$，则表示修改操作，如果$x=1$，则表示将所有值奇数的数字都加上$y$，否则$x=2$表示将所有值为偶数的数字都加上$y$。
如果$op=2$，则表示查询操作，查询数组$a$中所有数字的总和。
输出描述
输出包含若干行。对于每个$op=2$的询问，做出对应的回答。
样例
输入
3 4
1 2 3
1 1 2
2
1 2 1
2
输出
10
11
样例解释
第一次操作之后，数组变成了$[3,2,5]$
第二次查询，数组和为$10$
第三次操作之后，数组变成了$[3,3,5]$
第四次查询，数组和为$11$
题解：模拟
注意本题的数据范围，$q\le 2\times 10^5$，因此，对于每一次的查询和修改，我们都必须要将时间复杂度控制在$O(logn)$。
我们首先可以遍历初始数组$a$，计算出数组$a$的元素总和$total$，奇数数量$odd$和偶数数量$even$
如果$op=2$，则直接输出$total$即可。
如果$op=1$，则需要分情况讨论。
情况1：$x=1$，则表示将所有奇数加上$y$，数组总和增加 $odd \times y$。如果$y$为奇数，则表示所有奇数都变成了偶数，此时$odd=0$，$even=n$。
情况2：$x=2$，则表示将所有偶数加上$y$，数组总和增加 $even \times y$。如果$y$为奇数，则表示所有偶数都变成了奇数，此时$odd=n$，$even=0$。
C++
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n,q;
    cin >> n >> q;
    int odd = 0, even = 0;   //分别统计数组中的奇数和偶数个数
    long long total = 0;  //当前数组总和
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        total += x;
        if(x % 2) odd++;
        else even++;
    }
    for(int i = 1; i <= q; i++){
        int op, x, y;
        cin >> op;
        if(op == 2){
            cout << total << endl;
        }
        else{
            cin >> x >> y;
            if(x == 1){
                total += 1ll * odd * y;  //所有奇数+y
                if(y % 2){  //所有奇数都变成了偶数
                    even = n;
                    odd = 0;
                }
            }
            else{
                total += 1ll * even * y;  //所有偶数+y
                if(y % 2){  //所有偶数都变成了奇数
                    odd = n;
                    even = 0;
                }
            }
        }
    }
    return 0;
}
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int odd = 0, even = 0;   //分别统计数组中的奇数和偶数个数
        long total = 0;  //当前数组总和
        for(int i = 1; i <= n; i++){
            int x = scanner.nextInt();
            total += x;
            if(x % 2 == 1) odd++;
            else even++;
        }
        for(int i = 1; i <= q; i++){
            int op = scanner.nextInt();
            if(op == 2){
                System.out.println(total);
            }
            else{
                int x = scanner.nextInt();
                int y = scanner.nextInt();
                if(x == 1){
                    total += 1L * odd * y;  //所有奇数+y
                    if(y % 2 == 1){  //所有奇数都变成了偶数
                        even = n;
                        odd = 0;
                    }
                }
                else{
                    total += 1L * even * y;  //所有偶数+y
                    if(y % 2 == 1){  //所有偶数都变成了奇数
                        odd = n;
                        even = 0;
                    }
                }
            }
        }
    }
}
Python
n, q = map(int, input().split())
odd = 0
even = 0   #分别统计数组中的奇数和偶数个数
total = 0  #当前数组总和
for x in list(map(int,input().split())):
    total += x
    if x % 2 == 1:
        odd += 1
    else:
        even += 1
for i in range(1, q+1):
    op = list(map(int,input().split()))
    if op[0] == 2:
        print(total)
    else:
        x, y = op[1],op[2]
        if x == 1:
            total += odd * y  #所有奇数+y
            if y % 2 == 1:  #所有奇数都变成了偶数
                even = n
                odd = 0
        else:
            total += even * y  #所有偶数+y
            if y % 2 == 1:  #所有偶数都变成了奇数
                odd = n
                even = 0
第三题 矩阵最大和
在线测评链接：https://www.sspnote.com/oj/3/363
题目描述
薯条哥有一个大小为$n\times m$的矩阵，矩阵中每个元素都是非负整数。薯条哥每次操作可以选择矩阵的一行或者一列，然后获得这一行或者这一列中所有元素的和，随后，这一行或者这一列中的元素将会被清零。
薯条哥想知道，她最多进行三次操作，能获得的最大和是多少。
输入描述
第一行两个整数$n,m(1\le n,m\le 500)$，表示矩阵的大小。
接下来$n$行，每行$m$个整数$a_{ij}(1\le a_{ij}\le 10^9)$，表示矩阵中的元素。
输出描述
输出一个整数，表示薯条哥最多进行三次操作，能获得的最大和。
样例
输入
2 3
1 2 5
3 4 6
输出
21
样例解释
进行两次操作，选择第一行和第二行，得到的和为 $1+2+5+3+4+6=21$。
题解：贪心+分类讨论
本题还是有一定难度的，不过由于实际的$a_{ij}$是正数，因此直接枚举行和列就可以ac。这里给大家提供一个更加通用性的思路。适合
$-10^9\le a_{ij}\le 10^9$的范围。
首先，我们可以分别预处理每一行和每一列的和，分别存到$row,col$数组中。
然后，我们可以选择$row$和$col$数组中最大的3个值来求和，然后取二者的最大值。
这是只选择行或者列的情况，还有两种情况：选择两行一列或者一行两列
对于一行两列的情况，我们可以枚举选择第$i$行。
但是要注意，如果这个时候选择第$j$列，那么会有一个重复的数字$a_{ij}
因此，我们需要对$col$数组做处理，也就是$col[j]=col[j]-a[i][j]$，然后从处理后的数组中取最大的2个值，然后将其与$row[i]$相加，并对结果取$max$
同理，对于两行一列的情况，我们可以枚举选择第$j$列。然后按照上述相同的方式枚举即可。
整体的时间复杂度为$O(n\times m+n\times mlogm+m\times nlogn)$
C++
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N],n,m;
long long res=0;

long long get(vector<long long> a,int k){   //计算数组a topk的元素和
    sort(a.begin(),a.end(),greater<long long>{});  //降序排列
    long long res=0;
    for(int i=0;i<k;i++) res+=a[i];
    return res;
}

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>g[i][j];
        }
    }
    vector<long long>row{0},col{0};  //下标从1开始
    for(int i=1;i<=max(n,3);i++) {  //计算每一行的和(不足3行填充0)
        long long total=0;
        for(int j=1;j<=m;j++) {
            total+=g[i][j];
        }
        row.push_back(total);
    }
    for(int i=1;i<=max(m,3);i++) {  //计算每一列的和(不足3列填充0)
        long long total=0;
        for(int j=1;j<=n;j++) {
            total+=g[j][i];
        }
        col.push_back(total);
    }
    res=max(get(row,3),get(col,3));  //取行和列的最大值
    
    for(int i=1;i<=max(n,3);i++){  //固定一行,取最大的其他两列
        long long cur=row[i];
        vector<long long>tmp;
        for(int j=1;j<col.size();j++){
            long long total=col[j]-g[i][j];
            tmp.push_back(total);
        }
        res=max(res,cur+get(tmp,2));
    }
    for(int i=1;i<=max(m,3);i++){  //固定一列,取最大的其他两行
        long long cur=col[i];
        vector<long long>tmp;
        for(int j=1;j<row.size();j++){
            long long total=row[j]-g[j][i];
            tmp.push_back(total);
        }
        res=max(res,cur+get(tmp,2));
    }
    cout<<res<<endl;
    return 0;
}
Java
import java.util.*;

public class Main {
    static final int N = 510;
    static int[][] g = new int[N][N];
    static int n, m;
    static long res = 0;

    static long get(List<Long> a, int k) {   //计算数组a topk的元素和
        Collections.sort(a, Collections.reverseOrder());  //降序排列
        long res = 0;
        for(int i = 0; i < k; i++) res += a.get(i);
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                g[i][j] = scanner.nextInt();
            }
        }
        List<Long> row = new ArrayList<>();
        row.add(0L);  //下标从1开始
        for(int i = 1; i <= Math.max(n, 3); i++) {  //计算每一行的和(不足3行填充0)
            long total = 0;
            for(int j = 1; j <= m; j++) {
                total += g[i][j];
            }
            row.add(total);
        }
        List<Long> col = new ArrayList<>();
        col.add(0L);  //下标从1开始
        for(int i = 1; i <= Math.max(m, 3); i++) {  //计算每一列的和(不足3列填充0)
            long total = 0;
            for(int j = 1; j <= n; j++) {
                total += g[j][i];
            }
            col.add(total);
        }
        res = Math.max(get(row, 3), get(col, 3));  //取行和列的最大值

        for(int i = 1; i <= Math.max(n, 3); i++){  //固定一行,取最大的其他两列
            long cur = row.get(i);
            List<Long> tmp = new ArrayList<>();
            for(int j = 1; j < col.size(); j++){
                long total = col.get(j) - g[i][j];
                tmp.add(total);
            }
            res = Math.max(res, cur + get(tmp, 2));
        }
        for(int i = 1; i <= Math.max(m, 3); i++){  //固定一列,取最大的其他两行
            long cur = col.get(i);
            List<Long> tmp = new ArrayList<>();
            for(int j = 1; j < row.size(); j++){
                long total = row.get(j) - g[j][i];
                tmp.add(total);
            }
            res = Math.max(res, cur + get(tmp, 2));
        }
        System.out.println(res);
    }
}
Python
import sys

N = 510
g = [[0]*N for _ in range(N)]
res = 0

# 定义函数get，计算数组a的前k个元素之和
def get(a, k):
    a.sort(reverse=True)  # 降序排列
    return sum(a[:k])  # 返回前k个元素之和


n, m = map(int, sys.stdin.readline().split())
for i in range(1, n+1):
    g[i][1:m+1] = map(int, sys.stdin.readline().split())
row = [0]  # 初始化行数组，下标从1开始
for i in range(1, max(n, 3)+1):  # 计算每一行的和(不足3行填充0)
    total = sum(g[i][1:m+1])
    row.append(total)
col = [0]  # 初始化列数组，下标从1开始
for i in range(1, max(m, 3)+1):  # 计算每一列的和(不足3列填充0)
    total = sum(g[j][i] for j in range(1, n+1))
    col.append(total)
res = max(get(row, 3), get(col, 3))  # 取行和列的最大值
for i in range(1, max(n, 3)+1):  # 固定一行,取最大的其他两列
    cur = row[i]
    tmp = [col[j] - g[i][j] for j in range(1, len(col))]
    res = max(res, cur + get(tmp, 2))
for i in range(1, max(m, 3)+1):  # 固定一列,取最大的其他两行
    cur = col[i]
    tmp = [row[j] - g[j][i] for j in range(1, len(row))]
    res = max(res, cur + get(tmp, 2))
print(res)