-3 冠军魔术题意给定初始纸牌数量 和推送次数 。每次推送纸牌变硬币数量不变硬币变纸牌数量加倍。初始为纸牌。求 次后是纸牌还是硬币以及数量。思路推送奇数次后为硬币偶数次后为纸牌。数量每次从硬币变纸牌时加倍总共加倍次数为 /2 次。因此数量为 ×2/2。代码点击查看代码7-4 Cassels方程题意判断给定的三个正整数 , , 是否满足方程 2223⋅⋅⋅。思路直接计算等式左右两边的值比较是否相等即可。注意数据范围在 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 个人K1 表示只有自己。如果一个人出现在某个 K1 的朋友圈中则他有朋友。接下来有 M 个查询按顺序输出那些没有朋友的人同一个人只输出一次。如果没有输出 No one is handsome。思路用数组标记出现在 K1 朋友圈中的人有朋友。查询时按顺序检查是否被标记过并且只输出第一次出现的无朋友者。注意输出 ID 为 5 位数字前补零。代码点击查看代码7-9 海盗分赃题意P个海盗偷了D颗钻石按抽签顺序1到P编号。由1号开始提出分配方案给出每个海盗具体分到的钻石数如果得到绝对多数大于半数同意则执行否则1号被杀死由2号继续提出方案直到方案通过或只剩最后一个海盗独占所有钻石。海盗行为准则以自身利益最大化为准在利益相同时不会故意致同伙于死地即不会在利益相同时选择杀人分配钻石时优先分给序号小的海盗。给定D和P3≤P≤D≤100求1号海盗在自己提出的方案中最多能获得多少钻石。本题为经典博弈论题目有兴趣的自行搜索了解。思路逆推法。从最后只剩一个海盗P号开始逐步增加海盗数计算每个海盗作为提议者时为让方案通过所需的最小花费给其他海盗的钻石从而最大化自身所得。对于当前提议者i总人数n P-i1需获得至少need n/21人同意包括自己。他从i1到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 超能力者大赛题意模拟主角按照贪心算法行动直到击败所有对手、无法击败任何对手或时间结束。思路