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

第一题

题目：小红查单词

小红拿到了一个仅由英文字母组成的字符串。她想知道某单词在该字符串中出现了多少次，你能帮帮她吗？请注意，小红会询问多次。

输入描述

第一行输入两个正整数n和q，代表字符串长度和询问次数。第二行输入一行长度为n的，仅由小写英文字母组成的字符串。代表小红拿到的字符串。接下来的q行，每行输入一个仅由小写英文字母组成的字符串，代表小红的每次查询。

1<=n,q<=10^5。每次查询的字符串长度不超过 10。

输出描述

输出q行，每行输出一个整数，代表该次查询的结果。

样例输入

10 3

bobobalice

bob

alice

red

样例输出

2

1

0

参考题解

字符串Hash，模拟十进制加法。

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

#include <iostream>
#include <map>
#include <string>
#include <vector>

constexpr unsigned long long base = 13331;
constexpr int maxLen = 10;

unsigned long long calculateHash(const std::string& s) {
    unsigned long long hash = 0;
    for (char c : s) {
        hash = hash * base + c;
    }
    return hash;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    unsigned int n, q;
    std::cin >> n >> q;

    std::string s;
    std::cin >> s;

    std::vector<unsigned long long> h(n + 1, 0);
    std::vector<unsigned long long> p(n + 1, 1);

    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * base + s[i - 1];
        p[i] = p[i - 1] * base;
    }

    std::map<unsigned long long, int> mp;

    for (int len = 1; len <= maxLen; len++) {
        for (int i = 0; i < n; i++) {
            if (i + len > n) {
                break;
            }
            unsigned long long now = h[i + len] - h[i] * p[len];
            mp[now] += 1;
        }
    }

    for (unsigned int i = 0; i < q; i++) {
        std::string x;
        std::cin >> x;
        unsigned long long y = calculateHash(x);

        if (mp.count(y)) {
            std::cout << mp[y] << "\n";
        } else {
            std::cout << 0 << "\n";
        }
    }

    return 0;
}

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

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

public class Main {
    static final long base = 13331;
    static final int maxLen = 10;

    static long calculateHash(String s) {
        long hash = 0;
        for (char c : s.toCharArray()) {
            hash = hash * base + c;
        }
        return hash;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int q = sc.nextInt();

        sc.nextLine(); // Consume newline

        String s = sc.nextLine();

        long[] h = new long[n + 1];
        long[] p = new long[n + 1];

        h[0] = 0;
        p[0] = 1;

        for (int i = 1; i <= n; i++) {
            h[i] = h[i - 1] * base + s.charAt(i - 1);
            p[i] = p[i - 1] * base;
        }

        Map<Long, Integer> mp = new HashMap<>();

        for (int len = 1; len <= maxLen; len++) {
            for (int i = 0; i < n; i++) {
                if (i + len > n) {
                    break;
                }
                long now = h[i + len] - h[i] * p[len];
                mp.put(now, mp.getOrDefault(now, 0) + 1);
            }
        }

        for (int i = 0; i < q; i++) {
            String x = sc.nextLine();
            long y = calculateHash(x);

            if (mp.containsKey(y)) {
                System.out.println(mp.get(y));
            } else {
                System.out.println(0);
            }
        }
    }
}

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

def calculate_hash(s, base):
    hash_val = 0
    for c in s:
        hash_val = hash_val * base + ord(c)
    return hash_val

base = 13331
max_len = 10

n, q = map(int, input().split())
s = input()

h = [0] * (n + 1)
p = [1] * (n + 1)

for i in range(1, n + 1):
    h[i] = h[i - 1] * base + ord(s[i - 1])
    p[i] = p[i - 1] * base

mp = {}

for length in range(1, max_len + 1):
    for i in range(n):
        if i + length > n:
            break
        now = h[i + length] - h[i] * p[length]
        mp[now] = mp.get(now, 0) + 1

for _ in range(q):
    x = input()
    y = calculate_hash(x, base)
    if y in mp:
        print(mp[y])
    else:
        print(0)

第二题

题目：小红的魔法数组

小红有两个长度为 n 的数组，分别为 a和b。她可以施展魔法，先选择一个实数mul，获得c数组，其中ci=mul* ai+bi，小红想知道，她能获得的数组 c，最多有几个 0。

输入描述

一行一个整数 n，表示数组的长度。一行n个整数ai，表示数组a。一行n 个整数bi，表示数组 b。

1<=n<=10^5；-10^9<ai,bi<=10^9

输出描述

输出一个正整数，表示最多有几个0。

样例输入

4

2 4 6 7

1 2 3 4

样例输出

3

说明

选样mul=-0.5，得到e=[0,0,0,0.5]，有3个0。

参考题解

将a[i]=0且b[i]=0的情况单独算，记为cnt，统计下b[i]/a[i]的结果数量取最大值，输出最大值与cnt的和。

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

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<double> a(n);
    vector<double> b(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    map<double, int> mp;
    int zeroPairs = 0;
    int maxPairCount = 0;

    for (int i = 0; i < n; i++) {
        if (a[i] == 0 && b[i] == 0) {
            zeroPairs++;
        } else if (a[i] != 0) {
            double ratio = b[i] / a[i];
            mp[ratio]++;
            maxPairCount = max(maxPairCount, mp[ratio]);
        }
    }

    int result = maxPairCount + zeroPairs;
    cout << result << endl;

    return 0;
}

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

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

public class Main