笔试时间：2025年9月6日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：构造二次函数

给定一个正整数s，请构造一个二次函数：f(x) = ax² + bx + c，使得该函数的顶点处的数值等于s。要求a, b, c ∈ [-100, 100]。

输入描述

第一行一个整数T (1 ≤ T ≤ 100)，表示数据组数。 接下来T行，每行一个正整数s (1 ≤ s ≤ 10⁴)。

输出描述

对于每组数据，输出一行，包含三个整数a, b, c，表示所构造的二次函数。要求：-100 ≤ a, b, c ≤ 100，且a ≠ 0。

样例输入

2

1

10

样例输出

1 0 1

1 0 10

参考题解

二次函数顶点纵坐标公式为：y = -b²/(4a) + c 只要取a = 1, b = 0，即可使顶点值为c = s。

C++：

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int s;
        cin >> s;
        cout << "1 0 " << s << endl;
    }
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int s = sc.nextInt();
            System.out.println("1 0 " + s);
        }
        sc.close();
    }
}

Python：

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    s = int(input())
    print(1, 0, s)

第二题：构造排列

给定两个整数n和m，请输出一个长度为n的排列，使得排列中"谷值"的个数恰好为m。 定义：当1 < i < n时，如果aᵢ < aᵢ₋₁且aᵢ < aᵢ₊₁，则认为位置i形成一个"谷值"。

输入描述

第一行一个整数T (1 ≤ T ≤ 100)，表示测试数据组数。 接下来每行两个整数n, m (3 ≤ n ≤ 100, 0 ≤ m ≤ ⌊(n-1)/2⌋)。

输出描述

对于每组数据，输出一个长度为n的排列。若有多个解，输出任意一个。

样例输入

2

3 0

5 2

样例输出

1 2 3

3 4 5 2 1

参考题解

观察到[m, m-1, ..., 1, m+1, m+2, ..., n]这种构造方式，从位置2到位置m都是满足谷值条件的，因此可以构造出恰好m个谷值。

C++：

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }
    
    // Rearrange: [m+1, m+2, ..., n] + [m, m-1, ..., 1]
    vector<int> result;
    for (int i = m; i < n; i++) {
        result.push_back(a[i]);
    }
    for (int i = m - 1; i >= 0; i--) {
        result.push_back(a[i]);
    }
    
    for (int i = 0; i < n; i++) {
        cout << result[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Java：

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            a.add(i);
        }
        
        ArrayList<Integer> result = new ArrayList<>();
        // Add [m+1, m+2, ..., n]
        for (int i = m; i < n; i++) {
            result.add(a.get(i));
        }
        // Add [m, m-1, ..., 1]
        for (int i = m - 1; i >= 0; i--) {
            result.add(a.get(i));
        }
        
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i));
            if (i < result.size() - 1) System.out.print(" ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            solve(sc);
        }
        sc.close();
    }
}

Python：

import sys
input = lambda: sys.stdin.readline().rstrip()

def solve():
    n, m = map(int, input().split())
    a = list(range(1, n + 1))
    a = a[m:] + a[:m][::-1]
    print(*a)

if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

第三题：最小差值

有一棵n个节点的树，其中每个节点i初始有一个整数值aᵢ。树上有n-1条边。定义树的稳定度为所有边(u,v)的|aᵤ - aᵥ|的最大值。 Levko可以修改至多k个节点的取值（每个节点的新值可以是任意整数），请问修改后最小的稳定度是多少。

输入描述

第一行两个整数n, k (1 ≤ n ≤ 2000, 0 ≤ k ≤ n)。 第二行n个整数aᵢ (0 ≤ aᵢ ≤ 100)。 接下来n-1行，每行两个整数u, v，表示一条边。

输出描述

输出一个整数，表示最小稳定度。

样例输入

5 2

4 7 4 7 4

1 2

2 3

3 4

4 5

样例输出

0

参考题解

使用二分答案+树形DP。二分稳定度D，对于固定的D，在树上做DP：dp[u][x]表示让节点u取值x时，使得以u为根的子树所有边差值≤D所需的最小改动数。通过滑动窗口优化将复杂度降到O(n·V)每次检查，整体O(n·V·log V)。

C++：

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 2005;
const int VAL_MAX = 100;
const int V = 101;

int n, k;
vector<int> s;
vector<vector<int>> g;
vector<int> parent, order;
int dp[MAXN][V];

vector<int> window_min(vector<int>& arr, int D) {
    vector<int> res(V);
    deque<int> dq;
    int add_ptr = 0;
    
    for (int i = 0; i < V; i++) {
        int L = max(0, i - D);
        int R = min(V - 1, i + D);
        
        while (add_ptr <= R) {
            while (!dq.empty() && arr[dq.back()] >= arr[add_ptr]) {
                dq.pop_back();
            }
            dq.push_back(add_ptr);
            add_ptr++;
        }
        
        while (!dq.empty() && dq.front() < L) {
            dq.pop_front();
        }
        
        res[i] = arr[dq.front()];
    }
    return res;
}

bool feasible(int D) {
    for (int u : order) {
        vector<int> base(V);
        int su = s[u];
        
        for (int x = 0; x < V; x++) {
            base[x] = (x == su) ? 0 : 1;
        }