蓝桥杯齿轮题解析：哈希集合与整数运算解决比例匹配问题

1. 项目概述与问题拆解最近在带学生备赛蓝桥杯刷到了2022年国赛B组的这道“齿轮”题。题目本身描述不长但涉及到的数学建模和算法优化思想非常典型是检验选手从实际问题抽象出数学模型并选择高效算法能力的一道好题。很多同学第一次看到题目容易被“齿轮”、“传动比”这些物理概念唬住或者一头扎进复杂的排列组合计算里最终要么超时要么思路混乱。今天我就结合这道P8799来详细拆解一下如何用C将这道“物理题”转化为清晰的“算法题”并高效求解。简单来说题目给出了n个齿轮的半径询问在给定一个初始齿轮后是否存在一种齿轮排列方式使得最右侧齿轮的转速达到目标值。核心是判断从给定的半径列表中能否选出若干齿轮顺序排列使得第一个齿轮与最后一个齿轮的半径之比等于目标转速比。这本质上是一个在数组中寻找特定比例的数对或子序列的问题。暴力枚举所有排列显然不现实n最大10^5我们必须找到更聪明的办法。2. 核心思路与数学模型建立2.1 问题重述与关键转化我们先抛开齿轮的物理背景把问题翻译成纯数学语言我们有n个正整数代表齿轮半径存储于数组r中。我们有一个查询q包含起始齿轮半径first和目标转速比target以最简分数形式a/b给出表示目标转速是起始转速的a/b倍。齿轮传动的基本原理两个啮合的齿轮转速比与半径成反比。即如果齿轮1半径r1齿轮2半径r2则ω1 / ω2 r2 / r1ω表示转速。多个齿轮串联时总传动比为各相邻齿轮传动比的乘积。例如齿轮序列r[0], r[1], r[2], ..., r[k] 则ω_start / ω_end (r[1]/r[0]) * (r[2]/r[1]) * ... * (r[k]/r[k-1]) r[k] / r[0]。这个化简至关重要你会发现中间齿轮的半径在乘积中都被约掉了。最终整个传动系统的传动比只与第一个齿轮和最后一个齿轮的半径有关等于r_last / r_first。因此原问题“是否存在一种排列”被简化为在半径数组r中是否存在两个数可以相同吗题目没说不能复用但通常齿轮是选出的不同实体一般理解为不同齿轮即下标不同的两个数使得它们的比值r[j] / r[i]等于目标值target并且其中一个数必须等于查询中指定的first。所以对于每次查询(first, target)问题等价于 判断在数组r中是否存在另一个半径值x使得x / first target或first / x target取决于哪个作分子。即判断first * target或first / target这个值是否存在于数组r中除了first本身的位置。2.2 算法选型与复杂度分析思路清晰后算法设计就水到渠成了。我们需要一个支持高效“查找”的数据结构。暴力查找不可行对于每个查询遍历整个数组r寻找匹配值。时间复杂度 O(n * q)n和q最大均为10^5会达到10^10操作量级必然超时。排序二分查找预处理时将半径数组排序对于每个查询计算目标值val first * target然后用二分查找判断val是否在数组中。时间复杂度 O((n log n) (q log n))可以接受。但需要注意处理分数比较的精度问题。哈希集合最优选择将所有的半径值存入一个unordered_set哈希集合。对于每个查询计算目标值val然后直接在集合中查找是否存在。查找操作平均时间复杂度 O(1)整体复杂度 O(n q)是最优解。显然方法3哈希集合是最直接、最高效的。但这里有一个巨大的“坑”也是本题的核心难点精度处理。因为target是以分数a/b给出的first是整数val first * target first * (a / b)可能不是整数。而我们的半径是整数如果val不是整数它肯定不在整数集合中。但是我们需要判断的是比值相等而非数值相等。更准确的判断条件是是否存在一个半径x使得x / first a / b即x * b first * a。由于x和first都是整数a和b也是整数我们可以将判断转化为整数运算彻底避免浮点数精度误差。最终算法逻辑预处理将所有半径读入数组r并存入一个哈希集合radius_set用于快速查找。对于每个查询(first, a, b)情况A寻找一个半径x使得x / first a / bx * b first * a。需要判断(first * a) % b 0吗不我们需要的是x存在。即判断整数(first * a) / b是否存在且为整数。更安全的写法是计算long long target_val (long long)first * a;如果target_val % b 0则x_candidate target_val / b。然后检查x_candidate是否在radius_set中并且确保x_candidate不等于first除非题目允许同一个齿轮用两次通常不允许。情况B寻找一个半径x使得first / x a / bfirst * b x * a。同理计算x_candidate (long long)first * b / a需要(first * b) % a 0然后检查x_candidate是否在集合中且不等于first。只要情况A或情况B任一满足则回答“YES”否则“NO”。这里还有一个关键点first本身可能不在半径集合中吗题目描述“现给出这 n 个齿轮的半径以及 q 个询问”询问中的first应该是这 n 个半径之一。但严谨起见代码中应该先判断first是否在集合中如果不在直接输出“NO”因为起始齿轮都不存在。3. 代码实现与逐行解析掌握了核心算法我们来看C实现。我会用详细的注释解释每一部分。#include iostream #include vector #include unordered_set using namespace std; int main() { // 关闭同步提升cin/cout速度适用于大量输入输出的竞赛题 ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorint radius(n); // 使用unordered_set进行O(1)的查找 unordered_setint radius_set; // 读入所有齿轮半径并存入集合 for (int i 0; i n; i) { cin radius[i]; radius_set.insert(radius[i]); } // 处理每一个查询 while (q--) { int first, a, b; cin first a b; // 关键检查1起始齿轮是否存在 if (radius_set.find(first) radius_set.end()) { cout NO\n; continue; } bool found false; // 情况1寻找齿轮x使得 x / first a / b x (first * a) / b // 注意必须确保除法是精确的整数除法 long long target_num 1LL * first * a; // 1LL 强制转换为long long防止int溢出 if (target_num % b 0) { long long x_candidate target_num / b; // 检查候选值是否在集合中并且不是齿轮本身除非题目允许重复使用 if (x_candidate 1 x_candidate 1000000000) { // 可选根据数据范围加判断 if (radius_set.find(x_candidate) ! radius_set.end() x_candidate ! first) { found true; } } } // 情况2寻找齿轮x使得 first / x a / b x (first * b) / a if (!found) { long long target_num2 1LL * first * b; if (target_num2 % a 0) { long long x_candidate target_num2 / a; if (x_candidate 1 x_candidate 1000000000) { if (radius_set.find(x_candidate) ! radius_set.end() x_candidate ! first) { found true; } } } } cout (found ? YES : NO) \n; } return 0; }代码要点解析输入输出优化ios::sync_with_stdio(false); cin.tie(nullptr);是竞赛标配能显著加快C标准流输入输出速度。注意使用后不能混用printf/scanf和cin/cout。数据结构选择unordered_set基于哈希表平均查找时间复杂度O(1)完美契合本题需求。vector用于存储原始半径虽然查询主要用set但保留原始数据有时便于调试。整数运算与溢出处理first * a可能超出int范围最大10^9 * 10^9所以必须用long long计算。1LL * first * a是一种常见的强制提升为long long的写法。整除判断if (target_num % b 0)是核心。只有能整除计算出的x_candidate才是整数才可能存在于我们的整数半径集合中。候选值范围检查if (x_candidate 1 x_candidate 1000000000)是一个可选的健壮性检查。题目虽未明确半径范围但通常竞赛题数据会在合理范围内。加上它可以防止因计算错误导致的意外查找。齿轮不能重复使用条件x_candidate ! first确保了找到的齿轮不是起始齿轮本身除非题目明确说明可以复用本题没有。逻辑短路在情况1找到后通过if (!found)进入情况2避免不必要的计算。4. 常见错误与深度避坑指南这道题看似简单但实际实现时陷阱不少。下面是我总结的学员们最容易犯的几个错误以及背后的原因。4.1 浮点数精度陷阱最致命错误做法double target_ratio (double)a / b; double needed_radius first * target_ratio; // 或 first / target_ratio // 然后遍历数组用 fabs(r[i] - needed_radius) 1e-9 判断为什么错浮点数在计算机中是以二进制近似存储的涉及除法时可能产生无限循环小数导致精度损失。例如a1, b3target_ratio并非精确的0.333333...。即使比较时使用eps如1e-9也可能因为精度问题导致本应相等的数被判为不等或者本应不等的数被判为相等造成WA错误答案。避坑指南在算法竞赛中凡是涉及比值、比例、且输入为整数的问题应首先考虑将等式转化为整数等式通过判断整除来避免浮点数运算。这是处理此类问题的黄金法则。4.2 忽略整数溢出错误做法int target_num first * a; // 可能溢出 if (target_num % b 0) { ... }当first和a都很大时例如接近10^9它们的乘积会远超int型能表示的范围约21亿导致溢出计算结果错误。避坑指南在乘法操作前养成预估数据范围的习惯。本题中first, a, b最大10^9乘积最大10^18需要用long long64位整数范围约±9e18来存储。C中写1LL * a * b是安全的习惯。4.3 遗漏查询的另一种情况错误做法只考虑了x / first target的情况忽略了first / x target的情况。 题目要求的是最终转速是target倍传动比r_last / r_first等于target。但r_last和r_first哪个是first题目中first是给定的起始齿轮半径它既可能是序列中的第一个齿轮此时r_first first也可能是最后一个齿轮此时r_last first。所以我们需要检查两种可能性。避坑指南仔细阅读问题理解变量的角色。对于比例问题要考虑分子分母互换的对称情况。画个简单的示意图齿轮序列A - B - C转速比 C的半径 / A的半径有助于理解。4.4 未判断起始齿轮是否存在错误做法假设输入的first一定在半径列表中。 虽然题目描述可能隐含此意但严谨的代码应对输入做合法性检查或防御性编程。如果first根本不在集合中后续计算都没有意义直接输出“NO”。避坑指南不要完全信任输入格式。对于查询条件中的“键值”先检查其是否在有效数据集合中这是一个好习惯。4.5 哈希集合查找的边界情况错误做法计算出的x_candidate可能为0或负数直接放入unordered_setint查找。 我们的半径是正整数如果候选值非正肯定不存在。虽然查找一个不存在的值对结果没影响但有时可能导致意外的行为例如某些哈希函数对0处理特殊。显式判断一下更安全。实操心得在使用容器查找前先对要查找的值做一个简单的合理性判断如范围、符号可以使代码更健壮也便于调试。5. 算法扩展与思维提升解决这个问题后我们可以思考一些变种和扩展这有助于深化对问题本质的理解。5.1 如果齿轮可以复用呢如果允许同一个齿轮在序列中使用多次那么判断逻辑需要改变吗仔细想想如果齿轮可以复用那么对于查询(first, target)我们只需要判断target是否为1。因为如果target 1直接使用一个齿轮自己或者两个相同半径的齿轮即可。如果target ! 1我们仍然需要另一个不同半径的齿轮来改变传动比。所以允许复用只影响target 1的情况基本算法不变只需在判断时如果x_candidate first且target ! 1则不能认为找到因为需要不同的齿轮来改变速度除非target 1。5.2 如果查询的不是是否存在而是有多少种排列方式这就变成了一个计数问题。我们需要计算有多少对(i, j)i ! j使得r[j] / r[i] target。这可以通过使用哈希映射unordered_map来计数每个半径出现的次数来解决。将半径数组排序如果需要处理重复值。遍历每个半径r[i]计算其对应的配对半径r[i] * target需要处理整除和整数化。在哈希映射中查找配对半径的数量累加到答案中。注意处理重复数和i j的顺序问题通常除以2。 这变成了一个经典的“两数之比”计数问题。5.3 从“齿轮”到更一般的“比例匹配”问题本题的核心抽象是给定一个整数集合和多个比例查询判断集合中是否存在两个数满足该比例。这是一种非常实用的模型可以应用于很多场景金融分析判断是否存在两只股票的价格满足特定比值。资源调度判断是否存在两台机器的处理能力满足任务所需的比例。化学计量判断混合物中是否存在两种成分的质量比符合要求。掌握将具体场景抽象为“集合查找比例判断”模型的能力比解出这道题本身更重要。6. 调试技巧与测试数据设计自己编写测试数据是验证算法正确性的关键。针对这道题可以设计以下几类测试数据基础功能测试输入 5 3 2 4 6 8 10 2 1 2 // 寻找4应输出 YES 10 2 1 // 寻找5但5不在集合中应输出 NO 4 2 1 // 寻找2应输出 YES 输出 YES NO YES边界值测试大数测试半径和a,b都接近10^9检查整数溢出。target 1测试即需要转速相同。此时x_candidate first根据题目是否允许复用齿轮结果可能为YES或NO。first不在集合中的测试。精度陷阱测试输入 3 1 1 3 300000000 1 1 3 // target 1/3 需要寻找半径3。计算1*1/3 不是整数走情况2: 1*3/13存在。 输出 YES大量数据测试生成n100000, q100000的随机数据用脚本对拍检查程序效率和正确性。调试时的小技巧在本地调试时可以在关键分支添加一些输出比如打印计算出的target_num,x_candidate等帮助理解程序逻辑流。提交前务必记得删除这些调试输出。这道“齿轮”题很好地体现了竞赛编程的特点题目描述可能披着一层实际应用的外衣但核心考察的是选手的抽象建模能力和基础算法与数据结构的应用能力。关键在于不要被表象迷惑要迅速剥离出问题的数学本质。对于比例问题牢记“化比例为整数等式”对于查找问题优先考虑哈希表或二分查找。把这些套路内化再遇到类似问题就能快速找到突破口了。