笔试时间：2024年03月21日

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

第一题

题目：讨厌鬼的糖葫芦

讨厌鬼有n串长度为m的糖葫芦，一串糖葫芦用一串字符串表示，糖葫芦的甜度为所有字符的甜度之和。字符的甜度为这个字符与字符'a'的差值。即'a'的甜度为 0,'b'的甜度为 1.....,'z'的甜度为 25。讨厌鬼现在想吃一根独一无二的糖葫芦，且这串糖葫芦甜度最大。一个糖葫芦独一无二当且仅当另外n-1根糖葫芦都与这根糖葫芦不同，若有一根糖葫芦本身或翻转后与这根糖葫芦相同，则这根糖葫芦不是独一无二的。例如糖葫芦"abc"与"cba"被认为是相同的，"abc"和"abc"也被认为是相同的。讨厌鬼想知道，他吃到这根糖葫芦串的甜度最大是多少？若吃不到任何独一无二糖葫芦，则输出 0。

输入描述

第一行输入两个整数n,m(1<=n<=50000, 1<=m<=10) 接下来n行，每行输入一个长度为m的字符串。

输出描述

一行一个整数表示最大的甜度。

样例输入一

3 3

ccz

cba

zcc

样例输出一

3

说明：只有第二根糖葫芦是独一无二的，甜度为 2 + 1 + 0 = 3。

样例输入二

2 3

abc

cba

样例输出二

0

参考题解

哈希表计数。对于每一个字符串s，分为两种情况处理：如果s是回文串，那么hash[s] += 1；否则，记s为s的翻转，则 hash[s]+=1 , hash[s]+=1

最后遍历所有的哈希表，找到值为1的字符串，计算其甜度即可。

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

#include <iostream>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    set<string> s;
    unordered_map<string, int> dic;
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        if (str == string(str.rbegin(), str.rend())) {
            dic[str]++;
        } else {
            dic[str]++;
            dic[string(str.rbegin(), str.rend())]++;
        }
    }
    int ans = 0;
    for (const auto& pair : dic) {
        if (pair.second == 1) {
            int sum = 0;
            for (char c : pair.first) {
                sum += c - 'a';
            }
            ans = max(ans, sum);
        }
    }
    cout << ans << endl;
    return 0;
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Set<String> s = new HashSet<>();
        Map<String, Integer> dic = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            String str = scanner.next();
            if (str.equals(new StringBuilder(str).reverse().toString())) {
                dic.put(str, dic.getOrDefault(str, 0) + 1);
            } else {
                dic.put(str, dic.getOrDefault(str, 0) + 1);
                dic.put(new StringBuilder(str).reverse().toString(), dic.getOrDefault(new StringBuilder(str).reverse().toString(), 0) + 1);
            }
        }
        int ans = 0;
        for (Map.Entry<String, Integer> entry : dic.entrySet()) {
            if (entry.getValue() == 1) {
                int sum = 0;
                for (char c : entry.getKey().toCharArray()) {
                    sum += c - 'a';
                }
                ans = Math.max(ans, sum);
            }
        }
        System.out.println(ans);
    }
}

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

from collections import defaultdict

n,m = map(int, input().split())
s = set()
dic = defaultdict(int)
for _ in range(n):
    string = input()
    if string == string[::-1]:
        dic[string] += 1
    else:
        dic[string] += 1
        dic[string[::-1]] += 1

ans = 0
for k,v in dic.items():
    if v==1:
        ans = max(ans, sum([ord(c) - ord('a') for c in k]))

print(ans)

第二题

题目：小红的三倍数

小红喜欢 3 的倍数的数字，现在小红有一个长度为 n 的数字串，小红想通过分隔字符串的方式，获得一些子串，每个子串代表一个数字，那么小红最多能获得多少个数字是 3 的倍数呢？比如，小红有数字 1123，那么可以分隔为[1,12,3]，这样获得了两个数字是 3 的倍数。请注意，分隔后的数字串，不能包含前导零，比如 012 不能视为 12。可以分割出 0，0 也是 3 的倍数。

输入描述

第一行输入一个没有前导零的正整数 n，表示小红的数字。

1<=n<=10^(10^5)

输出描述

输出一个整数，表示小红能够获得的 3 的倍数的数字的最大数量。

样例输入一

1123

样例输出一

2

说明：分割为 [1, 12, 3]，获得了 2 个 3 的倍数的数字。

样例输入二

300

样例输出二

3

说明：分割为 [3, 0, 0]，获得了 3 个 3 的倍数的数字。

参考题解

动态规划。记录f[i,j]的含义是：从i往后考虑，当前所取元素的值%3的值为j，可以获取的3的倍数的数量。那么对于每一个字符，操作为如下两种：1：当前字符计入已有的数，则f[i+1,(j+n[i])%3]，2：作为新的字符串，则为f[i+1,n[i]%3)，同时要判断已有的j是否为0，如果是0说明之前的子串已经是3的倍数，则+1。

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

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

using namespace std;

string n;
int length;
unordered_map<int, vector<int>> memo;

int dfs(int i, int cur) {
    if (i >= length) {
        return cur == 0 ? 1 : 0;
    }
    if (memo.count(i) && memo[i][cur] != -1) {
        return memo[i][cur];
    }
    int ans = dfs(i + 1, (cur + (n[i] - '0')) % 3);
    ans = max(ans, dfs(i + 1,