[数据结构与算法]天体赛练习集 简要题解 - L2

001 - 紧急救援

• 作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
• 一眼最短路，然后题目要求输出最短路径的条数，以及能召集尽可能多的救援队
• 维护路径信息的单元最短路问题，我们优先考虑$dijkstra$算法
• 那么我们在维护最短路径的同时，维护从起点通过最短路径走到当前节点的路径条数，以及到当前点能召集的最多的救援队的数量，然后更新距离的同时，这些信息一起维护更新，每个路径的前驱节点记录一下
• 步骤如下，如果距离能被更新，距离是第一决定因素，此时将此点的路径数，救援队数量，前驱节点，距离全部更新。如果距离相等，此时路径信息是+=而不是直接更新，再比较救援队数量来决定前驱节点要不要更新。
• 初始化，将起点的路径数信息更新为1。输出路径是递归输出即可。
• 思路不难想，也是实现细节时注意一下即可。
• 代码链接?

002 - 链表去重

• 给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
• 数组模拟链表即可，地址为$5$位数字可以直接用下标来表示节点地址，用个$pair$存一下信息。
• 用两个数组存去重的链表和删掉的链表，对于当前地址，如果数组不为空直接令最后一个$pair$的$next$指向当前接节点的地址即可。
• 代码链接?

003 - 月饼

• 月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。
  注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。
• 直接贪心即可，按照单位吨数的售价从大到小排序，能取都取，不能取把剩下的部分都取掉。
• 一个需要注意点的细节是，有可能全部的月饼售完也没有达到需求量，最后求余下部分是判断一下，如果都月饼消耗完了就不用加剩下的需求量。
• 代码链接?

004 - 这是二叉搜索树吗？

• 给定一棵树先序遍历序列，问你是否是一棵二叉搜索的先序遍历或者镜像二叉搜索树的先序遍历。

• 这里我踩得坑点应该是把二叉搜索树认为一定是一棵完全二叉树了，所以建树时出问题了。

• 这里应该用给定的先序遍历序列直接判断这是否是一棵的合法二叉搜索树的遍历序列。

• 具体方法就是先序遍历第一个节点一定是根，然后我们在当前除根节点以外序列中找出第一个大于等于根节点的节点编号，第一个小于根节点权值的编号，如果是合法二叉搜索树，二者应该编号应该相差$1$，因为他们就是左右子树的分界线，然后不断递归子区间重复即可，满足条件节点假如答案数组，如果数组长度不为$n$即可知给出的序列不合法，因为题目让我们最后输出后序遍历序列，所以我们添加节点的时候直接按照后续遍历的顺序加入即可，即先递归左右子树，再加入节点。

• 我采取的是先建好二叉搜索树，如果合法，直接对树就行后序遍历

• 代码链接?

• 关于二叉树的问题还是根据遍历序列的特殊性质或者树本身的特点，划分左右子树，递归完成建树

005 - 集合相似度

• 首先两种度量都需要去重后再确定个数，所以每个集合直接用一个$set$存储即可
• 每次询问，枚举对于其中一个集合的所有元素，查询是否在另一个集合内出现过，此为$N_c$
• 根据容斥，两个集合的个数相加减去两个集合相同的元素个数，即为两个集合不同元素个数和$N_t$
• 复杂度应该跑不满，$O$能过
• 代码链接?

006 - 树的遍历

• 给定一棵树的中序遍历和后序遍历序列，让我们给出这棵树的层序遍历序列
• 关于给定一棵二叉树的中序和先/后序之后，我们都能唯一地确定出一棵二叉树
• 利用先后序根节点位置的特殊性，如后序遍历序列，最后一个节点一定是根节点，然后再在中序遍历地序列中找到根节点对应权值的位置，由此划分出左右两个子树，通过中序序列中得到的左右子树大小，再在后序遍历序列中重新划分左右子区间，不断递归即可完成树的构造
• 代码链接?

007 - 家庭房产

• 给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。
• 一个家庭我们看作一个集合，那么可以用并查集来维护这个集合关系
• 题目中还要求了成员数，房产总数，房产总面积，这些信息量，我们都可以在并查集合并的时候，累加在一起，子节点更新父节点，总而完成统计
• 题目要求输出最小编号，这里一个比较方便的操作就是，每次合并的时候我总是把根节点编号大的向编号小的合并，这样每个家庭的祖先一定是当前家庭内部编号最小的节点
• 最后找集合时，一定是题目关系中出现过的节点并且父节点还是自己的点
• 代码链接?
• 并查集是可以在合并操作时，维护一个集合内的各种具有可加性的信息的，常见的如大小，数量

008 - 最长对称子串

• 找出一个字符串的最大回文子串
• 范围小暴力，范围大$Manacher$或者二分长度，字符串哈希
• 这里为了复习一下字符串哈希，我就枚举了长度然后哈希判相等了
• 判断回文串，需要判断这个串翻转之后是否和原串相等，所以需要正一边哈希，到一边哈希
• 代码链接?

009 - 抢红包

• 模拟题，维护一下每个人发了多少钱，抢了多少钱即可。
• 代码链接?

010 - 排座位

• 朋友的朋友是朋友，很明显的联通关系
• 直接对关系建边
• 每次询问，以其中一人为起点除法遍历图中的朋友关系，看另一人是否被访问过，即代表二人是否互为朋友吗，然后根据是否敌对关系，回答问题即可
• 代码链接?

011 - 玩转二叉树

• 给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
• 和$006$一样，中序和先序确定一棵二叉树，只不过把左儿子指向右子树，右儿子指向左子树即可，然后直接$bfs$层序输出
• 代码链接?

012 - 关于堆的判断

• 询问都是堆节点中，父子兄弟节点间的关系
• 直接手写模拟一个堆的建立，每次在序列末尾插入，然后$siftup$操作上调即可
• 关于这种数和字符串和在一起的询问方式，我的评价是还是一个个输入比较好，不要直接用$getline$读，因为会涉及到数字位数，正负等问题，可能不好截取
• 对于节点的编号问题，$siftup$过程中即可维护，交换的同时，把二者$id$一块换了就行，这里的$id$指的是堆中的编号
• 堆中父节点和子节点的编号关系和二叉树是一样的，所以判断两个节点是否的兄弟节点，判断他们的编号$/2$之后是否相等，父子之间的关系也是用$/2$这个操作判断
• 代码链接?

013 - 红色警报

• 如果我们把每次摧毁一个城市，看作从城市群中孤立出一个点，那么每次摧毁操作理论上不破坏原先联通关系的话，连通块的数量只会增加$1$，但是假如我们摧毁某个城市后，连通块数量增加超过$1$我们就发出警报
• 每次摧毁过后，更新一下摧毁关系，再重新遍历图即可，千万别忘了摧毁之后不连通度＋1
• 联通关系我们用$dfs$图遍历求解，摧毁要看作独立出一个连通块，要不然一直不增加的话，能遍历的点不断减少，那不是永远也不拉警报了
• 代码链接?
• $dfs$计算图的联通度

014 - 列车调度

• 出站顺序是递减的，所以进站顺序如果是递减的话，我们就必须把这段分在不同的轨道中去，而给出的输入序列又是进站顺序反过来，所以就从求最长下降子序列变成了最长上升子序列。
• $1e5$的复杂度，$nlogn$求解即可
• 代码链接?

015 - 互评成绩

• 模拟题
• 代码链接?

016 - 愿天下有情人都是失散多年的兄妹

• 呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
• 对于每个人我们存储一下他的父母$ID$，和自己的性别。
• 对于每次询问，先根据性别判断，然后因为题目保证了二者同辈，所以我们直接往上搜四代即可，每次判断两个父母四种组合是否为同一个人，利用$dfs$完成即可
• 题目还有一个小坑点就是，他可能会询问某个人的父母亲，所以我们记录性别的时候也要记录父母$ID$的性别，有点离谱，都是父母生孩子了，你还纠结人家是不是五服干哈…
• 代码链接?

017 - 人以群分

• 白给模拟

018 - 多项式A除以B

• 模拟题，模拟多项式的除法，用数组存一下指数和对应系数的关系，下标作为指数，值就是系数
• 分别记录一下当前多项式的$A,B$的最高次数，当$A$的最高次数$\ge B$的最高次数时一直进行除法
• 每次都是从高项到$A,B$指数之差的项，枚举更新余式的系数即可
• 然后每次消掉最高项之后，不断更新最高项，只能被舍掉或者等于$0$就一直往低次幂更新最高项即可
• 细节模拟题，不要怕做，细心一点，考虑好再写，代码量也不大
• 每次更新的项相差的下标就是二者最高次幂的指数差
• 代码链接?

019 - 悄悄关注

• 模拟题
• 代码链接?

020 - 功夫传人

• 根据题目的信息，我们可以知道，传授关系就是棵树，所以直接建树，$dfs$遍历更新即可，走到得道者节点就是更新一下答案。
• 代码链接?

021 - 点赞狂魔

• 模拟题，直接按照题意实现即可
• 代码链接?

022 - 重排链表

• 感觉比前面那个链表题还要简单一些，也是同理下标存放地址，记录一下$next$即可
• 需要注意就是把前连向后，但是要注意整个链表的长度是奇数还是偶数，其分别对应了不同的末尾处理方法
• 代码链接?

023 - 图着色问题

• 图着色问题是一个著名的NP完全问题。给定无向图$G=(V,E)$，问可否用$K$种颜色为$V$中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。
• 两个合法性判断
• ① 使用的颜色种类数必须是$K$个
• ② 相邻顶点不得染同样的颜色，$dfs$遍历一边即可，需要注意的是先判断颜色是否相同，在判断是否访问过，一个点可以和多个点相邻，对于所有的相邻点都要满足关系嘛
• 代码链接?

024 - 部落

• 在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
• 并查集，规定每个社区中的其他人都和该社区中第$1$个人合并
• 最后遍历所有出现过的点，确定部落个数，查询之前看根节点是否一致即可
• 代码链接?

025 - 分而治之

• 分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。
• 打击过后的城市标记一下，然后对于每一个方案直接暴力判断就可以
• 代码链接?

026 - 小字辈

• $dfs$求树的节点的深度即可
• 代码链接?

027 - 名人堂与代金券

• 直接模拟题意即可

028 - 秀恩爱分得快

• 也是题意模拟
• 但是有个坑点就是会有$?0$的存在，所以要用字符串读入照片中每个人的编号，但是我一开始犯了这个错误，但是不想改了，就没代码贴了

029 - 特立独行的幸福

• 也是按照题意模拟嘛，某个数如果再迭代的过程中被访问到了标记成$false$代表它依赖于别的数，每个数迭代的时候把迭代产生的数扔到$set$里，再次出现代表死循环出现，直接退出即可，标记为$false$
• 素数判断，提前筛一下就好
• 代码链接?

030 - 冰岛人

• 和之前$016$差不多，也是存一下性别和父母编号，性别是从名字中截取即可，父母的名字也是从字符串中截取，只不过相较于前面的编号标识，这里是用名字唯一标识，所以我们用$map$存一下即可$map<string,pair<int,string>>$代表自己的性别和父亲外地人父亲存成空即可
• 这里还有一个细节，二者并不一定同辈，就是题目中特别提到的五代以内的解释，对于这个五代以内的判断，我们直接暴力往祖先去枚举，看两个人是否有五代以内的共同祖先，这里题目的意思是，假如A的100代祖先是B的1/2/3/4代祖先都称作五代以内，所以我们判断必须A和B的祖先都枚举到5代及以上，才能算作没有祖先。 也就是在五代以内，只需要在某一个人五代以内就算而不是都在。
• 外地人不受任何限制
• 和树上节点的$lca$差不多一个意思，两个节点的深度并不一定相同
• 因为只有$5$代可以暴力找一找，虽然感觉理论复杂度也是超的，但是能过
• 建树不好建，因为不一定都处于一个联通块内，而且祖先节点也不好确定
• 也算是考察了$STL$的应用
• 代码链接?

031 - 深入虎穴

• 根据题目描述我们应该可以知道，最后这些门和道路的关系就是一棵树树上节点和边的关系，不过就是题目没规定入口即根节点是哪个，所以记录一下每个点的出度，出度为$0$的即为根节点
• $dfs$遍历一下记录最大深度即可
• 代码链接?

032 - 彩虹瓶

• 一个栈操作的模拟题，注意下每次操作的先后顺序即可，一定先从货架上看有没有适合当前颜色的货物，有就一直先填上
• 代码链接?

033 - 简单计算器

• 也是个栈模拟操作题
• 注意一下除数为0的情况即可
• 代码链接?

034 - 口罩发放

• STL模拟题
• 这种冗长的题目一定注意唯一标识某个人的信息是啥，题目说是身份证号，那我们就用$map$记录一下每个身份证上一次领口罩的时间是什么时候，当他身份证合格的时候，检查如果发放过口罩并且间隔时间不符合题目要求就$pass$
• 最后输出身体状况不是很好的人的编号，只要是为$1$就输出，不管有没有为他分配过口罩
• 细心点就行
• 代码链接?

035 - 完全二叉树的层序遍历

• 给出后序遍历序列，完全二叉树，那就左儿子$\times 2$，右儿子$\times 2+1$，递归建树就完事了，节点编号$>n$后直接返回，然后层序输出
• 代码链接?

036 - 网红打卡攻略

• 给出的旅游路线，代表路线必须这么走，而且必须挨着走（从题意理论上感觉读不出来有这层意思），这样的话直接邻接矩阵存图，每次给出路线直接看有路可走嘛
• 只能说天梯赛的L2如果不是很明显的算法知识，还是优先考虑暴力，毕竟好写
• 代码链接?

037 - 包装机

• 我们可以发现，每个货道符合先进先出的概念，那就是一个队列结构，而储物的就是一个栈结构，所以用$stack,queue$模拟操作一下即可
• 代码链接?

038 - 病毒溯源

• 又是一个树遍历问题，按照最小字典序输出，那我们用$vector$存图，然后把一个节点的子节点排一下序，递归遍历的时候就能达到先走数值的小的节点效果，先处理一下各个节点的深度值，然后遍历到一个答案之后直接退出即可
• 代码链接?

039 - 清点代码库

• 难点就是对一个序列按照字典序排序，理论上我们好像可以自己重写一下数组的排序函数然后排就行了，然后出现次数可以哈希一下判断，但是咧，如果我们用$vector$存就会发现，$vector$的大小比较就是如此进行的，而且$map<vector<int>,int>$可以直接记录某个$vector$的出现次数
• 这里只实现了$vector$的方法，数组的方法我看看补一补
• 如果某场比赛没碰到STL题目，我觉得可以考虑一下STL有没有具有如此功能的封装好的数据结构
• 代码链接?
• $vector$的比较就是序列字典序比较

040 - 哲哲打游戏

• 题意模拟
• 记录一下当前点能到达的各个游戏点即可，比前面三道都简单
• 代码链接?

OK，收工！

阅读世界，共赴山海

423全民读书节，邀你共读