笔试时间：2025年9月11日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：数组操作

题目：小红认为一个长度为n的数组是"好的"，当且仅当对于任意的下标i（1≤i≤n）均满足：a[i] = i + d 或 a[i] = i - d，其中d相等。

小红每次可以对一个数执行以下操作之一：

• 加1
• 减1

请你求出：把给定数组变成"好数组"的最少操作次数。

输入描述

第一行一个整数n，表示数组长度。第二行包含n个整数，第i个数为a[i]。

输出描述

输出一个整数，表示最少操作次数。

样例输入

3

3 2 1

样例输出

2

参考题解

解题思路：

1. 枚举可能的差值d（从0到n）
2. 对每个位置i，计算将a[i]改成i+d或i-d所需的最小操作次数
3. 累加每个位置的操作次数得到该d值的总操作次数
4. 取所有可能d值中的最小操作次数

C++：

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        int ans = Integer.MAX_VALUE;
        for (int d = 0; d <= n; d++) {
            int total = 0;
            for (int i = 1; i <= n; i++) {
                int c1 = Math.abs(a[i] - (i + d));
                int c2 = Math.abs(a[i] - (i - d));
                total += Math.min(c1, c2);
            }
            ans = Math.min(ans, total);
        }
        
        System.out.println(ans);
    }
}

Java：

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        int ans = Integer.MAX_VALUE;
        for (int d = 0; d <= n; d++) {
            int total = 0;
            for (int i = 1; i <= n; i++) {
                int c1 = Math.abs(a[i] - (i + d));
                int c2 = Math.abs(a[i] - (i - d));
                total += Math.min(c1, c2);
            }
            ans = Math.min(ans, total);
        }
        
        System.out.println(ans);
    }
}

Python：

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

ans = float('inf')
for d in range(n + 1):
    total = 0
    for i in range(1, n + 1):
        c1 = abs(a[i] - (i + d))
        c2 = abs(a[i] - (i - d))
        total += min(c1, c2)
    ans = min(ans, total)

print(ans)

第二题：数组重排

题目：小红给定一个数字x，现在她准备把其数位上的数字重新排列，满足重排后的数字没有前导零并且和原数字不同。

现在请你帮助小红计算有多少个重排后的数字y，使得gcd(x,y) != 1。

其中gcd，即最大公约数，指两个整数共有约数中最大的一个。

输入描述

一个整数x (1 ≤ x ≤ 10^9)，表示给定的数字。

输出描述

一个整数，表示满足条件的重排数字的数量。

样例输入

213

样例输出

5

样例说明：213重排后可以是[123, 132, 231, 312, 321]，所有5个都满足与213的gcd不为1

参考题解

解题思路：

1. 生成数字的所有排列（使用next_permutation）
2. 排除前导零和与原数字相同的排列
3. 对每个合法排列，判断与原数字的gcd是否不等于1
4. 统计满足条件的排列数量

C++：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

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

int main() {
    long long x;
    cin >> x;
    string s = to_string(x);
    sort(s.begin(), s.end());
    
    long long cnt = 0;
    do {
        if (s[0] == '0') continue;  // 不能有前导0
        long long y = stoll(s);
        if (y == x) continue;  // 不能等于原数字
        if (gcd(x, y) != 1) cnt++;
    } while (next_permutation(s.begin(), s.end()));
    
    cout << cnt << endl;
    return 0;
}

Java：

import java.util.*;
import java.io.*;

public class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
    
    static long countPermutations(String s, long x) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        long cnt = 0;
        
        do {
            if (arr[0] == '0') continue;
            long y = Long.parseLong(new String(arr));
            if (y == x) continue;
            if (gcd(x, y) != 1) cnt++;
        } while (nextPermutation(arr));
        
        return cnt;
    }
    
    static boolean nextPermutation(char[] arr) {
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i < 0) return false;
        
        int j = arr.length - 1;
        while (arr[j] <= arr[i]) j--;
        swap(arr, i, j);
        reverse(arr, i + 1, arr.length - 1);
        return true;
    }
    
    static void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    static void reverse(char[] arr, int l, int r) {
        while (l < r) swap(arr, l++, r--);
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new