笔试时间：2023年08月12日 秋招

第一题

题目：小美的排列询问

小美拿到了一个排列。她想知道在这个排列中，x和y是否是相邻的。你能帮帮她吗？

排列是指一个长度为n的数组，其中 1 到n 每个元素恰好出现一次。

输入描述

第一行输入一个正整数n，代表排列的长度。

第二行输入n个正整数ai，代表排列的元素。

第三行输入两个正整数x和y，用空格隔开。

输出描述

如果x和y在排列中相邻，则输出"Yes"。否则输出"No"。

样例输入

示例1:

4

1 4 2 3

2 4

示例2:

5

3 4 5 1 2

3 2

样例输出

示例1:

Yes

示例2:

No

参考题解

C++：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);

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

    int x, y;
    cin >> x >> y;
    bool flag = false;

    for (int i = 0; i < n - 1; i++) {
        if ((nums[i] == x && nums[i + 1] == y) || (nums[i] == y && nums[i + 1] == x)) {
            flag = true;
            break;
        }
    }

    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Java：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        int x = sc.nextInt();
        int y = sc.nextInt();
        boolean flag = false;
        for (int i = 0 ; i < n - 1 ; i++) {
            if (nums[i] == x && nums[i+1] == y) flag = true;
            if (nums[i] == y && nums[i+1] == x) flag = true;
        }
        if (flag) System.out.println("Yes");
        else System.out.println("No");
    }

}

Python：

n = int(input())
nums = list(map(int, input().split()))

x, y = map(int, input().split())
flag = False

for i in range(n - 1):
    if (nums[i] == x and nums[i + 1] == y) or (nums[i] == y and nums[i + 1] == x):
        flag = True
        break

if flag:
    print("Yes")
else:
    print("No")

第二题

题目：小美走公路

有一个环形的公路，上面共有n站，现在给定了顺时针第i站到第i+1站之间的距离（特殊的，也给出了第n站到第1站的距离）。小美想沿着公路第x站走到第y站，她想知道最短的距离是多少？

输入描述

第一行输入一个正整数n，代表站的数量。第二行输入n个正整数ai，前n-1个数代表顺时针沿着公路走，i站到第i+1站之间的距离；最后一个正整数代表顺时针沿着公路走，第n站到第1站的距离。· 第三行输入两个正整数x和y，代表小美的出发地和目的地。

输出描述

一个正整数，代表小美走的最短距离。

样例输入

示例1:

3

1 2 2

2 3

示例2:

3

1 2 2

1 3

样例输出

示例1:2

示例2:2

参考题解

C++：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);

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

    int x, y;
    cin >> x >> y;
    long long tmp2 = 0;
    int f = x;

    while (f != y) {
        tmp2 += a[f];
        f = (f + 1) % (n + 1);
        if (f == 0) {
            f = 1;
        }
    }

    long long tmp1 = 0;
    f = x;

    while (f != y) {
        if (f > 1) {
            tmp1 += a[f - 1];
        } else {
            tmp1 += a[n];
        }
        f = (f - 1);
        if (f == 0) {
            f = n;
        }
    }

    cout << min(tmp1, tmp2) << endl;
    return 0;
}

Java：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt(); //
        }
        int x = sc.nextInt();
        int y = sc.nextInt();
        long tmp2 = 0;
        int f = x;
        while (f != y) {
            tmp2 += a[f];
            f = (f+1)%(n+1);
            if (f == 0) f = 1;
        }
        long tmp1 = 0;
        f = x;
        while (f != y) {
            if (f > 1)tmp1 += a[f-1];
            else tmp1 += a[n];
            f = (f-1);
            if (f == 0) f = n;
        }
        System.out.println(Math.min(tmp1,tmp2));
    }

}

Python：

n = int(input())
a = [0] + list(map(int, input().split()))

x, y = map(int, input().split())
tmp2 = 0
f = x

while f != y:
    tmp2 += a[f]
    f = (f + 1) % (n + 1)
    if f == 0:
        f = 1

tmp1 = 0
f = x

while f != y:
    if f > 1:
        tmp1 += a[f - 1]
    else:
        tmp1 += a[n]
    f = (f - 1)
    if f == 0:
        f = n

print(min(tmp1, tmp2))

第三题

题目：小美的蛋糕切割

小美有一个矩形的蛋糕，共分成了n行m 列，共n*m个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。

小美希望两个人吃的部分的美味度之和尽可能接近，请你输出|s1-s2|的最小值。（其中s1代表小美吃的美味度，s2代表小团吃的美味度）。

请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。

输入描述

第一行输出两个正整数n和m，代表蛋糕区域的行数和列数。接下来的n行，每行输入m个正整数aij，用来表示每个区域的美味度。

输出描述

一个整数，代表|s1-s2|的最小值。

样例输入

2 3

1 1 4

5 1 4

样例输出

0

把蛋糕像这样切开：

1 1 | 4

5 1 | 4

左边蛋糕美味度之和是8

右边蛋糕美味度之和是8

所以答案是0。

参考题解

二维前缀和模拟即可。

C++：

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> matrix;
vector<vector<int>> pre;

int get(int x1, int y1, int x2, int y2) {
    return pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] + pre[x1][y1];
}

int main() {
    int n,