笔试时间：2023年9月20日 秋招

第一题

题目：小红的子数组权值

小红拿到了一个数组。她定义一个连续子数组的权值为: 子数组内不同元素的个数。小红想知道，权值分别为1,2,3,...,n的子数组数量

有多少个？

输入描述

第一行输入一个正整数，代表数组的元素数量；

第二行输入n个正整数a;，代表小红拿到的数组。

1 <= n, ai <= 2000

输出描述

n个整数，分别代表权值为1,2,3,...,n的子数组数量。

样例输入

4

1 2 2 3

样例输出

5 4 1 0

参考题解

模拟，枚举每个元素作为起点，从右插入到set中。直接用一个集合进行模拟即可，最后对集合的大小进行统计。

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

#include <iostream>
#include <unordered_set>

using namespace std;
typedef long long ll;
const int N = 2004;

int counts[N];
int numbers[N];
int n;

int main() {
    unordered_set<int> uniqueNumbers;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> numbers[i];
    }
    
    for (int i = 1; i <= n; i++) {
        uniqueNumbers.clear();
        for (int j = i; j <= n; j++) {
            uniqueNumbers.insert(numbers[j]);
            counts[uniqueNumbers.size()]++;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        cout << counts[i] << (i == n ? "\n" : " ");
    }
}

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

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = 2004;
        int[] counts = new int[N];
        int[] numbers = new int[N];
        int n = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            numbers[i] = scanner.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            HashSet<Integer> uniqueNumbers = new HashSet<>();
            for (int j = i; j <= n; j++) {
                uniqueNumbers.add(numbers[j]);
                counts[uniqueNumbers.size()]++;
            }
        }

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

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

N = 2004
counts = [0] * N
numbers = [0] * N
n = int(input())

numbers[1:n+1] = map(int, input().split())

for i in range(1, n + 1):
    uniqueNumbers = set()
    for j in range(i, n + 1):
        uniqueNumbers.add(numbers[j])
        counts[len(uniqueNumbers)] += 1

for i in range(1, n + 1):
    print(counts[i], end=" \n"[i == n])

第二题

题目：平均数大于k的最长子序列

给定n个正整数组成的数组，求平均数大于k的最长子序列的长度。

输入描述

第一行输入两个正整数n和k，用空格隔开；

第二行输入n个正整数ai，用来表示数组。

1 <= n <=