笔试时间：2024年04月16日

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

第一题

题目

游游拿到了一个仅由小写字母组成的字符串，她准备向其中添加一些'0'字符，使得操作后的字符串中，有尽可能多的连续子串恰好等于"you"。游游想知道最少需要添加几个字符？

输入描述

一个仅包含小写字母的字符串，长度不超过200000。

输出描述

一个整数，代表游游最少添加的字符。

样例输入

yuyouy

样例输出

1

参考题解

只需要找到所有的"yu"即可。

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

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int ans = 0;
    for (size_t i = 0; i < s.length() - 1; i++) {
        if (s.substr(i, 2) == "yu") {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int ans = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.substring(i, i + 2).equals("yu")) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

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

s = input()
ans = 0
for i in range(len(s) - 1):
    if s[i:i+2] == "yu":
        ans += 1
print(ans)

第二题

题目

游游拿到了3个大小为n的数组a, b, c。他准备重排c数组，使得有尽可能多的下表i满足ai + bi = ci,你能帮帮他吗？

输入描述

第一行输入一个正整数n，代表三个数组的大小

第二行输出n个正整数ai

第三行输出n个正整数bi

第四行输出n个正整数ci

1<=n<=1e5,1<=ai,bi,ci<=2e9

输出描述

一个整数，代表满足ai+bi=ci的i的数量。

样例输入

4,[1,2,3,4],[2,3,4,5],[4,5,6,7]

样例输出

2

参考题解

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

#include <iostream>
#include <unordered_map>
using namespace std;

const int MAXN = 100010;
long long a[MAXN];
unordered_map<long long, long long> mp;
unordered_map<long long, long long> st;

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

    long long ans = 0;
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        a[i] += x;
        mp[a[i]]++;
    }

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        st[x]++;
    }

    for (const auto &entry : st) {
        long long key = entry.first;
        long long value = entry.second;
        ans += min(value, mp[key]);
    }

    cout << ans << endl;
    return 0;
}

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

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

public class Main {
    static long[] a = new long[100010];
    static Map<Long, Long> mp = new HashMap<>();
    static Map<Long, Long> st = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long ans = 0;
        int n = scanner.nextInt();
        for (int i = 1; i <= n; i++)
            a[i] = scanner.nextLong();
        for (int i = 1; i <= n; i++) {
            long x = scanner.nextLong();
            a[i] += x;
            mp.put(a[i], mp.getOrDefault(a[i], 0L) + 1);
        }
        for (int i = 1; i <= n; i++) {
            long x = scanner.nextLong();
            st.put(x, st.getOrDefault(x, 0L) + 1);
        }
        for (Map.Entry<Long, Long> entry : st.entrySet()) {
            long key = entry.getKey();
            long value = entry.getValue();
            ans += Math.min(value, mp.getOrDefault(key, 0L));
        }
        System.out.println(ans);
    }
}

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

from collections import defaultdict

a = [0] * 100010
mp = defaultdict(int)
st = defaultdict(int)

n = int(input())
for i in range(1, n + 1):
    a[i] = int(input())
for i in range(1, n + 1):
    x = int(input())
    a[i] += x
    mp[a[i]] += 1
for i in range(1, n + 1):
    x = int(input())
    st[x] += 1

ans = 0
for key, value in st.items():
    ans += min(value, mp[key])

print(ans)

第三题

题目

游游拿到了一个数组，她每次操作可以将相邻的两个素数元素进行合并，合并后的新数为原来的两个数之和，并删除原来两个数。游游希望最终数组的元素数量尽可能少，你能帮帮她吗?

输入描述

第一行输入一个正整数n，代表数组的大小。

第二行输入n个正整数a;，代表数组的元素:

1<=n<=1e5 ,1<=ai<=1e6

输出描述

合并结束后的元素数量。

样例输入

5, [1, 3, 2, 5, 4]

样例输出

3

说明

先合并3、2，数组变为[1,5,5,4],然后合并5、5，变成[1,10,4]，所以最后长度为3。

参考题解

因为除了2以外的素数都是奇数，奇数加奇数一定为合数，而2和一个素数相加，依然可能为素数，所以先处理2，将2和附近能合并的素数且合并之后依然为素数的数合并，然后用栈依次遍历处理即可。

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

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 100010;
const int MAXP = 10000010;

int a[MAXN];
int prime[MAXP];
bool st[MAXP];
stack<long long> s;

bool check(long long x) {
    if (x <= MAXP) return !st[x];
    for (int j = 0; prime[j] <= x / prime[j]; j++) {
        if (x % prime[j] == 0) return false;
    }
    return true;
}

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

    st[0] = st[1] = true;
    int cnt = 0;
    for (int i = 2; i <= 1e7; i++) {
        if (!st[i]) prime[cnt++] = i;
        for (int j = 0; j < cnt && prime[j] <= 1e7 / i; j++) {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }

    int n;
    cin >> n;
    vector<int> b(MAXN);
    int cntt = 0;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] == 2) {
            if (i > 1