笔试时间：2025年03月22日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目

小X在一片大陆上探险，有一天他发现了一个洞穴，洞穴里面有n道门，打开每道门都需要对应的钥匙，编号为i的钥匙能用于打开第i道门，而且只有在打开了第i(i>1)道门之后，才能打开第i+1道门，一开始只能打开第1道门。幸运的是，小X在外面探索的途中，每天都能发现一把能打开这n道门中其中一道门的钥匙，每天找完钥匙后他都会去打开所有能打开的门。现在给出他每天找到的钥匙编号，请问每道门分别在哪一天被打开。

输入描述

第一行包含一个正整数n，表示门的数量。

接下来一行包含n个正整数a1，a2，…， an，其中ai,表示第i天他找到的钥匙的编号，能够打开第ai道门，数据保证a1-an为1-n的一个排列。

输出描述

输出一行n个数s1，s2，…，sn，其中si,表示第i道门在第si天被打开。

样例输入

5

5 3 1 2 4

样例输出

3 4 4 5 5

参考题解

哈希

C++：[此代码未进行大量数据的测试，仅供参考]

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    unordered_set<int> st;
    int cur = 1;
    vector<int> ans(n + 1);
    for (int i = 0; i < n; i++) {
        int key;
        cin >> key;
        st.insert(key);
        while (cur <= n && st.count(cur)) {
            ans[cur] = i + 1;
            cur++;
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Set<Integer> st = new HashSet<>();
        int cur = 1;
        int[] ans = new int[n + 1];

        for (int i = 0; i < n; i++) {
            int key = scanner.nextInt();
            st.add(key);
            while (cur <= n && st.contains(cur)) {
                ans[cur] = i + 1; // 第 i+1 次时，cur 被覆盖
                cur++;
            }
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(ans[i] + " ");
        }
        System.out.println();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

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

st = set()
cur = 1
ans = [0] * (n + 1)

for i in range(n):
    key = arr[i]
    st.add(key)
    while cur <= n and cur in st:
        ans[cur] = i + 1
        cur += 1

print(' '.join(map(str, ans[1:])))

第二题

题目

有一种十分奇妙的约分:并非是分子分母同时除以一个数，而是上下同时删除相同的数字。例如，114514/1919810 ->14514/919810 ->1454/91980这样。当然我们知道这样约分后的结果可能和正常约分的结果并不一致，因此我们才称这一过程为奇妙的约分。

在奇妙的约分过程中，一个数可能会出现前导0。此时，我们会将前导0保留，只要保证数字没有被完全删除，以及分母不是全为0即可。

现在，给出两个分数，你需要判断第二个分数是否能够由第一个分数经过上述“奇妙的约分”得到。

输入描述

第一行一个正整数T，表示有T组数据。

对于每一组数据，输入一行两个形如a/b的分数，中间用空格隔开。

1≤T<10,1≤a,b≤10^10000，保证输入的数字无前导零。

输出描述

对于每一组数据，如果第二个分数能够由第一个分数经过上述“奇妙的约分”得到，输出Yes;否则，输出NO.

特别地，当第二个分数不需要操作即等于第一个分数时，也输出yes

样例输入

4

114514/1919810 1454/91980

114514/1919810 454/9980

114514/1919810 114514/1919810

21/42 1/2

样例输出

Yes

Yes

Yes

NO

参考题解

维护哈希表记录分子分母的字符个数，然后对每一个分数的分子分母进行判断，注意全0的情况。

C++：[此代码未进行大量数据的测试，仅供参考]

#include<bits/stdc++.h>
using namespace std;
void solve() {
    string a, b;
    cin >> a >> b;
    string x1 = a, y1, x2 = b, y2;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '/') {
            x1 = a.substr(0, i);
            y1 = a.substr(i + 1);
        }
    }
    for (int i = 0; i < b.size(); i++) {
        if (b[i] == '/') {
            x2 = b.substr(0, i);
            y2 = b.substr(i + 1);
        }
    }
    unordered_map<char, int> m1, m2, m3, m4;
    for (char c : x1) {
        m1[c]++;
    }