笔试时间：2024年05月15日

历史笔试传送门：2023秋招笔试合集

第一题

题目：小红的子序列排列

小红拿到了一个数组，她想知道该数组有多少个子序列是排列。由于答案过大，请对10^9+7取模。排列是一个长度为k的数组，其中1到k都恰好出现一次。例如[2,3,1]是排列，而[1,3,3]、[1,5,2,3]则不是排列。子序列指数组取若干元素（可以不连续）按原数组顺序形成的新数组。

输入描述

第一行输入一个正整数n，代表小红拿到的数组。第二行输入n个正整数ai，代表数组中的元素。

1<=n<=10^5

1<=ai<=10^9

输出描述

一个整数，代表子序列是排列的数量。

样例输入一

3

1 2 1

样例输出一

4

说明：有两个[1]子序列，1个[1,2]子序列，1个[2,1]子序列

样例输入二

1

2

样例输出二

0

参考题解

数学题。可以组成最长的排列取决于n，而n范围是10w，因此我们只需要枚举n即可。

如果存在2的排列数假设为x，那么假设存在y个3，那么此时3的排列数是x*y，利用这个性质即可快速求解。

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

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

const int MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    unordered_map<int, int> cnt;
    for(int num : nums) {
        cnt[num]++;
    }

    long long res = 0;
    long long pro = 1;
    for(int i = 1; i <= 100000; ++i) {
        if(cnt.find(i) == cnt.end()) break;
        res = (res + cnt[i] * pro) % MOD;
        pro = (pro * cnt[i]) % MOD;
    }

    cout << res << endl;
    return 0;
}

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

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    private static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int num : nums) {
            cnt.put(num, cnt.getOrDefault(num, 0) + 1);
        }

        long res = 0;
        long pro = 1;
        for (int i = 1; i <= 100000; i++) {
            if (!cnt.containsKey(i)) break;
            res = (res + cnt.get(i) * pro) % MOD;
            pro = (pro * cnt.get(i)) % MOD;
        }

        System.out.println(res);
    }
}

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

from collections import Counter

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

MOD = 1000000007

cnt = Counter(nums)

res = 0
pro = 1
for i in range(1, 100001):
    if i not in cnt: break
    res = (res + cnt[i]*pro) % MOD
    pro = (pro*cnt[i])%MOD

print(res)

第二题

题目：小红的01串字串计算

小红拿到了一个01串，她想知道有多少个字符串作为连续子串在01串中出现了至少k次？

输入描述

第一行输入两个正整数n,k，代表字符串长度、子串的至少出现次数。

第二行输入一个长度为n的、仅由'0'和'1'组成的字符串。

1<=k<=n<=400

输出描述

一个整数，代表出现了至少k次的字符串数量。

样例输入

6 2

010100

样例输出

5

说明："0"、"1"、"01"、"10"、"010"这五个字符串都出现了至少2次。

参考题解

枚举。题目的数据比较小，因此直接枚举所有的子串，判断子串的出现次数是否满足>=k即可。

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

#include <iostream>
#include <string>
#include <set>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    set<string> ans;
    
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            string sub = s.substr(i, j - i);
            int cnt = 0;
            for (int l = 0; l < n; ++l) {
                if (l + j - i > n) break;