拓扑排序应用：关卡解锁问题解析

发布时间：2026/7/22 6:37:03

F题闯关游戏题目描述小豫借助AI开发了一款单机闯关游戏游戏共有nnn个关卡。为引导玩家循序渐进体验内容部分关卡设置了前置解锁规则只有通关指定的前置关卡后才能解锁并进入当前关卡。请你根据给出的前置规则判断玩家是否能够解锁并通关全部关卡。输入格式第一行一个正整数ttt1≤t≤101 \leq t \leq 101≤t≤10表示测试用例的组数。对于每组测试用例第一行两个整数n,mn, mn,m1≤n≤10001 \leq n \leq 10001≤n≤10000≤m≤10000 \leq m \leq 10000≤m≤1000分别表示关卡总数和前置规则总数关卡编号从 1 到 n。接下来mmm行每行两个整数uuu和vvv表示关卡uuu是关卡vvv的前置关卡。输出格式对于每组测试用例若无法解锁全部关卡仅单独一行输出No若可以解锁全部关卡第一行输出Yes第二行按顺序输出字典序最小的闯关序列数字之间用空格分隔。示例输入 2 4 3 1 2 1 3 2 4 3 3 1 2 2 3 3 1 输出 Yes 1 2 3 4 No问题分析这是一个典型的拓扑排序问题关卡可以看作图中的节点前置规则u→vu \rightarrow vu→v表示从节点uuu到节点vvv的有向边需要判断这个有向图是否存在环如果存在环则无法完成所有关卡输出No如果没有环则可以拓扑排序输出Yes和序列要求输出字典序最小的拓扑序列算法思路1. 拓扑排序Kahn算法Kahn算法是解决拓扑排序问题的经典算法特别适合需要字典序最小序列的情况#includebits/stdc.husingnamespacestd;voidsolve(){intn,m;cinnm;vectorvectorintgraph(n1);// 邻接表vectorintindegree(n1,0);// 入度数组// 建图for(inti0;im;i){intu,v;cinuv;graph[u].push_back(v);indegree[v];}// 使用最小堆保证字典序最小priority_queueint,vectorint,greaterintpq;// 将所有入度为0的节点加入优先队列for(inti1;in;i){if(indegree[i]0){pq.push(i);}}vectorintresult;// Kahn算法核心while(!pq.empty()){intupq.top();pq.pop();result.push_back(u);// 遍历u的所有邻接节点for(intv:graph[u]){indegree[v]--;if(indegree[v]0){pq.push(v);}}}// 判断是否所有节点都被访问if(result.size()n){coutYesendl;for(inti0;in;i){coutresult[i](in-1?\n: );}}else{coutNoendl;}}intmain(){intt;cint;while(t--){solve();}return0;}2. 算法解释数据结构graph[u]存储从节点 u 出发能到达的所有节点indegree[v]记录节点 v 的入度有多少个前置关卡priority_queue最小堆保证每次取出当前可访问节点中编号最小的算法步骤初始化计算每个节点的入度入队将所有入度为 0 的节点加入最小堆循环处理从堆中取出最小节点 u将 u 加入结果序列遍历 u 的所有后继节点 v将 v 的入度减 1如果 v 的入度变为 0将 v 加入堆中判断结果如果结果序列长度等于 n说明可以完成所有关卡否则说明图中存在环无法完成示例解析示例1可以完成输入 4 3 1 2 1 3 2 4 图结构 1 → 2 → 4 ↘ 3 拓扑序列1 2 3 4字典序最小示例2存在环无法完成输入 3 3 1 2 2 3 3 1 图结构 1 → 2 → 3 → 1形成环 无法拓扑排序输出No关键点总结拓扑排序适用场景有向无环图DAG的线性排序字典序最小使用最小堆优先队列而不是普通队列环检测如果最终结果序列长度小于 n说明存在环多测试用例注意每组测试前要清空数据结构H题和谐模数问题题目描述在魔法森林的深处小明正在进行一项古老的仪式——apple‑coconut‑mango。仪式需要找到一个神秘整数 k使得所有魔法能量值除以 k 后得到相同的余数。给定一个长度为nnn的整数序列a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​若存在整数k1k 1k1使得所有aia_iai​对kkk取模的余数相同则称kkk为和谐模数。现在小明需要你帮助他找出所有大于 1 的和谐模数。输入格式第一行包含一个正整数nnn2≤n≤1002 \leq n \leq 1002≤n≤100表示能量值的个数。接下来nnn行每行包含一个整数aia_iai​1≤ai≤1091 \leq a_i \leq 10^91≤ai​≤109表示各魔法的能量值。保证所有能量值互不相同。输出格式一行正整数以升序输出所有符合要求的kkk中间以空格分隔。如果不存在这样的数输出-1。示例输入 3 6 34 38 输出 2 4问题分析这是一个数论问题需要找到所有大于1的整数kkk使得ai mod kr(对所有 i 都相同) a_i \bmod k r \quad (\text{对所有 } i \text{ 都相同})ai​modkr(对所有i都相同)等价于ai−aj≡0(modk)(对所有 i,j) a_i - a_j \equiv 0 \pmod{k} \quad (\text{对所有 } i, j)ai​−aj​≡0(modk)(对所有i,j)也就是说kkk必须能整除所有数对之差的绝对值k∣∣ai−aj∣(对所有 i,j) k \mid |a_i - a_j| \quad (\text{对所有 } i, j)k∣∣ai​−aj​∣(对所有i,j)因此我们需要找到所有大于1的整数kkk使得kkk能整除所有数对差值的最大公约数。算法思路计算差值计算所有数对差值的绝对值求最大公约数计算这些差值的最大公约数ggg特殊情况如果g0g 0g0所有数相等那么任意k1k 1k1都满足条件但题目保证所有能量值互不相同所以这种情况不会出现如果g1g 1g1则不存在大于1的kkk输出-1找出所有因数找出ggg的所有大于1的因数按升序输出代码实现#includebits/stdc.husingnamespacestd;voidsolve(){intn;cinn;vectorinta(n1);for(inti1;in;i)cina[i];intg0;for(inti1;in;i){g__gcd(g,abs(a[i1]-a[i]));//计算所有数对差值的最大公约数}if(g1)cout-1endl;else{for(inti2;is;i){if(g%i0)couti ;// 输出g的所有大于1的因数}coutsendl;}}intmain(){intt1;while(t--)solve();return0;}时间复杂度计算所有数对差值O(n2)O(n^2)O(n2)其中n≤100n \leq 100n≤100完全可行计算最大公约数每次计算O(log⁡M)O(\log M)O(logM)其中MMM是数值范围找出所有因数O(g)O(\sqrt{g})O(g​)其中g≤109g \leq 10^9g≤109总复杂度O(n2log⁡Mg)O(n^2 \log M \sqrt{g})O(n2logMg​)关键点数学转化将问题转化为求所有数对差值的最大公约数的因数边界情况所有数相等时任意k1k 1k1都满足但题目保证数互不相同g1g 1g1时直接输出-1因数查找只需遍历到g\sqrt{g}g​注意i2gi^2 gi2g的情况示例解析示例输入363438计算过程数对差值|6-34| 28|6-38| 32|34-38| 4最大公约数gcd(28, 32, 4) 44的大于1的因数2, 4输出2 4关键点总结数学建模将余数相同问题转化为整除问题最大公约数性质如果kkk整除所有ai−aja_i - a_jai​−aj​则kkk整除这些差值的最大公约数因数查找优化只需遍历到g\sqrt{g}g​即可找到所有因数边界处理注意g1g1g1和所有数相等的情况总结这道H题考察了数论中的同余性质和最大公约数的应用通过巧妙的数学转化将问题简化是典型的竞赛数学题目。