筆試時(shí)間：2025年03月22日

歷史筆試傳送門：

2023春招秋招筆試合集

2024春招秋招筆試合集

第一題

題目

小X在一片大陸上探險(xiǎn)，有一天他發(fā)現(xiàn)了一個(gè)洞穴，洞穴里面有n道門，打開每道門都需要對應(yīng)的鑰匙，編號(hào)為i的鑰匙能用于打開第i道門，而且只有在打開了第i(i>1)道門之后，才能打開第i+1道門，一開始只能打開第1道門。幸運(yùn)的是，小X在外面探索的途中，每天都能發(fā)現(xiàn)一把能打開這n道門中其中一道門的鑰匙，每天找完鑰匙后他都會(huì)去打開所有能打開的門?，F(xiàn)在給出他每天找到的鑰匙編號(hào)，請問每道門分別在哪一天被打開。

輸入描述

第一行包含一個(gè)正整數(shù)n，表示門的數(shù)量。

接下來一行包含n個(gè)正整數(shù)a1，a2，…， an，其中ai,表示第i天他找到的鑰匙的編號(hào)，能夠打開第ai道門，數(shù)據(jù)保證a1-an為1-n的一個(gè)排列。

輸出描述

輸出一行n個(gè)數(shù)s1，s2，…，sn，其中si,表示第i道門在第si天被打開。

樣例輸入

5

5 3 1 2 4

樣例輸出

3 4 4 5 5

參考題解

哈希

C++：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

#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：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

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 次時(shí)，cur 被覆蓋
                cur++;
            }
        }

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

Python：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

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:])))

第二題

題目

有一種十分奇妙的約分:并非是分子分母同時(shí)除以一個(gè)數(shù)，而是上下同時(shí)刪除相同的數(shù)字。例如，114514/1919810 ->14514/919810 ->1454/91980這樣。當(dāng)然我們知道這樣約分后的結(jié)果可能和正常約分的結(jié)果并不一致，因此我們才稱這一過程為奇妙的約分。

在奇妙的約分過程中，一個(gè)數(shù)可能會(huì)出現(xiàn)前導(dǎo)0。此時(shí)，我們會(huì)將前導(dǎo)0保留，只要保證數(shù)字沒有被完全刪除，以及分母不是全為0即可。

現(xiàn)在，給出兩個(gè)分?jǐn)?shù)，你需要判斷第二個(gè)分?jǐn)?shù)是否能夠由第一個(gè)分?jǐn)?shù)經(jīng)過上述“奇妙的約分”得到。

輸入描述

第一行一個(gè)正整數(shù)T，表示有T組數(shù)據(jù)。

對于每一組數(shù)據(jù)，輸入一行兩個(gè)形如a/b的分?jǐn)?shù)，中間用空格隔開。

1≤T<10,1≤a,b≤10^10000，保證輸入的數(shù)字無前導(dǎo)零。

輸出描述

對于每一組數(shù)據(jù)，如果第二個(gè)分?jǐn)?shù)能夠由第一個(gè)分?jǐn)?shù)經(jīng)過上述“奇妙的約分”得到，輸出Yes;否則，輸出NO.

特別地，當(dāng)?shù)诙€(gè)分?jǐn)?shù)不需要操作即等于第一個(gè)分?jǐn)?shù)時(shí)，也輸出yes

樣例輸入

4

114514/1919810 1454/91980

114514/1919810 454/9980

114514/1919810 114514/1919810

21/42 1/2

樣例輸出

Yes

Yes

Yes

NO

參考題解

維護(hù)哈希表記錄分子分母的字符個(gè)數(shù)，然后對每一個(gè)分?jǐn)?shù)的分子分母進(jìn)行判斷，注意全0的情況。

C++：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

#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]++;
    }