1. 从“奇偶组合”到“真爱99”PAT乙级春季考试算法实战全解析最近有不少朋友在准备PAT乙级的考试尤其是春季这场题目出的挺有意思既有数学味道又考验编程基本功。我刷完这几道题感觉它们像是一套精心设计的“思维体操”从简单的奇偶性判断到需要一点巧思的数字特性分析再到实际场景的模拟层层递进。今天我就结合自己的解题经验和大家聊聊这几道题背后的门道特别是怎么把题目里那些看似复杂的条件转化成我们代码里清晰、高效的逻辑。我会尽量用大白话把思路讲清楚就算你算法基础一般跟着走一遍也能明白。很多人一看到“n个不同的正偶数”和“m个不同的正奇数”要凑2024第一反应可能就是去模拟组合但这在考场上时间肯定不够而且n和m最大能到1000暴力搜索根本不现实。这道题的精髓在于“正难则反”——我们不去想怎么“能”组成而是去思考什么情况下“不能”组成。一旦转换思路问题就变得清晰多了。同样后面那道“真爱99”数题目描述看起来有点绕什么从左往右、从右往左每两位断开求和但核心其实就是对一个超大数字进行特定规则的分割和取模运算考验的是我们对字符串处理的熟练度以及对取模运算性质的理解。咱们就从第一题开始一步步拆解。2. B-1 奇偶组合数学思维如何秒杀编程题2.1 题目重述与第一层思考题目很简单给你K组测试数据每组给两个数n和m。问是否存在n个互不相同的正偶数以及m个互不相同的正奇数它们的和恰好等于2024。我第一眼看到这个题心里想的是“这不就是找两个等差数列求和吗” 正偶数序列是2, 4, 6, 8...正奇数序列是1, 3, 5, 7...。要让它们互不相同我们肯定从最小的开始取这样总和才能最小也最有可能不超过2024。所以n个最小的不同正偶数和就是 2 4 ... 2n这是一个等差数列求和公式是(首项末项)*项数/2也就是(2 2n) * n / 2 n*(n1)。同理m个最小的不同正奇数和是 1 3 ... (2m-1)求和公式是(1 2m-1) * m / 2 m*m。所以一个最直接的必要条件是n*(n1) m*m 2024。如果连最小的和都大于2024那肯定没戏。这是解题的第一个关键点很多朋友都能想到。2.2 容易被忽略的“奇偶性”陷阱但光有这个条件就够了吗我一开始也以为够了直到我试了几个例子。比如 n1, m1。最小和是 12 11 3远小于2024那是不是就能组成呢我们试试看一个正偶数是2一个正奇数是1和是3。我们当然可以通过选更大的偶数比如1000和更大的奇数比如1024来凑2024看起来似乎可行。但是这里藏着一个致命的陷阱题目要求的是n个偶数和m个奇数的和是2024。2024是个偶数。n个偶数的和不管你怎么选一定是偶数因为偶数偶数偶数。那么要让总和是偶数剩下的m个奇数的和也必须是个偶数才行因为偶数偶数偶数偶数奇数奇数。m个奇数的和是什么性质奇数个奇数相加结果是奇数偶数个奇数相加结果是偶数。所以m必须是一个偶数这样m个奇数的和才是偶数才能和偶数的和相加得到偶数2024。这是一个非常漂亮的纯数学约束它直接过滤掉了一半无效的输入。很多同学在考场上可能因为时间紧张只想到了最小和的条件而漏掉了这个奇偶性条件导致丢分。在实际写代码时我们应该先判断这个条件因为它计算量极小可以快速排除大量情况。2.3 代码实现与边界处理想通了这两个条件代码就非常简单了。我们只需要对每一组输入的n和m判断m是否为偶数。如果不是直接输出no。如果m是偶数再计算n*(n1) m*m是否小于等于2024。如果是输出yes否则输出no。这里有个小细节题目要求输出yes和no并且注意最后一行的输出末尾不要换行虽然有些评测系统可能不严格检查这个但养成好习惯很重要。下面是我用Java写的参考代码逻辑非常清晰import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int K scanner.nextInt(); while (K-- 0) { int n scanner.nextInt(); int m scanner.nextInt(); // 条件1: 奇数必须为偶数个其和才能为偶数 if (m % 2 ! 0) { System.out.print(no); } else { // 条件2: 最小可能和不能超过目标值 // n个最小不同偶数和 n*(n1) // m个最小不同奇数和 m*m long minSum (long) n * (n 1) (long) m * m; if (minSum 2024) { System.out.print(yes); } else { System.out.print(no); } } // 如果不是最后一行就输出换行 if (K 0) { System.out.println(); } } scanner.close(); } }我特别把minSum的计算用long类型来存因为当n和m接近1000时n*(n1)会超过一百万加上m*m也很大用int可能会溢出。虽然2024这个目标值不大但养成防止溢出的习惯对编程竞赛很重要。这道题给我的启发是有些算法题的本质是数学题找到那个关键的数学约束往往比写复杂的循环和搜索要高效得多。3. B-2 “真爱99”数玩转大数取模与字符串技巧3.1 理解“双向断开”的规则这道题的描述需要多读几遍。它首先介绍了一个已知的规律一个数N除以99的余数r可以通过“从右向左”每两位断开求和再除以99来得到。例如12345从右向左断开是1、23、45求和是6912345 % 99确实等于69。而“从左向右”断开12, 34, 5求和是51就不对。然后题目说有些数字很特别无论你从左向右断还是从右向左断按照这个“两位一断、求和、取模”的方法得到的结果都一样。这种数就叫“真爱99”数。题目还提示所有偶数位数比如2位、4位、6位的数字都满足这个性质。现在要我们判断那些奇数位数的数字里哪些也是“真爱99”数。这题的关键在于我们不需要去理解这个规律为什么成立当然背后是模运算的分配律我们只需要严格按照题目描述的算法对一个给定的数字字符串进行两次计算然后比较结果是否相等。输入的数字N可以非常大10的1000次方所以我们必须用字符串来处理绝不能转换成整数。3.2 算法步骤拆解与实现对于每一个输入的数字字符串str我们需要做两件事从左向右断开计算余数从索引0开始每次取2个字符str.substring(i, i2)转换成整数累加到总和leftToRight中并且每次累加后立即对99取模防止溢出虽然这里用int也够但立即取模是好习惯。如果字符串长度是奇数最后会剩下一个单独的字符需要单独处理。从右向左断开计算余数从字符串末尾开始每次向左取2个字符str.substring(i-1, i1)。同样如果长度是奇数最左边会剩下一个单独的字符。判断两个余数是否相等即可。注意题目说了所有偶数长度的字符串直接就是“真爱99”数所以我们可以先判断长度如果是偶数直接输出yes能节省一半的计算量。下面是我的实现代码我加了详细的注释import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n Integer.parseInt(scanner.nextLine()); // 读取行数 for (int i 0; i n; i) { String numStr scanner.nextLine(); int len numStr.length(); // 规则1偶数位数字一定是“真爱99” if (len % 2 0) { System.out.println(yes); continue; } int leftSum 0, rightSum 0; // 从左到右处理 for (int j 0; j len - 1; j 2) { // 取两位数字 int twoDigit Integer.parseInt(numStr.substring(j, j 2)); leftSum (leftSum twoDigit) % 99; } // 处理最后剩下的一位因为长度是奇数 leftSum (leftSum (numStr.charAt(len - 1) - 0)) % 99; // 从右到左处理 for (int j len - 1; j 1; j - 2) { // 取两位数字注意下标 int twoDigit Integer.parseInt(numStr.substring(j - 1, j 1)); rightSum (rightSum twoDigit) % 99; } // 处理最前面剩下的一位 rightSum (rightSum (numStr.charAt(0) - 0)) % 99; // 比较结果 if (leftSum rightSum) { System.out.println(yes); } else { System.out.println(no); } } scanner.close(); } }在实现从右向左断开时下标处理要小心很容易出StringIndexOutOfBoundsException。我的循环从len-1开始每次减2确保j-1是有效的。这道题锻炼了我们细心处理字符串边界的能力以及对模运算“边加边模”特性的运用。4. B-3 与 B-4空间优化与模式识别的实战4.1 B-3 单词存储寻找最大值的简单艺术第三题题目很长但意思很简单有n个单词我们要用定长的数组来存它们像C语言的字符数组末尾有\0结束符。每个数组的长度必须一样问这个统一的长度最少是多少以及总共需要多少字节的存储空间。举个例子单词“pat”长度3加上结束符需要4字节“test”长度4需要5字节。为了让定长数组能存下最长的单词数组长度必须等于最长单词长度 1。那么总空间就是n * (最长单词长度 1)字节。这题可能是整套试卷里最简单的就是一次遍历找最大值。但千万别小看它它在考察我们的阅读理解能力和基础编码稳定性。题目明确说了字符串只有小写字母以回车结尾这避免了空格处理的麻烦。我们只需要在读取每个单词时更新记录的最大长度即可。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n Integer.parseInt(scanner.nextLine()); // 单词个数 int maxLen 0; for (int i 0; i n; i) { String word scanner.nextLine(); if (word.length() maxLen) { maxLen word.length(); } } int arrayLen maxLen 1; // 每个数组需要的长度 long totalSpace (long) n * arrayLen; // 总空间注意用long防溢出 System.out.println(arrayLen totalSpace); scanner.close(); } }这里唯一要注意的是数据范围。n最大是10^5maxLen最大可能也是10^5虽然单词不太可能这么长那么n * arrayLen最大可能是10^10超过了int的范围约21亿所以要用long类型来计算总空间。题目说输出不会超过10^8那是基于测试数据但我们自己写代码要保证健壮性。4.2 B-4 盲文数字识别将图像映射为编码的巧思第四题很有意思是一个简单的图像模式识别问题。给我们一个N行M列的网格每个格子是*凸起或.未凸起。盲文数字用一个3行2列的点阵表示题目给了0-9的图案。我们需要在整个大网格中找出所有符合这些3x2小图案的区域并统计每个数字出现了多少次。关键点1重叠计算。题目明确说了图案可以重叠。比如样例里那个****和....组成的重叠区域要算作3个“3”。这意味着我们不能用一个“匹配即标记”的方法而是要对网格中每一个可能的3行2列的起始位置(i, j)都将其视为一个独立的盲文单元进行判断。关键点2如何高效判断一个3x2区域是哪个数字最笨的办法是把0-9的图案模板存下来然后逐个像素比较。但这样代码会很长容易写错。题目给出的满分代码用了一个非常聪明的方法编码法。它把3行2列的6个点按照一个固定的顺序比如左上、右上、左中、右中、左下、右下看作一个6位的二进制数。如果该点是*对应位就是1否则是0。这样每个盲文数字就对应一个唯一的6位二进制数进而可以转换成一个十进制整数。例如数字“1”的图案只有左上角一个点对应的二进制是000001十进制就是1。数字“2”可能是000101十进制是5。在代码里作者用了一个HashMap来建立这个十进制编码到实际数字的映射。这样在遍历网格时对于每个起始位置(i, j)我们只需要查看这6个点的状态生成一个编码temp然后去HashMap里查一下。如果能查到就说明匹配到了一个数字给对应的计数器加一。// 核心的编码生成逻辑假设(i,j)是左上角起点 int temp 0; if (grid[i][j] *) temp 1; // 位0: 左上 if (grid[i][j1] *) temp 10; // 位1: 右上 (权重10) if (grid[i1][j] *) temp 100; // 位2: 左中 (权重100) if (grid[i1][j1] *) temp 1000; // 位3: 右中 if (grid[i2][j] *) temp 10000;// 位4: 左下 if (grid[i2][j1] *) temp 100000;//位5: 右下 // 然后 map.get(temp) 就能得到对应的数字0-9这个方法的妙处在于它将一个二维的模式匹配问题转化成了一维的整数查找问题效率极高代码也简洁。我们不需要关心具体的图案长什么样只需要根据题目给出的图案事先建立好编码映射表就行。这提醒我们在处理有固定模式的识别问题时可以尝试将其“特征化”为一个简单的值或编码。5. B-5 能力评估报告综合排序与条件筛选5.1 理解中位线与反馈分类最后一题是数据统计和处理的综合题场景是模拟一个考试系统的能力评估报告生成。题目给了N个考生每个考生有5个维度的分数。我们需要先为每个维度计算一个“中位线”。这里的中位线不是中位数而是从大到小排序后第(N1)/2N为奇数或第N/2N为偶数个值。这其实就是统计学里的“下中位数”或者说“第50百分位数”的一种定义。计算完5个维度的中位线值(m1, m2, m3, m4, m5)后对于每一个被查询的考生我们将他的每个维度分数vi与对应的中位线mi比较。如果vi mi则该维度属于“正向反馈类”否则属于“负向反馈类”。5.2 输出格式的复杂排序规则题目要求的输出格式是本题最大的难点。它要求我们把5个维度的编号1到5按特定规则输出在一行。先输出正向反馈类的维度编号按(vi - mi)的差值非递增即从大到小排序。如果差值相同则按维度编号递增从小到大排序。再输出负向反馈类的维度编号按(mi - vi)的差值非递减即从小到大排序。同样差值相同则按编号递增排序。并且每个负向反馈的编号前要加一个负号-。举个例子假设一个考生的比较结果是维度1和3正向差值分别为5和3维度2、4、5负向差值分别为214。那么输出顺序是先排正向的1和3因为差值53所以顺序是1 3。再排负向的2、4、5按(mi-vi)从小到大排是4(差1)2(差2)5(差4)所以最终输出是1 3 -4 -2 -5。5.3 实现策略与性能考量思路很直接但实现起来要注意细节和性能。N和M最大都是10^5如果对每个查询考生都重新计算中位线或者进行低效的查找很容易超时。高效的做法分三步数据读取与存储一次读取所有考生数据将准考证号和五个分数存储起来可以用HashMapString, int[]。同时将五个维度的分数分别存入5个独立的列表如ListInteger score1, score2, ...。计算中位线分别对5个分数列表进行从大到小排序。然后根据N的奇偶性取出对应位置的元素作为中位线值m1~m5。处理查询对于每个查询的准考证号快速从HashMap中取出其分数数组。然后创建一个大小为5的列表每个元素记录维度编号和差值(vi-mi)。接着根据差值的正负我们可以自然地将维度分为正向和负向两类。对正向列表按规则排序差值降序编号升序对负向列表也按规则排序mi-vi的差值升序编号升序。最后按顺序输出即可。这里排序规则的实现可以通过自定义一个Pair类或者使用int[][]并实现Comparator接口来完成。下面是一个简化的核心逻辑片段// 假设有一个Listint[] posList (存储[维度编号, vi-mi]) 和 negList (存储[维度编号, mi-vi]) // 正向排序 Collections.sort(posList, (a, b) - { if (a[1] ! b[1]) return b[1] - a[1]; // 差值降序 else return a[0] - b[0]; // 编号升序 }); // 负向排序 Collections.sort(negList, (a, b) - { if (a[1] ! b[1]) return a[1] - b[1]; // 差值升序 else return a[0] - b[0]; // 编号升序 }); // 输出 for (int[] p : posList) System.out.print(p[0] ); for (int[] n : negList) System.out.print(- n[0] );这道题综合考察了排序、查找、条件判断和自定义排序规则是PAT乙级中比较典型的“描述复杂但思路清晰”的题目。只要耐心把题目要求翻译成代码逻辑一步步实现就能拿分。它模拟了实际数据处理中的一个常见场景基于统计基准如中位数对个体进行多维度的评估和分类报告。
PAT乙级2024春季考试：奇偶组合与数字特性的算法实战
1. 从“奇偶组合”到“真爱99”PAT乙级春季考试算法实战全解析最近有不少朋友在准备PAT乙级的考试尤其是春季这场题目出的挺有意思既有数学味道又考验编程基本功。我刷完这几道题感觉它们像是一套精心设计的“思维体操”从简单的奇偶性判断到需要一点巧思的数字特性分析再到实际场景的模拟层层递进。今天我就结合自己的解题经验和大家聊聊这几道题背后的门道特别是怎么把题目里那些看似复杂的条件转化成我们代码里清晰、高效的逻辑。我会尽量用大白话把思路讲清楚就算你算法基础一般跟着走一遍也能明白。很多人一看到“n个不同的正偶数”和“m个不同的正奇数”要凑2024第一反应可能就是去模拟组合但这在考场上时间肯定不够而且n和m最大能到1000暴力搜索根本不现实。这道题的精髓在于“正难则反”——我们不去想怎么“能”组成而是去思考什么情况下“不能”组成。一旦转换思路问题就变得清晰多了。同样后面那道“真爱99”数题目描述看起来有点绕什么从左往右、从右往左每两位断开求和但核心其实就是对一个超大数字进行特定规则的分割和取模运算考验的是我们对字符串处理的熟练度以及对取模运算性质的理解。咱们就从第一题开始一步步拆解。2. B-1 奇偶组合数学思维如何秒杀编程题2.1 题目重述与第一层思考题目很简单给你K组测试数据每组给两个数n和m。问是否存在n个互不相同的正偶数以及m个互不相同的正奇数它们的和恰好等于2024。我第一眼看到这个题心里想的是“这不就是找两个等差数列求和吗” 正偶数序列是2, 4, 6, 8...正奇数序列是1, 3, 5, 7...。要让它们互不相同我们肯定从最小的开始取这样总和才能最小也最有可能不超过2024。所以n个最小的不同正偶数和就是 2 4 ... 2n这是一个等差数列求和公式是(首项末项)*项数/2也就是(2 2n) * n / 2 n*(n1)。同理m个最小的不同正奇数和是 1 3 ... (2m-1)求和公式是(1 2m-1) * m / 2 m*m。所以一个最直接的必要条件是n*(n1) m*m 2024。如果连最小的和都大于2024那肯定没戏。这是解题的第一个关键点很多朋友都能想到。2.2 容易被忽略的“奇偶性”陷阱但光有这个条件就够了吗我一开始也以为够了直到我试了几个例子。比如 n1, m1。最小和是 12 11 3远小于2024那是不是就能组成呢我们试试看一个正偶数是2一个正奇数是1和是3。我们当然可以通过选更大的偶数比如1000和更大的奇数比如1024来凑2024看起来似乎可行。但是这里藏着一个致命的陷阱题目要求的是n个偶数和m个奇数的和是2024。2024是个偶数。n个偶数的和不管你怎么选一定是偶数因为偶数偶数偶数。那么要让总和是偶数剩下的m个奇数的和也必须是个偶数才行因为偶数偶数偶数偶数奇数奇数。m个奇数的和是什么性质奇数个奇数相加结果是奇数偶数个奇数相加结果是偶数。所以m必须是一个偶数这样m个奇数的和才是偶数才能和偶数的和相加得到偶数2024。这是一个非常漂亮的纯数学约束它直接过滤掉了一半无效的输入。很多同学在考场上可能因为时间紧张只想到了最小和的条件而漏掉了这个奇偶性条件导致丢分。在实际写代码时我们应该先判断这个条件因为它计算量极小可以快速排除大量情况。2.3 代码实现与边界处理想通了这两个条件代码就非常简单了。我们只需要对每一组输入的n和m判断m是否为偶数。如果不是直接输出no。如果m是偶数再计算n*(n1) m*m是否小于等于2024。如果是输出yes否则输出no。这里有个小细节题目要求输出yes和no并且注意最后一行的输出末尾不要换行虽然有些评测系统可能不严格检查这个但养成好习惯很重要。下面是我用Java写的参考代码逻辑非常清晰import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int K scanner.nextInt(); while (K-- 0) { int n scanner.nextInt(); int m scanner.nextInt(); // 条件1: 奇数必须为偶数个其和才能为偶数 if (m % 2 ! 0) { System.out.print(no); } else { // 条件2: 最小可能和不能超过目标值 // n个最小不同偶数和 n*(n1) // m个最小不同奇数和 m*m long minSum (long) n * (n 1) (long) m * m; if (minSum 2024) { System.out.print(yes); } else { System.out.print(no); } } // 如果不是最后一行就输出换行 if (K 0) { System.out.println(); } } scanner.close(); } }我特别把minSum的计算用long类型来存因为当n和m接近1000时n*(n1)会超过一百万加上m*m也很大用int可能会溢出。虽然2024这个目标值不大但养成防止溢出的习惯对编程竞赛很重要。这道题给我的启发是有些算法题的本质是数学题找到那个关键的数学约束往往比写复杂的循环和搜索要高效得多。3. B-2 “真爱99”数玩转大数取模与字符串技巧3.1 理解“双向断开”的规则这道题的描述需要多读几遍。它首先介绍了一个已知的规律一个数N除以99的余数r可以通过“从右向左”每两位断开求和再除以99来得到。例如12345从右向左断开是1、23、45求和是6912345 % 99确实等于69。而“从左向右”断开12, 34, 5求和是51就不对。然后题目说有些数字很特别无论你从左向右断还是从右向左断按照这个“两位一断、求和、取模”的方法得到的结果都一样。这种数就叫“真爱99”数。题目还提示所有偶数位数比如2位、4位、6位的数字都满足这个性质。现在要我们判断那些奇数位数的数字里哪些也是“真爱99”数。这题的关键在于我们不需要去理解这个规律为什么成立当然背后是模运算的分配律我们只需要严格按照题目描述的算法对一个给定的数字字符串进行两次计算然后比较结果是否相等。输入的数字N可以非常大10的1000次方所以我们必须用字符串来处理绝不能转换成整数。3.2 算法步骤拆解与实现对于每一个输入的数字字符串str我们需要做两件事从左向右断开计算余数从索引0开始每次取2个字符str.substring(i, i2)转换成整数累加到总和leftToRight中并且每次累加后立即对99取模防止溢出虽然这里用int也够但立即取模是好习惯。如果字符串长度是奇数最后会剩下一个单独的字符需要单独处理。从右向左断开计算余数从字符串末尾开始每次向左取2个字符str.substring(i-1, i1)。同样如果长度是奇数最左边会剩下一个单独的字符。判断两个余数是否相等即可。注意题目说了所有偶数长度的字符串直接就是“真爱99”数所以我们可以先判断长度如果是偶数直接输出yes能节省一半的计算量。下面是我的实现代码我加了详细的注释import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n Integer.parseInt(scanner.nextLine()); // 读取行数 for (int i 0; i n; i) { String numStr scanner.nextLine(); int len numStr.length(); // 规则1偶数位数字一定是“真爱99” if (len % 2 0) { System.out.println(yes); continue; } int leftSum 0, rightSum 0; // 从左到右处理 for (int j 0; j len - 1; j 2) { // 取两位数字 int twoDigit Integer.parseInt(numStr.substring(j, j 2)); leftSum (leftSum twoDigit) % 99; } // 处理最后剩下的一位因为长度是奇数 leftSum (leftSum (numStr.charAt(len - 1) - 0)) % 99; // 从右到左处理 for (int j len - 1; j 1; j - 2) { // 取两位数字注意下标 int twoDigit Integer.parseInt(numStr.substring(j - 1, j 1)); rightSum (rightSum twoDigit) % 99; } // 处理最前面剩下的一位 rightSum (rightSum (numStr.charAt(0) - 0)) % 99; // 比较结果 if (leftSum rightSum) { System.out.println(yes); } else { System.out.println(no); } } scanner.close(); } }在实现从右向左断开时下标处理要小心很容易出StringIndexOutOfBoundsException。我的循环从len-1开始每次减2确保j-1是有效的。这道题锻炼了我们细心处理字符串边界的能力以及对模运算“边加边模”特性的运用。4. B-3 与 B-4空间优化与模式识别的实战4.1 B-3 单词存储寻找最大值的简单艺术第三题题目很长但意思很简单有n个单词我们要用定长的数组来存它们像C语言的字符数组末尾有\0结束符。每个数组的长度必须一样问这个统一的长度最少是多少以及总共需要多少字节的存储空间。举个例子单词“pat”长度3加上结束符需要4字节“test”长度4需要5字节。为了让定长数组能存下最长的单词数组长度必须等于最长单词长度 1。那么总空间就是n * (最长单词长度 1)字节。这题可能是整套试卷里最简单的就是一次遍历找最大值。但千万别小看它它在考察我们的阅读理解能力和基础编码稳定性。题目明确说了字符串只有小写字母以回车结尾这避免了空格处理的麻烦。我们只需要在读取每个单词时更新记录的最大长度即可。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n Integer.parseInt(scanner.nextLine()); // 单词个数 int maxLen 0; for (int i 0; i n; i) { String word scanner.nextLine(); if (word.length() maxLen) { maxLen word.length(); } } int arrayLen maxLen 1; // 每个数组需要的长度 long totalSpace (long) n * arrayLen; // 总空间注意用long防溢出 System.out.println(arrayLen totalSpace); scanner.close(); } }这里唯一要注意的是数据范围。n最大是10^5maxLen最大可能也是10^5虽然单词不太可能这么长那么n * arrayLen最大可能是10^10超过了int的范围约21亿所以要用long类型来计算总空间。题目说输出不会超过10^8那是基于测试数据但我们自己写代码要保证健壮性。4.2 B-4 盲文数字识别将图像映射为编码的巧思第四题很有意思是一个简单的图像模式识别问题。给我们一个N行M列的网格每个格子是*凸起或.未凸起。盲文数字用一个3行2列的点阵表示题目给了0-9的图案。我们需要在整个大网格中找出所有符合这些3x2小图案的区域并统计每个数字出现了多少次。关键点1重叠计算。题目明确说了图案可以重叠。比如样例里那个****和....组成的重叠区域要算作3个“3”。这意味着我们不能用一个“匹配即标记”的方法而是要对网格中每一个可能的3行2列的起始位置(i, j)都将其视为一个独立的盲文单元进行判断。关键点2如何高效判断一个3x2区域是哪个数字最笨的办法是把0-9的图案模板存下来然后逐个像素比较。但这样代码会很长容易写错。题目给出的满分代码用了一个非常聪明的方法编码法。它把3行2列的6个点按照一个固定的顺序比如左上、右上、左中、右中、左下、右下看作一个6位的二进制数。如果该点是*对应位就是1否则是0。这样每个盲文数字就对应一个唯一的6位二进制数进而可以转换成一个十进制整数。例如数字“1”的图案只有左上角一个点对应的二进制是000001十进制就是1。数字“2”可能是000101十进制是5。在代码里作者用了一个HashMap来建立这个十进制编码到实际数字的映射。这样在遍历网格时对于每个起始位置(i, j)我们只需要查看这6个点的状态生成一个编码temp然后去HashMap里查一下。如果能查到就说明匹配到了一个数字给对应的计数器加一。// 核心的编码生成逻辑假设(i,j)是左上角起点 int temp 0; if (grid[i][j] *) temp 1; // 位0: 左上 if (grid[i][j1] *) temp 10; // 位1: 右上 (权重10) if (grid[i1][j] *) temp 100; // 位2: 左中 (权重100) if (grid[i1][j1] *) temp 1000; // 位3: 右中 if (grid[i2][j] *) temp 10000;// 位4: 左下 if (grid[i2][j1] *) temp 100000;//位5: 右下 // 然后 map.get(temp) 就能得到对应的数字0-9这个方法的妙处在于它将一个二维的模式匹配问题转化成了一维的整数查找问题效率极高代码也简洁。我们不需要关心具体的图案长什么样只需要根据题目给出的图案事先建立好编码映射表就行。这提醒我们在处理有固定模式的识别问题时可以尝试将其“特征化”为一个简单的值或编码。5. B-5 能力评估报告综合排序与条件筛选5.1 理解中位线与反馈分类最后一题是数据统计和处理的综合题场景是模拟一个考试系统的能力评估报告生成。题目给了N个考生每个考生有5个维度的分数。我们需要先为每个维度计算一个“中位线”。这里的中位线不是中位数而是从大到小排序后第(N1)/2N为奇数或第N/2N为偶数个值。这其实就是统计学里的“下中位数”或者说“第50百分位数”的一种定义。计算完5个维度的中位线值(m1, m2, m3, m4, m5)后对于每一个被查询的考生我们将他的每个维度分数vi与对应的中位线mi比较。如果vi mi则该维度属于“正向反馈类”否则属于“负向反馈类”。5.2 输出格式的复杂排序规则题目要求的输出格式是本题最大的难点。它要求我们把5个维度的编号1到5按特定规则输出在一行。先输出正向反馈类的维度编号按(vi - mi)的差值非递增即从大到小排序。如果差值相同则按维度编号递增从小到大排序。再输出负向反馈类的维度编号按(mi - vi)的差值非递减即从小到大排序。同样差值相同则按编号递增排序。并且每个负向反馈的编号前要加一个负号-。举个例子假设一个考生的比较结果是维度1和3正向差值分别为5和3维度2、4、5负向差值分别为214。那么输出顺序是先排正向的1和3因为差值53所以顺序是1 3。再排负向的2、4、5按(mi-vi)从小到大排是4(差1)2(差2)5(差4)所以最终输出是1 3 -4 -2 -5。5.3 实现策略与性能考量思路很直接但实现起来要注意细节和性能。N和M最大都是10^5如果对每个查询考生都重新计算中位线或者进行低效的查找很容易超时。高效的做法分三步数据读取与存储一次读取所有考生数据将准考证号和五个分数存储起来可以用HashMapString, int[]。同时将五个维度的分数分别存入5个独立的列表如ListInteger score1, score2, ...。计算中位线分别对5个分数列表进行从大到小排序。然后根据N的奇偶性取出对应位置的元素作为中位线值m1~m5。处理查询对于每个查询的准考证号快速从HashMap中取出其分数数组。然后创建一个大小为5的列表每个元素记录维度编号和差值(vi-mi)。接着根据差值的正负我们可以自然地将维度分为正向和负向两类。对正向列表按规则排序差值降序编号升序对负向列表也按规则排序mi-vi的差值升序编号升序。最后按顺序输出即可。这里排序规则的实现可以通过自定义一个Pair类或者使用int[][]并实现Comparator接口来完成。下面是一个简化的核心逻辑片段// 假设有一个Listint[] posList (存储[维度编号, vi-mi]) 和 negList (存储[维度编号, mi-vi]) // 正向排序 Collections.sort(posList, (a, b) - { if (a[1] ! b[1]) return b[1] - a[1]; // 差值降序 else return a[0] - b[0]; // 编号升序 }); // 负向排序 Collections.sort(negList, (a, b) - { if (a[1] ! b[1]) return a[1] - b[1]; // 差值升序 else return a[0] - b[0]; // 编号升序 }); // 输出 for (int[] p : posList) System.out.print(p[0] ); for (int[] n : negList) System.out.print(- n[0] );这道题综合考察了排序、查找、条件判断和自定义排序规则是PAT乙级中比较典型的“描述复杂但思路清晰”的题目。只要耐心把题目要求翻译成代码逻辑一步步实现就能拿分。它模拟了实际数据处理中的一个常见场景基于统计基准如中位数对个体进行多维度的评估和分类报告。
