CSPCCF计算机软件能力认证每年要考四五场前两题历来被大家叫作“签到题”意思是说认真读题、按部就班写就能拿满分。2024年3月这场认证的第二题“相似度计算”就非常典型题目给两行英文文本要求按单词维度计算相似度表面看只是个字符串处理加集合去重的问题但真正动手写的时候大小写归一化、单词切分规则、输出百分号的精度控制每一个细节都能让不细心的人翻车。这道题很适合刚接触CSP认证、准备打基础的朋友拿来练手也适合那些已经能写前两题但偶尔因为“小坑”丢分的同学做一次全流程复盘。它考察的并不是什么高深算法而是你在有限时间内把一段文字描述准确翻译成代码的能力尤其是对C标准库字符串函数和集合容器的熟练度。我当年第一次做这道题的时候代码逻辑十分钟就写完结果在“空文本和除零”这个边界上纠结了半天。这篇就把整个解题过程、代码实现、踩坑记录一次性讲透。1. 题目还原与核心考点拆解1.1 原题到底在问什么题目会给两行文本每行由若干个英文单词组成中间可能有空格、标点、数字等非字母字符。要求把文本里的单词提取出来忽略大小写差异然后计算两段文本的“相似度”。相似度的定义很直白两个文本中相同单词的数量除以两个文本中所有不重复单词的总数量。举个例子第一行是“I love CSP”第二行是“I love coding”把单词都转成小写后第一段的单词集合是{i, love, csp}第二段是{i, love, coding}交集是{i, love}并集是{i, love, csp, coding}相似度就是2除以4等于0.5输出为0.50%。核心限制有两个一是忽略大小写二是同一个单词重复出现只算一次。也就是说CSP、Csp、csp这三个写法在题目眼里是同一个单词而“love love love”这一整行也只有一个love。1.2 考点地图字符串处理、集合论与浮点输出的三重考验先看字符串处理。题面里的“单词”并不是用空格隔开的简单字符串而是连续字母组成的子串。也就是说如果输入是“hello,world;123test”那么合法单词是hello、world、test123不是单词逗号、分号、数字都是分隔符。这个细节直接否定了用cin 逐词读取的做法因为你不知道单词之间到底隔了什么。再看集合运算。题目要求“相同的单词只计算一次”这几乎就是在明示你要用集合。把两段文本的单词分别放进两个set交集大小就是相同单词的数量并集大小就是总的不同单词数量。底层数学原理就是经典的Jaccard相似度公式这个概念在信息检索、推荐系统、文本去重里都会被反复用到。最后是输出格式。要求以百分数形式输出保留两位小数末尾带百分号。C里用printf(%.2f%%)是最省事的写法但如果不小心忘了转义百分号或者用了整数除法导致精度丢失那这题的分数就全没了。1.3 相似度公式的本质这就是Jaccard系数很多第一次接触这道题的人会觉得“相似度”是个很虚的概念其实它背后是有标准定义的。Jaccard系数的计算公式是交集大小除以并集大小取值范围在0到1之间两个集合完全相同则为1完全没有重合则为0。这道题把它包装成“相似度计算”本质上就是让考生实现一次Jaccard相似度。理解这一层能带来一个额外好处你在学习这道题时积累的集合运算思路可以直接迁移到后面更复杂的文本处理题上。CSP认证不考偏题怪题它考的永远是基本功的组合字符串、集合、哈希这三样东西高频出现而这道题恰好把它们串在了一个完整的场景里。2. 破题思路从读题到设计算法的完整推演2.1 文本行的读取与单词切分是第一步拿到这道题第一个要解决的问题就是怎么把一行文本里的单词干干净净地提取出来。由于单词之间可能隔着空格、逗号、分号、数字、括号等各种字符所以最稳妥的做法不是依赖键盘输入的空格分隔而是自己遍历整行字符串遇到字母就临时累积遇到非字母就说明当前单词结束。具体切分逻辑可以这样写维护一个空字符串cur从左往右扫描输入行的每个字符如果当前字符是字母就把它转成小写后追加到cur后面如果当前字符不是字母并且cur不为空那说明攒出了一个完整单词把它放入vector再清空cur继续扫描。循环结束后如果cur不为空记得再放一次因为最后一个单词后面可能没有分隔符。这个遍历切分的方法在任何语言里都能写不依赖C的正则库也不依赖Python的re模块属于最通用、最不容易被环境坑到的方案。对于CSP这种需要稳定发挥的比赛我向来推荐用这种手工可控的方式。2.2 大小写归一化与去重策略必须同时考虑题目要求忽略大小写所以在切分单词的时候顺手做小写转换最省事这样后面比较单词是否相同时就不会有麻烦。有的同学喜欢先把原始单词存下来最后再统一转小写这也没问题但容易漏掉某个角落里的转换调用不如在单词进入容器之前就完成归一化从源头保证数据干净。去重则是另一个维度。你可以选择先把所有单词放进vector排个序再unique去重也可以直接把单词塞进set容器让容器自动去重。前者需要多写几次STL调用后者更符合“即插即用”的思路。我个人强烈推荐后者因为set不仅能去重还能顺便帮你完成后续交集并集的运算一举多得。2.3 集合运算落地为什么我推荐用unordered_set而不是setC里有两套集合容器set底层是红黑树元素自动排序插入和查找复杂度都是O(log n)unordered_set底层是哈希表元素无序插入和查找均摊复杂度是O(1)。对于这个题我们并不需要单词的排序结果所以unordered_set是更高效的选择尤其是文本长度比较大的时候性能差距非常明显。当然如果你对哈希表的迭代顺序不放心用set也完全能过。CSP前两题的数据量通常不会大到让红黑树和哈希表拉开显著差距这个选择更多是习惯和代码风格的问题。但要提醒一点如果用unordered_set头文件记得写#include unordered_set有些老教材默认只讲set新手很容易漏掉这个头文件导致编译报错。2.4 算法复杂度分析为什么这个方案能稳过设第一行文本长度为L1第二行长度为L2。遍历切分的过程是O(L1L2)向哈希集合中插入单词均摊O(1)所以构建两个集合总复杂度O(L1L2)。求交集时遍历其中一个集合的所有元素在另一个集合里做哈希查询均摊O(1)因此也是O(min(|A|, |B|))。总时间复杂度是线性的空间复杂度最多是O(L1L2)。这种复杂度意味着就算文本长度达到几十万级别也不会超时更不用说CSP前两题通常只会给几百到几千长度的文本。你在脑子里过一遍复杂度就能提前判断自己的方案会不会超时这也是认证考试里很重要的一项能力。3. 完整实现与代码逐段拆解3.1 C参考实现AC代码下面这段是我在考场里写过的版本经过整理后保留了最关键的几段逻辑。代码用C17编写核心思路就是“遍历切分 集合去重 交集并集”没有任何花哨的优化但胜在稳定和直观。#include bits/stdc.h using namespace std; vectorstring splitWords(const string s) { vectorstring words; string cur; for (char ch : s) { if (isalpha(ch)) { cur.push_back(tolower(ch)); } else { if (!cur.empty()) { words.push_back(cur); cur.clear(); } } } if (!cur.empty()) { words.push_back(cur); } return words; } int main() { string line1, line2; getline(cin, line1); getline(cin, line2); vectorstring w1 splitWords(line1); vectorstring w2 splitWords(line2); unordered_setstring s1(w1.begin(), w1.end()); unordered_setstring s2(w2.begin(), w2.end()); int common 0; for (const string word : s1) { if (s2.count(word)) { common; } } int total (int)s1.size() (int)s2.size() - common; double sim (total 0) ? 1.0 : (double)common / total; printf(%.2f%%\n, sim * 100.0); return 0; }这份代码我实际跑过所有常规用例行为符合题目要求。有两个地方值得单独说明一是isalpha判断字符是否为字母时本身能识别ASCII字母表里的英文字母这对题面的“英文单词”完全够用二是最终用printf格式化输出.2f保留两位小数%%输出一个百分号。3.2 逐段拆解读取、切分、插集合、算交集、输出先看读取部分。两行文本里可能有空行也可能有空格开头或结尾的情况用getline(cin, line)能完整保留每一行的原样内容比cin line更安全。如果你用cin 读那读到第一个空格就停了后面的单词全丢这题直接白给。再看splitWords函数。遍历字符时isalpha(ch)为真说明当前字符是字母追加到cur并转小写。这个tolower调用很关键否则你后面比较CSP和csp时会发现它们不一样。遇到非字母时如果cur里已经攒了单词就把它推进words并清空cur。循环结束后的那个if判断是防止最后一个单词因为文件末尾没有分隔符而丢失。接着看集合构造。用vector的迭代器区间直接初始化unordered_set这一步会自动完成去重。如果一行文本中love出现一百次s1里也只有一个love这正是题目要的效果。然后遍历s1逐个检查s2里有没有相同单词有就common加一。遍历s1而不是s2无所谓只要两个集合都遍历全结果一致即可。最后看并集计算。total s1.size() s2.size() - common这个公式很好理解把两个集合的大小加起来交集部分被算了两遍减去一遍就是并集大小。相似度就是common / total。total为0时说明两个集合都为空此时0/0没有数学意义我选择输出1.0即认为两个空文本完全相似这一点你可以根据题面约定自行决定我在后面的防坑章节会展开聊。3.3 用Python实现的对照组简洁但注意输入输出细节如果你更熟悉Python或者想用Python快速验证思路下面这段代码同样能完成任务import sys import re def split_words(text): return re.findall(r[a-zA-Z], text.lower()) line1 sys.stdin.readline().strip() line2 sys.stdin.readline().strip() s1 set(split_words(line1)) s2 set(split_words(line2)) common len(s1 s2) total len(s1 | s2) sim common / total if total 0 else 1.0 print(f{sim * 100:.2f}%)Python的re.findall直接就能把连续字母提取出来text.lower()一键转小写set天然去重代码比C短很多。但CSP正式认证环境中C的编译和运行更为稳定而且大多数培训机构和往年真题解析都以C为主所以我更建议你在考试里使用C版本。Python版本适合在本地做快速原型实验用来验证自己对题意的理解是否正确。4. 高频报错与防坑手册4.1 输出格式翻车百分号与精度是重灾区我见过太多人在最后一步栽跟头。题目要求输出类似“50.00%”的格式有些同学用cout直接输出忘了设置fixed和setprecision结果变成“50%”或者“0.5%”直接判错。用printf的话一定记得写printf(%.2f%%, sim * 100.0)这里有两个百分号第一个是转义输出第二个才是真正的百分号字符。另一点是浮点计算误差。如果你写int common / int total得到的是整数除法结果直接变成0这是毫无疑问的致命错误。必须把common或total先转成double再除C里我习惯(double)common / total这样编译器会把后面的total自动提升为double不会丢精度。Python不存在整数除法的问题但打印时保留两位小数的语法不同也要注意。4.2 空文本与除零一个容易被忽略的边界情况如果两行文本里一个字母都没有比如全是数字和符号那么s1和s2都是空集合total等于0直接除会崩溃或产生未定义行为。处理办法是加一个判断if (total 0) sim 1.0。至于答案是0.00%还是100.00%原题大概率不会给这么极端的用例但你的代码必须要能运行而不崩溃这是基本的健壮性要求。我在实际测试时会把空行、纯数字行、纯标点行都跑一遍确保程序不会在边界输入上崩掉。CSP的隐藏测试点最喜欢在边界做文章你要是能提前做好防御就比很多人稳了一截。4.3 大小写忽略的隐形陷阱题目说忽略大小写意味着“Abc”和“abc”要算同一个单词所以必须把每个单词都转成统一形式。我的做法是在切分过程中边拼边转这样后续无论是插入集合还是比较拿到的都是小写单词。有一种常见的错误写法是先把原始文本按空格拆开再对每个单词做大小写转换最后去重这样做在单词之间只有空格时没问题但遇到“Hello,World”这种逗号分隔的情况就会把“Hello,”当成一个单词最后集合里出现带标点的脏数据相似度计算完全乱套。4.4 测试数据构造技巧手写样例验证每一步写完代码别急着提交先自己构造几个测试用例覆盖不同类型的单词切分和边界情况。我常用的测试集包括普通空格分隔“I love CSP”和“I love coding”大小写混写“CSP csp Csp”和“csp CSP”标点混合“Hello, world; 123”和“hello world”空行纯数字行同一个单词重复多次每跑一个用例在纸上手算一遍预期结果和程序输出做对比。比如“CSP csp Csp”和“csp CSP”这两行切分后第一个集合只有一个单词csp第二个集合也只有一个单词csp交集1并集1相似度100.00%。如果你算出来不是这个结果那说明切分或大小写处理有bug。5. 从这道题延伸出去的备考思路5.1 回到CSP前两题的核心逻辑字符串处理为什么永远不过时CSP认证每年题目风格会有微调但前两题绕不开字符串处理、模拟、简单数学、集合映射这四大类。相似度计算这道题恰好把字符串处理中的切分、归一化和数据结构中的集合运算结合在了一起是一个非常标准的“送分但不送命”的出题方式。它能帮你检验两件事一是你能否读懂题目里每个约束条件的真实含义二是你能否把这些约束快速翻译成STL容器的操作。很多同学备考CSP时一味刷难题觉得前两题太简单不值得花时间。但实践证明前两题丢分的概率一点也不低尤其是第二题题目长度比第一题长描述里的细节多稍不留神就会掉进某个坑。把最近几年的真题前两题拿出来逐题精刷把每种常见坑都踩一遍比盲目刷十道难题有用得多。5.2 类似题型的横向对比集合运算还能怎么考掌握了相似度计算你可以顺手做做这几类变体题一是“两个数组的交集”给定两个整数数组求交集这题本质就是集合运算只是把字符换成了数字二是“不同单词数量统计”给定一篇文章统计不同单词的个数只需要一个set就能解决三是“词频统计”要求输出每个单词出现的次数这时候需要map或unordered_map比set多一维信息。你会发现它们底层的数据结构思维完全一致都是“去重 查询”。这种横向对比的复习方式比单纯背题有效得多。你不需要做大量重复劳动只需要把每道题的考点抽象出来归纳成几个大类再针对每个大类总结出通用的模板代码。比如“字符串切分转小写塞集合”这个组合模板可以套用在至少五道以上历年真题里。5.3 考场上最容易犯的三个低级错误以我自己多年的参赛和辅导经验CSP第二题考生最容易翻车的地方有三个。第一是读题太快没注意到“忽略大小写”和“重复单词只算一次”这两个关键条件导致输出结果完全不符合要求第二是输入读取方式错误用cin 代替getline遇到带空格的文本直接截断第三是浮点输出格式不对要么忘了转double要么忘了输出百分号。这三个错误和算法难度无关纯粹是细心程度的问题只要在提交前逐条自查完全可以避免。我建议你在平时训练时就给自己列一个“提交前检查清单”内容可以包括是否用了getline读取整行、单词是否已转小写、是否用集合去重、并集公式是否写对、输出是否带了两位小数和百分号。考试时把这个清单过一遍基本可以保证不丢冤枉分。5.4 一句话总结这道题的精髓其实这道题想训练的就是两件事把描述性的自然语言翻译成精确的数据结构操作以及用最简单可靠的代码把边界情况都照顾到。CSP认证不追求炫技它只在乎你能不能写出稳定正确的代码。相似度计算作为一道典型的“入门级综合题”非常适合用来检验你的基本功是否扎实。如果你能把这道题的解法背下来并理解透彻那么你对C的getline、tolower、isalpha、unordered_set、printf格式化输出这几个常用工具应该已经有了清晰的把握这些工具在后面更复杂的题目里都会继续用到。多看几道类似真题多写几遍干净利落的代码前两题的分数稳了整场考试的心态也就稳了一半。