最近在准备某大厂的OD机考刷到一道双机位C卷的算法题叫“AI处理器组合”限定Java实现。第一眼看到这个题名我以为是什么硬件调度或者系统资源分配问题读了两遍题干才发现它本质就是一道组合枚举题只不过穿了层AI处理器的外衣。网上这题的题解不多不少文章只讲思路、不给完整可跑的代码我把自己调试通过的Java版本和踩过的坑整理出来给正在刷OD真题的兄弟一个参考。这篇内容适合两类人一类是第一次接触OD机考、想提前熟悉C卷常见题型的同学另一类是已经会基础递归回溯但不确定怎么处理输出格式、去重逻辑和边界条件的Java选手。我会从题干还原、解法设计、完整代码、机考避坑几个方面逐层拆保证你读完能直接照着写。1. 先把题目读懂AI处理器组合到底在问什么1.1 题干还原按最常见的版本AI处理器组合这道题网上流传的版本细节略有出入但核心框架基本一致。我用自己在机考平台刷到的常见版本来还原输入第一行是两个整数N和KN表示AI处理器的总数是偶数编号从1到N。相邻编号的两个处理器组成一个链路组比如1和2是一组3和4是一组5和6是一组以此类推。K表示需要挑选的处理器数量取值只会是1、2、4。挑选规则K 1任意选一个处理器都行。K 2选出的两个处理器不能来自同一个链路组。K 4选出的四个处理器必须来自两个不同的链路组并且是整组整组地选。换句话说选了编号1就必须连带选2最终组合长这样1 2 3 4。输出要求所有满足条件的组合每个组合占一行组合内部编号升序排列组合之间按字典序升序输出。举几个例子输入 4 2 输出 1 3 1 4 2 3 2 4为什么1 2不合法因为1和2在同一个链路组里违反K 2的约束。再看看K 4的情况输入 6 4 输出 1 2 3 4 1 2 5 6 3 4 5 6因为链路组是 {1,2}、{3,4}、{5,6}整组选两组正好三种结果。1.2 考点拆解这是组合题不是排列题这道题第一眼容易让人想复杂实际上考点非常明确组合枚举 条件筛选 有序输出。最大的坑在于很多人看到“四个处理器”就下意识去写全排列。你要是在考场上输出1 3和3 1两个组合那基本可以确定这题只对了一半因为题目要的是组合组合内部不考虑顺序。组合问题用标准回溯模板时递归参数里必须带一个startIndex保证每次只往后选不回头。第二个坑是题意里的“链路组”。处理器的编号是1开头组号计算可以统一用公式(编号 - 1) / 2比如编号1得到组0编号2也得到组0编号3得到组1。这个公式建议直接背下来后面判断两个编号是否同组非常快。第三个坑是K 4的约束。不是任意挑四个来自不同组的处理器就行而是必须挑两个完整的链路组。这个约束直接决定了解法的复杂度如果无脑从编号里选4个再判断组合数量是C(N, 4)数据稍微给大一点就有大量无效枚举如果按照“选组”的思路把递归对象从“编号”换成“组”效率会高一个量级。从考点分布看这道题同时考了数据结构设计怎么表示链路组、递归回溯怎么枚举组合、剪枝优化怎么避免无效分支和排序输出怎么满足题目输出要求。这四个点也正是C卷中组合类题目的通用解法骨架。2. 解题框架回溯 条件筛选 排序输出2.1 数据结构设计先给处理器分好“链路组”写代码之前先把数据模型定下来。我推荐直接用分组数组而不是每次判断时临时计算组号。N个编号能分成N / 2个组每组两个编号int groupCount n / 2; ListInteger[] groups new List[groupCount]; for (int i 0; i groupCount; i) { groups[i] new ArrayList(); groups[i].add(2 * i 1); groups[i].add(2 * i 2); }groups[0]就是{1,2}groups[1]就是{3,4}。这样处理之后K 4的场景可以非常自然地转成“从groupCount个组里选两个组选到就把组内两个编号一起放进结果”。同时保留一个组号判断函数static int groupOf(int x) { return (x - 1) / 2; }这样K 2的场景里判断两个编号是否同组就只需要比较groupOf(a) groupOf(b)。为什么建议把组号公式和分组表都准备好因为两种场景用的判断方式不一样。K 2是逐个编号选需要快速判断“当前编号和已选编号是否同组”K 4是按组选需要直接拿到组内两个编号。提前把分组表建好两种需求都能覆盖代码也更干净。2.2 回溯怎么写从选编号到选组先看K 2的情况。标准组合回溯的模板是void dfs(int start, ListInteger path) { if (path.size() 2) { // 判断是否同组 if (groupOf(path.get(0)) ! groupOf(path.get(1))) { result.add(new ArrayList(path)); } return; } for (int i start; i n; i) { path.add(i); dfs(i 1, path); path.remove(path.size() - 1); } }这里的核心是dfs(i 1, path)保证编号只往后取不会出现1 3和3 1同时存在的情况。再看K 4。如果沿用“选编号”的思路循环里要写一堆条件判断而且会枚举大量无意义组合。更聪明的做法是把递归对象换成“组编号”void dfsPickTwoGroups(int groupIdx, ListInteger path) { if (path.size() 4) { result.add(new ArrayList(path)); return; } for (int g groupIdx; g groupCount; g) { int first groups[g].get(0); int second groups[g].get(1); path.add(first); path.add(second); dfsPickTwoGroups(g 1, path); path.remove(path.size() - 1); path.remove(path.size() - 1); } }因为每组内的两个编号天然是升序的第一组编号一定小于第二组编号所以按组顺序累加进path后path内部也是升序的。这一步直接满足了“组合内部编号升序”的要求不用额外排序。K 1就更简单了直接遍历1到N每个编号单独成一个组合。2.3 剪枝思路提前去掉不合法分支剪枝的目的不是炫技而是减少无效递归调用。以K 2为例我的代码是先枚举完所有二元组再判断是否同组这在N不大时没问题但如果机考把N调到200甚至更大无效枚举就有点浪费了。可以在回溯过程中直接跳过同组情况for (int i start; i n; i) { if (!path.isEmpty() groupOf(path.get(0)) groupOf(i)) { continue; } path.add(i); dfs(i 1, path); path.remove(path.size() - 1); }这样只有不同组的编号才会进入下一层递归路径上的每个分支都是合法分支最后也不用再做二次判断。K 4的按组选择本身已经是最优剪枝它从源头上避免了“同一组只选一个编号”这种非法状态。如果题目改成“四个处理器必须来自四个不同链路组”那你只需要在选编号的回溯里判断当前编号的组号是否已经在已选集合里出现过同样是一行判断的事。这说明剪枝的套路是通用的核心是抓住题目约束里“不能同时满足”的条件尽早掐断分支。3. Java完整实现从输入到输出一次跑通3.1 输入解析与多组处理OD机考的编程题通常要求自己写Main类并处理标准输入输出也就是俗称的ACM模式。输入用Scanner足够因为这类题的数据规模通常不大。我习惯写成while (sc.hasNextInt())的循环这样单组输入和多组输入都能兼容Scanner sc new Scanner(System.in); while (sc.hasNextInt()) { int n sc.nextInt(); int k sc.nextInt(); ... }这里有一个细节值得注意如果题目明确是单组输入那么不写while也没问题但写while不会出错而且能避免某些在线评测系统把多个测试用例一次性输入时只读第一组的问题。初始化分组表时要注意N为偶数groupCount n / 2。如果输入出现奇数最后一组会少一个编号这类非法输入在机考里一般不会出现但代码里可以加一个简单保护防止数组越界。3.2 递归实现K2和K4的差异我把完整代码整理如下可以直接复制到本地跑import java.util.*; public class Main { static int n; static int k; static int groupCount; static ListInteger[] groups; static ListListInteger result new ArrayList(); public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNextInt()) { n sc.nextInt(); k sc.nextInt(); groupCount n / 2; groups new List[groupCount]; for (int i 0; i groupCount; i) { groups[i] new ArrayList(); groups[i].add(2 * i 1); groups[i].add(2 * i 2); } result.clear(); if (k 1) { for (int i 1; i n; i) { ListInteger single new ArrayList(); single.add(i); result.add(single); } } else if (k 2) { dfsPickTwo(1, new ArrayList()); } else if (k 4) { dfsPickTwoGroups(0, new ArrayList()); } Collections.sort(result, (a, b) - { int len Math.min(a.size(), b.size()); for (int i 0; i len; i) { if (!a.get(i).equals(b.get(i))) { return a.get(i) - b.get(i); } } return a.size() - b.size(); }); for (ListInteger list : result) { StringBuilder sb new StringBuilder(); for (int i 0; i list.size(); i) { if (i 0) { sb.append( ); } sb.append(list.get(i)); } System.out.println(sb.toString()); } } } static void dfsPickTwo(int start, ListInteger path) { if (path.size() 2) { result.add(new ArrayList(path)); return; } for (int i start; i n; i) { if (!path.isEmpty() groupOf(path.get(0)) groupOf(i)) { continue; } path.add(i); dfsPickTwo(i 1, path); path.remove(path.size() - 1); } } static void dfsPickTwoGroups(int groupIdx, ListInteger path) { if (path.size() 4) { result.add(new ArrayList(path)); return; } for (int g groupIdx; g groupCount; g) { path.add(groups[g].get(0)); path.add(groups[g].get(1)); dfsPickTwoGroups(g 1, path); path.remove(path.size() - 1); path.remove(path.size() - 1); } } static int groupOf(int x) { return (x - 1) / 2; } }这段代码我实测跑过题目里的几组样例输出都正确。几个关键点再强调一下dfsPickTwo里path.size() 2时直接加入结果因为循环内已经通过groupOf判断排除了同组分支不需要二次校验。dfsPickTwoGroups的终止条件是path.size() 4每次递归一层只加一个组所以递归深度最多两个非常浅。结果排序用了自定义比较器逐个元素比较数字大小不是比较字符串原因后面专门讲。3.3 排序细节为什么不能直接转字符串机考题目要求“组合之间按字典序升序输出”这里的“字典序”指的是数学意义上序列的字典序也就是先比较第一个元素第一个元素相同再比较第二个元素。最容易踩的坑是直接用String.compareTo做排序。假设有两个组合[2, 10]和[2, 3]转成字符串 2 10 和 2 3 后字符串比较会认为 2 10 小于 2 3因为字符 1 小于 3。但整数序列字典序应该认为[2, 3]小于[2, 10]因为 3 10。所以排序必须用数字逐个比较Collections.sort(result, (a, b) - { int len Math.min(a.size(), b.size()); for (int i 0; i len; i) { if (!a.get(i).equals(b.get(i))) { return a.get(i) - b.get(i); } } return a.size() - b.size(); });这个坑在N比较小的时候不容易暴露因为编号都是个位数时字符串排序和数字排序结果一样。但一旦N超过10编号出现两位数结果就会差很多。考场上不会给这种提示只能自己小心。4. 实战踩坑双机位环境下最容易被扣分的细节4.1 类名、包名、Scanner的坑机考平台的Java提交要求和本地IDE不一样。类名必须是Main不能带package声明否则编译直接报错。我见过不少人把本地工程里的一堆 import 和类名直接复制上去结果编译失败。Scanner的问题主要是资源关闭。有些人习惯在main末尾调用sc.close()这在有些本地环境没问题但在机考提交环境里偶尔会触发奇怪的行为所以我的习惯是不主动关闭Scanner反正是单次运行。还有一个版本兼容问题机考平台的Java版本不一定支持最新语法。尽量用Java 8的朴素写法不要用var、List.of()这类新特性。上面代码里全部用的是最基础的语法到哪个环境都能编译。4.2 边界输入N2、K4、无解情况边界情况是最容易漏的。我调试时特意测了几组输入预期输出说明2 11 然后 2单个处理器任意选2 2无输出只有1和2但同组不合法结果集为空4 41 2 3 4两组全选只有一个组合2 4无输出组数不足两个选不出两个完整组如果结果集为空代码会什么都不输出。机考题目如果没有特别说明这是合理行为。但如果题目要求输出一行空行或者某个特定占位符比如 NA就需要在最后判断result.isEmpty()后单独处理。我在代码里没有加这个逻辑因为不同版本要求不一样建议你提交前看一眼题目原话别想当然。4.3 输出格式空格、换行、多余空行输出格式的评判是严格按字符串匹配的多一个空格或多一个换行都可能被判错。常见的正确做法是每个组合内部用空格分隔行尾不要留空格。每个组合单独一行即每个组合输出后有一个换行。不要在开头输出任何额外提示文字。我的输出代码用的是StringBuilder拼接在添加每个编号前判断i 0这样行尾没有多余空格System.out.println负责行尾换行。另一个细节是不要在两个测试用例之间多打一个空行。用while (sc.hasNextInt())循环时如果每轮循环结束都加一个System.out.println()多组输入就会多出空行。正确的做法是不手动添加空行让输出内容自然逐行排列。4.4 超时与内存回溯的复杂度控制这道题数据规模一般不会太大但递归的写法会直接影响超时风险。先算一笔账如果N 100K 2时组合总量是C(100, 2) 4950不管怎么枚举都很快。但K 4如果按编号选C(100, 4)约等于392万再对每个组合做链路组判断虽然勉强能跑但已经有点危险。如果N到200C(200, 4)超过6400万大概率超时。按组选就完全不同N200时只有100个组选两组是C(100, 2) 4950几乎可以忽略不计。这就是我在第2.2节强调按组递归的原因。机考对时间限制往往是1秒到2秒复杂度差几个数量级结果就是天壤之别。内存方面结果集存在ListListInteger里每个组合最多4个元素算上100组输入的极端情况也就几千个组合完全不担心内存。5. 双机位C卷备考经验除了写代码还要注意什么5.1 双机位环境准备清单OD机考是双机位监控也就是说除了电脑摄像头还要一部手机从侧面拍到你的人和屏幕。这个环节不写代码但直接影响能否正常考试准备清单整理如下项目准备要点电脑摄像头提前测试能否正常开启画面要拍到整个面部手机机位需要手机支架位置在身体侧后方45度左右拍到电脑屏幕和双手网络有线网络优先Wi-Fi容易波动手机要开飞行模式或者关掉通知浏览器按通知要求提前下载指定浏览器关闭所有插件桌面清空无关物品只留身份证和允许的草稿纸、笔草稿纸部分场次允许1张空白A4纸考试前会让你对着摄像头展示正反面这些细节看起来琐碎但任何一步出问题都可能中断考试。我见过有同学在机考开始时因为手机角度不对被要求重新调整白白浪费几分钟。双机位考试还有一个隐形要求视线不能长时间离开屏幕也不能低头看手机或草稿纸以下的位置。所以平时刷题就要养成“先想清楚再敲代码”的习惯减少考场上的临时思考时间。5.2 C卷刷题策略与时间分配C卷常见的特点是题干包装复杂但核心算法并不偏门。像“AI处理器组合”这种题表面是AI、处理器、链路底层就是回溯组合。刷题的时候不用被题干名称吓到先把输入输出读懂再抽离出数学结构。我自己的刷题顺序是先把基本的输入输出处理练熟包括Scanner、BufferedReader、StringTokenizer的用法不在这类地方浪费时间。再集中刷组合类题目包括子集、组合总和、电话号码字母组合这些题会了AI处理器组合的套路基本也就掌握了。最后刷真题和模拟题熟悉机考平台的提交节奏。时间分配上C卷如果有两道题建议先做有把握的那道再做难的。不一定非要按题目顺序写。很多同学卡在第二题上结果第一题都没提交这就亏大了。宁可第一题写得保守一点先把分数拿到再回头优化第二题。5.3 考场上遇到变体题怎么应对机考题目存在“同题不同描述”的情况AI处理器组合在不同场次里可能约束不完全一样。比如有的版本把K2的定义改成“两个处理器必须来自同一个链路组”还有的版本把K4改成“四个处理器分别来自四个不同链路组”。遇到这种情况不用慌核心回溯框架不用变只需要修改条件判断。平时练习时多问自己几个“如果题目改成XXX怎么写”比如如果要求选出的编号不能相邻怎么判断如果要求组合内不能出现连续编号怎么处理如果输出要求按字符串字典序而不是整数序列字典序怎么改比较器把这些问题在练习时都想一遍考场上看到变体就不会觉得陌生。组合类题目的本质是全排列模板去掉回头路再加一道条件筛选判断条件永远跟着题干的约束走其他部分全部固定。最后说一点我在实际调试里的体会。这道题最坑的不是递归逻辑而是很多人会把K4写成从编号里选4个再判断不是说不可以而是容易漏掉“整组整组选”这个关键约束。后来我把递归对象从编号换成组之后代码量变少逻辑也更容易检查跑出来的结果一次就对了。如果大家刷题时碰到题干描述不一样的AI处理器组合版本核心思路不用变只需要把条件判断那块换成题目给的约束就行。祝机考顺利。