笔试时间：2025年9月24日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：海蒂爷爷的木桶

海蒂爷爷想做一个奇怪的木桶。

他去山里砍了一些木柴并加工成高矮不一的木板，然后他把木板按高矮排好顺序，依次取出，竖在地上，排列成一个圆桶状。该圆桶满足循环单调非递减规律（即从第1块木板开始，后续的木板不矮于前一根，直到最高的木板与第一块最矮的木板连接在一起）。

比如序列 3 4 5 1 2 1，表示有7根木板，最矮的木板高度为1，最高的木板高度为5。起始木板高度为3，然后按木板高度依次排列，直到排到最高木板后，再从高度为1的最矮木板开始继续排列。

正当海蒂爷爷想用铁箍将木桶箍上时，小海蒂从远处跑来，递给爷爷一条新的木板。请给海蒂爷爷想想办法，把新木板插入合适的位置，把奇怪的木桶完成。

如果新木板有多个位置可以插入时，则请放置在下标最小的位置。如 1 2 3 1 插入 1，预期输出结果为 1 1 2 3 1，而不是 1 2 3 1 1。

输入描述

输出描述

返回插入新数据后的boards列表。

样例输入

4

2 3 4 2

1

样例输出

2 3 4 1 2

样例说明1

新增木板长度为1，只有插在原第3块和第4块木板之间，才能满足循环非递减规律。

参考题解

解题思路：

1. 理解循环非递减的判定条件：整个环中最多只能有一个"下降点"
2. 枚举所有可能的插入位置（共n+1个位置）
3. 在每个位置插入新木板，生成新序列
4. 检查新序列是否满足循环非递减条件
5. 找到第一个满足条件的位置即可

C++：

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

bool check(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return true;
    
    int drop_count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > arr[(i + 1) % n]) {
            drop_count++;
        }
    }
    
    return drop_count <= 1;
}

int main() {
    int n;
    cin >> n;
    vector<int> boards(n);
    for (int i = 0; i < n; i++) {
        cin >> boards[i];
    }
    int newBoardLen;
    cin >> newBoardLen;
    
    for (int i = 0; i <= n; i++) {
        vector<int> temp_boards = boards;
        temp_boards.insert(temp_boards.begin() + i, newBoardLen);
        
        if (check(temp_boards)) {
            for (int j = 0; j < temp_boards.size(); j++) {
                if (j > 0) cout << " ";
                cout << temp_boards[j];
            }
            cout << endl;
            break;
        }
    }
    
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static boolean check(List<Integer> arr) {
        int n = arr.size();
        if (n <= 1) return true;
        
        int dropCount = 0;
        for (int i = 0; i < n; i++) {
            if (arr.get(i) > arr.get((i + 1) % n)) {
                dropCount++;
            }
        }
        
        return dropCount <= 1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> boards = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            boards.add(sc.nextInt());
        }
        int newBoardLen = sc.nextInt();
        
        for (int i = 0; i <= n; i++) {
            List<Integer> tempBoards = new ArrayList<>(boards);
            tempBoards.add(i, newBoardLen);
            
            if (check(tempBoards)) {
                for (int j = 0; j < tempBoards.size(); j++) {
                    if (j > 0) System.out.print(" ");
                    System.out.print(tempBoards.get(j));
                }
                System.out.println();
                break;
            }
        }
    }
}

Python：

import sys

def check(arr):
    n = len(arr)
    if n <= 1:
        return True
    
    drop_count = 0
    for i in range(n):
        if arr[i] > arr[(i + 1) % n]:
            drop_count += 1
    
    return drop_count <= 1

def main():
    n = int(sys.stdin.readline().strip())
    boards = list(map(int, sys.stdin.readline().strip().split()))
    newBoardLen = int(sys.stdin.readline().strip())
    
    for i in range(n + 1):
        temp_boards = boards[:]
        temp_boards.insert(i, newBoardLen)
        
        if check(temp_boards):
            print(*temp_boards)
            break

main()

第二题：关灯方案

老旧小区需要关闭一排灯，由于接线混乱，按某个灯的开关时可能会同步影响多个灯的状态，被影响的灯的状态会发生反转，即原先亮着的灯会关闭，而关闭的灯会打开。

已知第i个开关除了改变i号灯的状态之外，还会额外影响多个灯的状态；请问是否存在方案使得所有的灯都关闭。如果无解则输出-1；有解时输出选择按开关数量最小的方案，如果数量相同再比较字典序最小的方案。

输入描述

输出描述

样例输入

2 2

0 1

1 2

2 1

样例输出

-1

样例说明1

两盏灯互相影响，无法全部关闭。

参考题解

解题思路：

1. 使用状态压缩，用二进制位表示灯的状态和开关的影响范围
2. 暴力枚举所有可能的开关组合（2^n种情况）
3. 对于每个组合，模拟按下开关后的最终状态
4. 检查最终状态是否为0（所有灯关闭）
5. 选择开关数量最少、字典序最小的方案

C++：

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

int main() {
    int a, b;
    cin >> a >> b;
    
    int h = 0;
    for (int i = 0; i < a; i++) {
        int val;
        cin >> val;
        if (val == 1) {
            h |= (1 << i);
        }
    }
    
    vector<int> d(a, 0);
    for (int k = 0; k < a; k++) {
        d[k] |= (1 << k);
    }
    
    for (int i = 0; i < b; i++) {
        int m, n;
        cin >> m >> n;
        d[m - 1] |= (1 << (n - 1));
    }
    
    vector<int> o;
    bool p = false;
    
    for (int q = 0; q < (1 << a); q++) {
        int r = h;
        for (int s = 0; s < a; s++) {
            if ((q >> s) & 1) {
                r ^= d[s];
            }
        }
        
        if (r == 0) {
            vector<int> t;
            for (int u = 0; u < a; u++) {
                if ((q >> u) & 1) {
                    t.push_back(u + 1);
                }
            }
            
            if (!p) {
                o = t;
                p = true;
            } else {
                if (t.size() < o.size() || (t.size() == o.size() && t < o)) {
                    o = t;
                }
            }
        }
    }
    
    if (!p) {
        cout << -1 << endl;
    } else {
        for (int i = 0; i < o.size(); i++) {
            if (i > 0) cout << " ";
            cout << o[i];
        }
        cout << endl;
    }
    
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.next