SMU 2026 Spring 天梯赛5题解
-3 冠军魔术
题意：
给定初始纸牌数量 � 和推送次数 �。每次推送：纸牌变硬币数量不变，硬币变纸牌数量加倍。初始为纸牌。求 � 次后是纸牌还是硬币，以及数量。
思路：
推送奇数次后为硬币，偶数次后为纸牌。数量每次从硬币变纸牌时加倍，总共加倍次数为 �/2 次。因此数量为 �×2�/2。
代码
点击查看代码
7-4 Cassels方程
题意：
判断给定的三个正整数 �, �, � 是否满足方程 �2+�2+�2=3⋅�⋅�⋅�。
思路：
直接计算等式左右两边的值，比较是否相等即可。注意数据范围在 1000 以内，但乘积可能较大，使用 long long 避免溢出。
代码
点击查看代码
7-5 吉老师的回归
题意：
给定 N 个题目描述字符串，吉老师按顺序看题，但跳过包含“qiandao”或“easy”（区分大小写）的题目。已知吉老师做完了 M 道题目（实际做的，不包括跳过的），求他当前正在做的题目。如果已做完所有有效题目，输出“Wo AK le”。
思路：
模拟吉老师的做题过程。遍历每个题目，检查是否包含关键词，若包含则跳过。维护一个计数器 cnt 表示有效题目数。当 cnt 等于 M 时，记录下一个有效题目作为答案。遍历结束后，若未记录到答案，则输出“Wo AK le”。
代码
点击查看代码
7-6 大笨钟的心情
题意：
给定 24 个整数，代表一天 24 小时的心情指数。随后输入若干询问，每个询问是一个小时数（0-23），要求输出该小时的心情指数以及是否大于 50（大于则输出 Yes，否则输出 No）。当输入非法小时数（不在 0-23 范围内）时结束输入。
思路：
直接用数组存储 24 个心情指数，对于每个合法询问，输出对应位置的值并判断是否大于 50 即可。
代码
点击查看代码
7-7 爆气球
题意：
给定 � 个递增的整数坐标和一个长度 ℎ。孩子跳到一个位置 �，躺平后身体覆盖区间 [�,�+ℎ]。求一个位置 �，使得区间覆盖的气球数最多，输出 � 和覆盖数。如果有多个 �，输出最小的 �。
思路：
由于坐标有序，使用双指针维护一个滑动窗口，窗口内点的最大差不超过 ℎ。对于每个窗口，覆盖数为窗口点数，对应的最小 � 为窗口最大坐标减去 ℎ。遍历所有窗口，记录最大覆盖数和对应的最小 �。
代码
点击查看代码
7-8 帅到没朋友
题意：
给定 N 个朋友圈，每个朋友圈有 K 个人（K=1 表示只有自己）。如果一个人出现在某个 K>1 的朋友圈中，则他有朋友。接下来有 M 个查询，按顺序输出那些没有朋友的人（同一个人只输出一次）。如果没有，输出 "No one is handsome"。
思路：
用数组标记出现在 K>1 朋友圈中的人（有朋友）。查询时，按顺序检查是否被标记过，并且只输出第一次出现的无朋友者。注意输出 ID 为 5 位数字（前补零）。
代码
点击查看代码
7-9 海盗分赃
题意：
P个海盗偷了D颗钻石，按抽签顺序1到P编号。由1号开始提出分配方案（给出每个海盗具体分到的钻石数），如果得到绝对多数（大于半数）同意，则执行；否则1号被杀死，由2号继续提出方案，直到方案通过或只剩最后一个海盗独占所有钻石。海盗行为准则：
- 以自身利益最大化为准；
- 在利益相同时，不会故意致同伙于死地（即不会在利益相同时选择杀人）；
- 分配钻石时，优先分给序号小的海盗。
给定D和P（3≤P≤D≤100），求1号海盗在自己提出的方案中最多能获得多少钻石。
本题为经典博弈论题目，有兴趣的自行搜索了解。
思路：
逆推法。从最后只剩一个海盗（P号）开始，逐步增加海盗数，计算每个海盗作为提议者时，为让方案通过所需的最小花费（给其他海盗的钻石），从而最大化自身所得。
对于当前提议者i（总人数n = P-i+1），需获得至少need = n/2+1人同意（包括自己）。他从i+1到P号海盗中选择need-1人，用钻石收买。对于海盗j，若当前轮给他x颗钻石，他同意的条件是x > next[j]（其中next[j]为下一轮中j能获得的钻石数）。
提议者i会优先选择next[j]最小的海盗，给这些海盗next[j]+1颗钻石以争取同意。计算总花费sum，若sum ≤ D则方案可行，i获得D - sum颗钻石，并更新next数组（被收买的海盗j的next值变为next[j]+1，其余为0）；若不可行则i获得0颗且next数组不变（i被杀）。最终next[1]即为答案。
代码
点击查看代码
7-10取行李
题意：
给定一个正整数 � 和一个 1 到 � 的重排列，表示旅客的排队顺序。行李按顺序 1 到 � 到达传送带窗口，行李 � 属于旅客 �。每个人到窗口时，如果行李不是自己的，就走到队尾等待，行李留在窗口。每次检查需要 1 分钟。求所有行李被取走的总时间和旅客的平均等待时间（从开始到行李被取走的时间）。
思路：
模拟过程。维护一个旅客队列，对于每个行李 �，从队首开始检查，如果不匹配则队首移到队尾，时间加 1；直到匹配，时间加 1 并取走行李，累加等待时间。总时间即为最后取走行李的时间，平均等待时间为总等待时间除以 �。
代码
点击查看代码
7-11 德才论
题意：
给定 � 个考生的准考证号、德分和才分，以及最低分数线 � 和优先录取线 ℎ。首先筛选出德分和才分均不低于 � 的考生，然后根据以下规则分为四类：
- 第一类：德分和才分均不低于 ℎ。
- 第二类：德分不低于 ℎ，但才分低于 ℎ（不低于 �）。
- 第三类：德分和才分均低于 ℎ，但德分不低于才分。
- 其他：剩余达到 � 的考生。
对每类考生分别按总分降序排序，若总分相同则按德分降序排序，若德分也相同则按准考证号升序排序。输出达标考生总数，并按类别顺序（1→2→3→4）输出所有考生信息。
思路：
直接模拟分类过程，使用四个 vector 分别存储四类考生。读入时根据条件将考生放入对应的容器，然后对每个容器按题目要求排序。最后输出总人数并按顺序输出所有考生。
代码
点击查看代码
7-12 红色警报
题意：
给定一个包含 N 个城市和 M 条道路的图，需要按顺序处理 K 个城市被攻占的事件。每次攻占一个城市后，需要判断国家的连通性是否发生变化（即连通分量数量是否增加）。如果增加，发出红色警报；否则只输出普通信息。如果所有城市都被攻占，最后输出"Game Over."。
思路：
使用并查集的思想模拟删除城市后的连通分量数量。每次删除城市后，重新计算剩余城市的连通分量数量，并与之前进行比较。
代码
点击查看代码
7-13 森森美图
题意：
给定一个 �×� 的网格，每个格子有一个分值。给定起点 �(��,��) 和终点 �(��,��)。连接 � 和 � 的直线将网格分为两部分（不包括直线上的点）。需要在每一部分中分别找一条从 � 到 � 的八连通路径，使得两条路径的总得分最小。得分计算规则：
- 若从 (�,�) 走到正交相邻格（上下左右），得分增加目标格的分值。
- 若走到斜向相邻格，得分增加目标格分值 + （当前格分值 + 目标格分值）×(2−1)。
起点和终点的分值只计算一次（即总得分要减去一次起点和一次终点的分值）。
思路：
使用 Dijkstra 算法求最短路径。分别对直线的两侧进行两次最短路计算，每次只允许访问该侧的点（但允许最后一步走到终点）。判断点 � 位于直线的哪一侧使用叉积：��→×��→ 的符号。注意坐标原点在左上角，� 轴向下为正，叉积公式为 (��−��)∗(�−��)−(��−��)∗(�−��)。
代码
点击查看代码
7-14 那就别担心了
题意：
给定一个有向无环图，问从起点A到终点B有多少条不同的路径，并判断是否所有从A出发的路径都能到达B。
思路：
- 用DFS标记从A可达的所有节点
- 统计可达节点的出度和入度（仅考虑可达节点之间的边）
- 计数：用拓扑排序+DP计算从A到B的路径数，dp[A]=1，按拓扑序累加
- 判断逻辑自洽：检查所有可达节点中，除了B以外是否有出度为0的节点
代码
点击查看代码
7-15 超能力者大赛
题意：
模拟主角按照贪心算法行动，直到击败所有对手、无法击败任何对手或时间结束。