笔试时间：2025年9月17日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：大模型分词

您正在为一种罕见的语言构建一个专用的大语言模型。由于训练样本缺失，传统BPE等标准的分词器效果不佳，使得大模型推理生成的句子不理想。

幸运的是，一位语言学家为罕见语言的已知词根和词缀（统称为"词元"或"Token"）都标注了一个置信度分数，这个分数代表了该词元作为一个"独立单位"的合理性。同时，语言学家还总结出了一个转移分数表，表示当前词元选择对下一个词元"置信度"的影响。

您的任务是设计并实现一个"最优分词器"，它能将输入的罕见语言句子（一个不含空格的英文小写字符串）切分成一系列词元，并使得所有词元的置信度分数之和达到最大。

输入描述

• 第1行为输入的、不含空格的罕见字符串 text，假设只含英文小写字符
• 第2行为已知置信度词汇表的个数 n
• 随后 n 行为已标注词元及其置信度分数 P，以空格分隔
• 第 n+3 行为转移分数的个数 m
• 随后 m 行为转移分数数据，包括起始词、下一个词、转移分数加分 X，以空格分隔

输入限制：

• 0 < len(text) ≤ 100
• -100 ≤ 转移分数表中的影响分数 X ≤ 100
• -100 ≤ 词汇表置信度分数 P ≤ 100
• 0 < 词汇表大小 n ≤ 100

输出描述

返回最高的分词得分，若根据已知词汇表无法拆分则返回0。

样例输入

applepie

2

pen 3

apple 10

2

pen apple 5

pie apple 2

样例输出

0

样例说明： text句子中含有不在已知词汇表中出现的词，无法进行拆分。

参考题解

解题思路：

这是一个动态规划分词问题，需要将输入字符串切分为一系列已知词元，使得所有词元的置信度分数之和加上转移分数之和达到最大。

1. 状态定义：使用dp[i]表示处理到第i个字符时的最优解状态。由于需要考虑转移分数，dp[i]需要记录以不同词元结尾时的最大得分。
2. 状态转移：对于每个位置i，遍历所有可能的起始位置j（0≤j<i），检查子串text[j:i]是否在已知词元表中。
3. 边界条件：dp[0]初始化为空字符串''得分为0。
4. 最终结果：dp[len(text)]中所有可能状态的最大值。

Python：

import sys

def optimal_tokenizer():
    text = sys.stdin.readline().strip()
    n = int(sys.stdin.readline())
    
    confidences = {}
    for _ in range(n):
        token, score_str = sys.stdin.readline().split()
        confidences[token] = int(score_str)
    
    m = int(sys.stdin.readli