【华为OD机试真题】手牌接龙 · 最大出牌次数（C++）

一、真题题目描述手里给一副手牌数字从0-9有(红色)g(绿色)b(蓝色)y(黄色)四种颜色出牌规则为每次打出的牌必须跟上一张的数字或者颜色相同否则不能抽选。选手应该怎么选才能使得抽选的次数最大并且输出这个最大次数。输入描述第一行牌的数值n(1n9)·第二行牌的颜色(r,g,b,y四种颜色表示)输出描述输出最大出牌数量0示例1【输入输出示例仅供调试后台判题数据一般不包含示例】输入1 4 3 4 5r y b b r输出3说明如果打(1,r)-(5,r)那么能打两张。如果打(4,y)-(4,b)-(3,b)那么能打三张。二、题目深度解析这道题本质是在寻找图中的最长简单路径。由于 N 极小 N≤9 O(N!)的复杂度完全在 C 的毫秒级处理能力范围内。1. 数据结构设计手牌结构体struct Card { int num; char color; bool used; // 标记是否已出 };使用struct将属性打包比并行数组更易于管理且编译器会进行内存对齐优化。全局/类成员变量vectorCard cards存储所有手牌。int maxLen记录全局最大出牌数。int n手牌总数。2. 核心逻辑流程外层循环遍历0到n-1尝试让每一张牌作为第一张打出的牌。DFS 递归参数lastIndex(上一张牌的索引),currentCount(当前长度)。更新最值maxLen max(maxLen, currentCount)。剪枝/扩展遍历所有未使用的牌i。若cards[i]与cards[lastIndex]满足数字同 OR 颜色同标记cards[i].used true递归dfs(i, currentCount 1)回溯cards[i].used false(关键步骤)3. C 性能优势引用传递vector和struct在递归中通过引用或全局访问避免了值拷贝的开销。IO 加速ios::sync_with_stdio(0); cin.tie(0);确保输入读取不成为瓶颈。栈效率C 的函数调用栈经过高度优化即使递归深度达到 9 层开销也几乎为零。三、C 极致实现 (C11/14 标准)本代码采用了以下最佳实践IO 加速关闭同步流提升读取速度。结构体封装清晰定义手牌属性。引用优化虽然本题使用了全局变量但在复杂场景下推荐引用传递。逻辑严密完善的边界处理和状态恢复。#include iostream #include vector #include algorithm #include string using namespace std; // 手牌结构体 struct Card { int num; char color; bool used; Card(int n, char c) : num(n), color(c), used(false) {} }; int n; vectorCard cards; int maxLen 0; // DFS 回溯函数 // lastIndex: 上一张打出的牌的索引 // currentCount: 当前已经打出的牌数 void dfs(int lastIndex, int currentCount) { // 更新全局最大值 if (currentCount maxLen) { maxLen currentCount; } const Card lastCard cards[lastIndex]; // 尝试接下一张牌 for (int i 0; i n; i) { if (!cards[i].used) { const Card nextCard cards[i]; // 规则判断数字相同 或 颜色相同 if (nextCard.num lastCard.num || nextCard.color lastCard.color) { // 选择标记为已使用 cards[i].used true; // 递归进入下一层 dfs(i, currentCount 1); // 回溯恢复状态以便其他分支可以使用这张牌 cards[i].used false; } } } } void solve() { // 输入加速 ios::sync_with_stdio(false); cin.tie(nullptr); if (!(cin n)) return; // 临时存储数字和颜色 vectorint nums(n); vectorchar cols(n); // 读取数字行 for (int i 0; i n; i) { cin nums[i]; } // 读取颜色行 for (int i 0; i n; i) { string s; cin s; cols[i] s[0]; // 取第一个字符 } // 初始化手牌 cards.clear(); cards.reserve(n); for (int i 0; i n; i) { cards.emplace_back(nums[i], cols[i]); } maxLen 0; // 核心策略枚举每一张牌作为起点 // 因为题目没规定第一张必须是谁最长序列可能以任意牌开头 for (int i 0; i n; i) { cards[i].used true; // 标记起点 dfs(i, 1); // 从该点开始搜索长度为1 cards[i].used false; // 回溯还原现场供下一次循环使用 } cout maxLen endl; } int main() { solve(); return 0; }✅ C 版代码亮点解析const Card引用在dfs内部使用const Card lastCard cards[lastIndex];避免了对结构体的拷贝。虽然Card很小但在深层递归中这种习惯能显著提升性能并体现专业性。emplace_back使用cards.emplace_back(nums[i], cols[i])直接在容器内存中构造对象比push_back(Card(...))少了一次临时对象的构造和析构是 C11 后的高效写法。输入流处理颜色输入可能是字符串如 r代码中使用string s; cin s; cols[i] s[0];安全地提取字符避免了直接cin char可能遇到的空白符跳过问题虽然cin char也会跳过空白但读字符串更稳健。清晰的回溯结构used true-dfs-used false三段式结构缩进整齐逻辑一目了然极大降低了维护成本。四、逻辑推演与正确性证明为什么必须枚举所有起点假设最优解序列是A - B - C。如果我们只从A开始 DFS能找到这个序列。但如果我们错误地固定从某张特定的牌比如输入的第一张牌X开始而X不在最优序列中或者X在最优序列的中间我们就永远无法得到A-B-C的全长。结论最长路径的起点是不确定的必须通过外层循环for (int i 0; i n; i)穷举所有可能性。为什么回溯不会死循环每次递归前都会检查!cards[i].used。一旦某张牌被使用它在当前路径的后续递归中会被跳过。路径长度严格递增最大深度为 N 因此必然终止。五、避坑指南 (C 特有)⚠️cin的空白符处理cin int和cin char都会自动跳过空格和换行。本题中数字和颜色分两行直接使用循环读取即可无需手动处理换行符。但要注意颜色如果是字符串输入要取[0]。全局变量重置如果是在多组测试用例的环境中虽然本题通常是一组务必在solve函数开始时清空cards并重置maxLen。本代码已在solve中处理。递归深度N9 时递归深度仅为 9远小于默认栈限制通常几 MB无需手动调整栈大小。max函数使用std::max需要包含algorithm头文件否则编译报错。六、复杂度分析时间复杂度 O(N!)最坏情况下所有牌互连需遍历全排列。N9 时9!362,880 次操作。C 每秒可执行约 10^8 次操作因此耗时约为3-5 毫秒性能极其优异。空间复杂度 O(N)递归栈深度 O(N) 存储数组 O(N) 。内存占用极小。七、结语C 以其零开销抽象和极致性能成为解决此类搜索问题的首选。通过这道题我们不仅掌握了DFS 回溯的通用模板还实践了 C 的结构体设计、引用传递和IO 加速技巧。对于初学者理解used标记的“设”与“消”是掌握回溯法的关键。对于进阶者体会 C 在微小数据量下依然保持的代码整洁性与运行速度的完美平衡。掌握这套C DFS 模板无论是面对华为 OD 的“手牌接龙”还是更复杂的“八皇后”、“数独”问题都能游刃有余觉得有帮助请点赞、收藏⭐、关注下一期我们将挑战动态规划专题背包问题的 C 滚动数组优化