PAT乙级乒乓球筐模拟题：计数数组与边界处理实战

1. 从乒乓球筐这个标题说起PAT乙级里被低估的模拟题第一次看到乒乓球筐这个题目名很多人会以为这是一道关于体育器材的简单题甚至有人直接跳过。但如果你刷过PAT乙级题库就会知道这类名字朴素、逻辑绕人的模拟题恰恰是拉开分数差距的关键。它不考高深的算法不涉及动态规划或图论考的是你对循环控制、状态模拟、边界条件的把握能力。说白了它检验的是你能不能把一件日常小事用代码一丝不苟地描述清楚。这道题的核心场景大致是这样的有两个筐分别装着若干乒乓球球上标有字母或数字作为标识。你需要判断第二个筐里的球能否通过某种规则从第一个筐里凑出来或者反过来判断两个筐的球是否满足某种匹配关系。题目看似简单但真正动手写的时候你会发现坑一个接一个输入怎么读、什么时候算匹配成功、多余球怎么处理、空筐怎么办……每一个细节都可能让你的代码在测试点上报WA。这篇文章适合三类人第一类是正在刷PAT乙级、想拿满分的同学第二类是想通过这道题夯实基础模拟能力的编程新手第三类是对字符串处理计数统计这类题型感兴趣、想找一道典型题练手的开发者。我会从题目理解、核心思路、代码实现、踩坑记录到优化扩展完整地拆一遍让你看完就能自己写出稳定AC的版本。2. 题目到底在考什么把生活场景翻译成代码逻辑2.1 乒乓球筐的规则还原先把场景说清楚。假设有两个筐我们叫它们筐A和筐B。每个筐里装着若干个乒乓球每个球上有一个字符标识可能是大写字母、小写字母或数字。题目的要求通常是判断筐B中的球是否都能在筐A中找到对应的球或者判断两个筐的球是否完全一致。这里有一个关键点容易被忽略球是有数量概念的。如果筐A里只有一个标着A的球而筐B里有两个A那就不匹配。很多人第一遍写的时候只检查了字符是否存在忘了统计每个字符出现的次数结果测试点只过了一半。用生活化的类比来说筐A是你的库存筐B是客户的订单。客户要两个A球你库存里只有一个那这单就接不了。题目要你做的就是当一次库存管理员逐项核对数量。2.2 为什么这类题容易丢分PAT乙级的评分机制是测试点全过才得分一个测试点挂了整道题就是0分。而模拟题的特点是边界情况特别多。比如筐是空的怎么办两个筐的球数量不一样但字符集合一样算不算匹配输入里有没有空格要不要处理换行字符范围是只有大写字母还是包含小写字母和数字这些问题在题目描述里往往一笔带过但每一个都对应一个测试点。我见过太多人代码逻辑大方向对了就因为没处理空筐或者大小写敏感的问题反复提交都是WA最后怀疑人生。提示做PAT乙级模拟题第一件事不是写代码而是把题目里的每一句话拆成条件然后逐条问自己如果这种情况出现我的代码会怎么走。2.3 核心考点的技术拆解从技术角度看这道题考的是三个能力的组合第一是输入解析能力。PAT的输入格式有时候很刁钻可能是一行字符串也可能是多行还可能带有不确定的空格。你需要用合适的方式读取不能想当然。第二是计数统计能力。最直接的做法是用一个数组或哈希表记录每个字符出现的次数。字符作为下标次数作为值。这是这类题的标准武器。第三是逻辑判断能力。判断两个计数表是否满足题目要求的关系。是包含关系还是相等关系还是差值不超过某个阈值这取决于题目的具体规则。把这三个能力拆开看每一个都不难。但组合在一起再加上边界条件就成了一道合格的乙级题。3. 我的解题路线从暴力模拟到计数数组3.1 第一版思路暴力查找法我最初的想法很直接遍历筐B的每个球去筐A里找。找到了就拿走标记为已使用找不到就判定失败。这个思路的逻辑是对的但实现起来有个问题如果筐A里的球被标记为已使用下次遍历时要跳过。用数组做标记没问题但每次查找都是O(n)的复杂度两个筐各n个球整体就是O(n²)。对于PAT乙级的数据规模n通常不大O(n²)也能过。但问题是代码写起来容易出错标记数组的初始化、查找时的边界、找到后怎么处理每一步都可能引入bug。我试过用这个方法写结果在一个筐A有重复球的测试点上挂了。原因是我的标记逻辑写错了同一个球被用了两次。后来我意识到与其在查找上纠结不如换个角度直接统计每个字符的数量。3.2 第二版思路计数数组法计数数组的思路非常干净开一个大小为256的整型数组覆盖所有ASCII字符遍历筐A遇到一个字符就把对应位置加1再遍历筐B遇到一个字符就把对应位置减1。最后检查数组里有没有负数——如果有说明筐B里某个字符的数量超过了筐A不匹配。这个方法的复杂度是O(n)代码量少逻辑清晰而且天然处理了重复球的问题。因为它不关心球的位置只关心数量。用代码表示大概是这样int count[256] {0}; for (int i 0; a[i]; i) { count[(int)a[i]]; } for (int i 0; b[i]; i) { count[(int)b[i]]--; if (count[(int)b[i]] 0) { // 不匹配 } }这段代码的精髓在于用空间换时间用计数代替查找。你不需要知道球在哪里只需要知道有多少个。3.3 为什么最终选了计数法而不是排序法有人可能会想到另一种思路把两个筐的球分别排序然后逐个比较。这个方法也能做但有两个缺点一是排序本身有O(n log n)的开销虽然不大但没必要二是排序后比较的逻辑要处理长度不等的情况代码反而更绕。计数法的优势在于它把比较这个动作转化成了加减这个动作。你不需要写任何比较逻辑只需要在最后检查有没有负数。这种用数据结构的性质代替显式逻辑的思路在模拟题里非常常见值得刻意练习。4. 代码实现细节那些题目没说但你必须处理的坑4.1 输入读取别想当然地用scanfPAT的输入有时候会给你惊喜。比如题目说输入两个字符串但实际测试数据里可能包含空格或者字符串长度不确定。如果你用scanf(%s, buf)遇到空格就截断了后面的内容全乱套。我的建议是先看清楚题目对输入的描述。如果明确说是两个字符串不含空格那用scanf没问题。如果没说或者你发现测试点过不去就换成fgets或getline把整行读进来再处理。还有一个细节fgets会把换行符也读进来。如果你不处理换行符会被当成一个字符参与计数导致结果错误。处理方法是读完之后把末尾的\n替换成\0。fgets(a, sizeof(a), stdin); int len strlen(a); if (len 0 a[len-1] \n) { a[len-1] \0; }这段代码看起来简单但我见过至少三个人因为忘了处理换行符而WA。4.2 字符范围256够不够用256大小的数组是因为ASCII字符的范围是0到255。但这里有个前提题目里的字符必须是ASCII字符。如果题目涉及中文字符或者Unicode256就不够了。不过PAT乙级的题目基本不会涉及这些所以256是安全的。但要注意char类型在某些平台上是有符号的。如果字符的值超过127作为数组下标时会变成负数导致越界。保险的做法是在索引时强制转换成unsigned charcount[(unsigned char)a[i]];这个细节平时不会出问题但一旦出问题就是段错误很难查。4.3 判断逻辑什么时候算匹配成功这是整道题最核心的判断。根据题目的具体规则可能有几种情况题目规则判断条件实现方式筐B的球筐A都有计数数组无负数遍历B时减减到负数即失败两筐球完全一致计数数组全为零先加A再减B最后检查全零筐A的球筐B都有计数数组无正数遍历A时加遍历B时减检查正数我遇到过的变体是判断筐B能否由筐A通过某种变换得到这时候判断条件会更复杂但核心还是计数。注意判断的时机很重要。如果你在遍历B的过程中就检查负数可以提前退出节省时间。但如果题目要求必须读完所有输入那就得老老实实读完再判断。4.4 完整代码框架把上面的细节拼起来一个稳健的版本大概长这样#include stdio.h #include string.h int main() { char a[1005], b[1005]; int count[256] {0}; // 读取输入处理换行符 if (fgets(a, sizeof(a), stdin) NULL) return 0; int la strlen(a); if (la 0 a[la-1] \n) a[la-1] \0; if (fgets(b, sizeof(b), stdin) NULL) return 0; int lb strlen(b); if (lb 0 b[lb-1] \n) b[lb-1] \0; // 统计筐A for (int i 0; a[i]; i) { count[(unsigned char)a[i]]; } // 核对筐B int ok 1; for (int i 0; b[i]; i) { count[(unsigned char)b[i]]--; if (count[(unsigned char)b[i]] 0) { ok 0; break; } } // 输出结果 if (ok) { printf(Yes\n); } else { printf(No\n); } return 0; }这段代码不长但每一行都有它的作用。数组大小1005是经验值比题目可能的最大长度稍大一点留出余量。unsigned char的转换是为了防止下标越界。提前break是为了效率虽然乙级题的数据量不大但养成习惯没坏处。5. 踩坑实录我在这道题上栽过的跟头5.1 第一个坑忘了处理空字符串有一次我提交代码其他测试点都过了就一个测试点WA。我反复检查逻辑怎么看都没问题。后来我把输入改成空字符串试了一下发现程序直接崩溃了——因为fgets读到空行时strlen返回0后面的循环虽然不会执行但如果我在循环里访问了a[0]就会读到\0逻辑上没问题但输出格式可能不对。更隐蔽的情况是题目可能给一个空筐另一个筐有球。这时候计数数组全是0遍历B时第一个球就减成负数输出No。逻辑上是对的但如果题目期望的是Yes比如空筐被认为可以匹配任何筐那就错了。教训空输入不是边界情况是必须处理的正常情况。写代码时先问自己如果输入是空的我的代码会怎么走5.2 第二个坑大小写敏感问题题目里的球可能标着大写字母也可能标着小写字母。如果你用count[A]和count[a]它们在ASCII表里是不同的位置不会互相干扰。但如果你在某个地方做了大小写转换比如用tolower就会把两个不同的球当成同一个。我犯过的错误是在读取输入时习惯性地用了tolower结果把A和a混在一起导致计数错误。后来我把转换去掉问题就解决了。教训除非题目明确说不区分大小写否则一律按原样处理。不要自作聪明地做归一化。5.3 第三个坑输出格式的细节PAT的题目对输出格式要求很严格。有时候是Yes和No有时候是YES和NO有时候还要输出具体数量。我见过有人因为输出多了一个空格或者少了一个换行而WA。这道题如果输出的是Yes/No注意首字母大写末尾有换行。如果你用printf(Yes)而不加\n有些评测系统会判错。教训输出格式照抄题目描述一个字符都不要改。不确定的时候把题目里的输出示例复制下来对比。5.4 第四个坑数组越界这个问题最隐蔽。如果你的数组大小是1000而输入字符串长度正好是1000那么fgets会读入999个字符加一个\0看起来没问题。但如果输入长度是1001fgets只会读1000个字符包括\0剩下的留在缓冲区里影响下一次读取。更危险的是如果你在循环里用i strlen(a)而不是i strlen(a)就会访问到a[len]也就是\0的位置。虽然\0的计数不影响结果但如果数组刚好在边界上就可能越界。教训数组大小永远比题目给的最大长度大一点。循环条件用而不是。这些是基本功但紧张的时候容易忘。6. 从AC到举一反三这类题的通用套路6.1 计数数组的适用场景计数数组是模拟题里的万能工具。只要题目涉及判断两个集合是否满足某种数量关系就可以考虑用它。常见的变体包括判断两个字符串是否为变位词anagram判断一个字符串能否由另一个字符串的字符重新排列得到统计字符频率找出出现次数最多/最少的字符判断两个集合的差集、交集、并集这些题的核心逻辑都是一样的用数组下标表示元素用数组值表示数量。掌握了这个套路一类题就都能做了。6.2 什么时候不该用计数数组计数数组不是万能的。如果元素的取值范围很大比如整数范围是-10^9到10^9开数组就不现实了。这时候要用哈希表C的unordered_mapPython的dict。另一个限制是计数数组只能统计可枚举的元素。如果元素是自定义对象没法直接作为下标就得换方法。在PAT乙级里字符是最常见的统计对象所以计数数组几乎无处不在。但到了甲级或者更高级的题目哈希表会更常用。6.3 模拟题的通用解题框架刷多了模拟题我总结出一个通用的解题框架第一步把题目翻译成状态和操作。状态是什么操作是什么操作如何改变状态第二步确定数据结构的选型。是用数组、哈希表、栈、队列还是直接用变量选型的依据是操作的类型和数据的规模。第三步处理边界条件。空输入、最大输入、特殊字符、格式要求逐条检查。第四步写代码并测试。先写核心逻辑再补边界处理。测试时至少覆盖正常情况、空情况、边界情况、题目给的示例。这个框架看起来简单但真正做题时能坚持走完这四步的人不多。大多数人都是拿到题就开始写写到一半发现逻辑不对再回头改浪费时间还容易出错。7. 进阶思考如果题目变难了怎么办7.1 变体一加入交换操作如果题目改成你可以交换筐A中任意两个球的位置判断能否让两个筐匹配那计数法的思路就不够了。你需要先判断两个筐的字符集合是否一致再判断是否可以通过交换达到目标。这其实就变成了判断两个字符串是否为变位词的问题计数法依然适用但判断条件变成了计数数组全为零。7.2 变体二加入重量或优先级如果每个球除了字符标识还有一个重量值题目要求在匹配字符的同时总重量不能超过某个阈值那就变成了一个带约束的匹配问题。这时候可能需要用到贪心或者动态规划。不过这种难度已经超出乙级范围了属于甲级或更高级的题目。7.3 变体三多个筐的匹配如果有三个或更多筐要求判断它们之间是否满足某种传递关系那就需要用图或者并查集来建模。这种变体在乙级里不常见但了解一下没坏处。我想说的是一道题的价值不在于它本身而在于它背后的模式。乒乓球筐这道题表面上是判断两个筐的球是否匹配本质上是计数比较这个模式。掌握了这个模式你就能解决一大类问题。8. 一些实战建议和收尾刷PAT乙级的过程中我最大的体会是不要轻视任何一道简单题。乒乓球筐这种题看起来就是统计字符数量但真正写的时候输入处理、边界条件、输出格式每一个环节都可能出问题。而那些看起来很难的题比如涉及图论或动态规划的反而因为思路明确写起来更顺。另一个建议是每道题做完之后把踩过的坑记下来。不用写得很正式就在代码旁边加个注释或者在自己的笔记里写一行。下次遇到类似的题翻一下笔记能省很多时间。我自己的笔记里光输入处理这一项就记了七八条每一条都是血泪教训。最后说一个具体的技巧提交之前用题目给的示例数据跑一遍再自己造两组边界数据跑一遍。示例数据是题目保证能过的但边界数据才是真正拉开差距的地方。空输入、最大长度、特殊字符这三类数据各造一组能过就基本稳了。至于这道题的代码上面已经给了完整的框架。你可以直接拿去用但建议自己先写一遍再对比。看别人写的代码和自己写出来是两回事。自己写的时候卡住了再看别人的那个卡住的点就是你真正学到的东西。