整场笔试难度不高，考点分别为：贪心、模拟、贪心

第三题有点难度，但是由于数据范围原因，直接枚举行和列就可以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$

#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;
}

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

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++、Java）可以前往AK机的网站学习哦~

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++、Python）可以前往AK机的网站学习哦~

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