今天主要学习了提高组复赛知识点：并查集和相关的最小生成树。复习了最短路的一些相关算法。 一.并查集和最小生成树 并查集，最喜欢找爹的一集。 也就是查找最近公共祖先的算法。 也就是在图论中找父亲节点。 但是仔细想想，一个一个节点的遍历过去时间复杂度太高了，所以就有了所谓“路径压缩”。 听起来很诡异，但其实做法非常简单。 看图：链接描述 所谓路径压缩，就是在查找祖先节点的过程中，将自己的父节点转换为父节点的父节点的父节点的..... 这个查找的过程是递归，递归要有截止条件，其截止条件就是当前的节点，它没有父节点/父节点就是自己（根据初始化不同而不同）。 模版代码： 与其相关的还有最小生成树，那个在此不进行解释（没时间了，还要默模版） 最小生成树模版：链接描述 二.最短路问题 DIJKSTRA 对于这个算法不多进行解释，详情请见坐着的其他文章。 模版：链接描述 SPFA 模版：链接描述 FLOYD(阴间版） 模版：链接描述

这题数据有问题，10个有9个“NO”，只有一个“YES”还和样例一样； 所以我们可以这么过

改了范围 -> 做对后 再改过来 纯乐子一枚

1.《惊封》 2.《天官赐福》 3.《一屋暗灯》 4.《二哈和他的白猫师傅》 5.《庄周梦蝶》 【关注】 【粉丝】！！！

12 何礼贤 倒4 13 王胜楷 倒3 14 朱允升 倒2

我为了跟随周围人的节奏，建立了一个全新的团队，现在正式开始招人，欢迎大家光临我的团队 入队

回答我！look my eyes! tell me why?

若你们关注loaking✈，loaking✈一定反关

呵呵呵，集训的第五天到了，前五天跟过了5个世纪一样，我直接被恶心到了，我的学习理念是：用心聆听，wa声争鸣

我当时脑子一热，写了210个测试点 题目

DIJ 01DFS

快点我

今日大法：关机大法，当牢湿吧我们黑屏的时候，可以用关机大法，会脱离牢湿的管控。 缺点：不能用键盘。 等级：T2

https://www.acgo.cn/application/1812107348361400320

加油！！！！！！

加油！！！！！！

eeeeee-------

问题分析： 需要在 n×n 的方格中放置药水，满足每个 2×2 的子矩阵恰好包含 2 瓶药水，目标是最大化所有放置药水的法力值总和。 核心观察： 满足 "每个 2×2 子矩阵恰好有 2 瓶药水" 的放置方式存在两种基础模式，这两种模式能覆盖所有可能的最优解： 1. 行交替模式：对于每一列，选择要么在奇数行放置药水，要么在偶数行放置药水。这种模式下，任意 2×2 子矩阵会包含恰好 2 瓶药水（上下两行各 1 列选择不同）。 2. 列交替模式：对于每一行，选择要么在奇数列放置药水，要么在偶数列放置药水。这种模式下，任意 2×2 子矩阵同样会包含恰好 2 瓶药水（左右两列各行选择不同）。 算法核心： 分别计算两种模式下的最大可能法力值总和，取其中的最大值作为答案。 步骤分解： 1. 行交替模式计算（Family A）： o 遍历每一列，分别计算该列中所有奇数行（1-based）的法力值总和，以及所有偶数行的法力值总和。 o 对每一列，选择上述两个总和中的较大值，累加得到行交替模式的总法力值。 2. 列交替模式计算（Family B）： o 遍历每一行，分别计算该行中所有奇数列（1-based）的法力值总和，以及所有偶数列的法力值总和。 o 对每一行，选择上述两个总和中的较大值，累加得到列交替模式的总法力值。 3. 结果： o 行交替模式与列交替模式的总法力值中的最大值，即为满足条件的最大可能法力值。

问题目标：计算通过一系列合成操作后，编号为n的金属能达到的最大克重。 核心规则：每种金属的合成配方仅能使用编号更小的金属作为原料，且每种金属最多对应一种合成配方。 一、整体策略：二分查找 + 反向需求验证 1. 二分查找确定最大可能产量 * 原理：金属n的最大产量存在上限（所有金属初始总量之和），且“能否达到某一产量X”具有单调性（若X可行，则所有小于X的产量均可行），因此适合用二分法高效定位最大值。 * 范围：下界为金属n的初始克重（至少拥有这么多），上界为所有金属初始克重的总和（合成过程不会增加总质量）。 2. 反向需求验证判断可行性 * 核心逻辑：对于猜测的目标产量X，从金属n开始反向推导，计算每种金属需要提供的总量，最终验证基础金属（无合成配方的金属）的初始量是否能满足所有需求。 * 步骤： a. 假设金属n需要达到产量X，计算其缺口（X减去初始量，若为负则无需合成）。 b. 根据合成配方，将缺口转化为对其原料金属的需求量（每种原料需多提供与缺口等量的克重）。 c. 对每一种原料金属重复上述过程：若有配方则计算其缺口并传递给更低级的原料，若为基础金属则直接检查初始量是否满足需求量。 d. 若所有基础金属的初始量均能满足需求，则X可行；否则不可行。 二、特殊场景处理 1. 无效配方：若某配方的原料编号不小于产物编号，该配方无效，无法通过合成增加金属n的量，直接返回其初始量。 2. 金属n=1：此时无更小编号的金属可作为原料，无法合成，直接返回其初始量。 3. 基础金属初始量不足：若反向推导中某基础金属的需求量超过其初始量，则当前目标产量不可行。

问题分析： 需要判断每个嫌疑人是否能洗清嫌疑。判断标准是：如果嫌疑人无法在所有犯罪事件和自己的不在场证明之间进行合理移动（即移动速度不超过 1 单位时间 / 单位距离），则可以洗清嫌疑。 核心观察： 1. 犯罪者必须在所有犯罪事件发生时出现在对应地点。 2. 嫌疑人的不在场证明是其在特定时间的位置。 3. 若嫌疑人是犯罪者，那么他必须能在所有犯罪时间点之间以及与不在场证明时间点之间，以不超过 1 单位 / 时间的速度移动。 4. 只需检查嫌疑人与时间上相邻的犯罪事件是否能合理移动即可，因为如果能在相邻两点间合理移动，则能在所有点间合理移动。 算法核心： 1. 对所有犯罪事件按时间排序。 2. 对于每个嫌疑人的不在场证明，找到与其时间最接近的前后两个犯罪事件。 3. 检查嫌疑人是否能在不在场证明时间点与这两个（或一个）犯罪事件时间点之间合理移动。 4. 若存在任何一段无法合理移动，则该嫌疑人可洗清嫌疑。 步骤分解： 5. 数据预处理： o 读取所有犯罪事件的位置和时间。 o 按时间对犯罪事件进行排序，便于后续查找。 6. 处理每个嫌疑人的不在场证明： o 读取嫌疑人的位置和不在场证明时间。 o 根据时间找到该时间点前后的犯罪事件（利用二分查找提高效率）： o 若不在场证明时间早于所有犯罪时间，只需检查与最早的犯罪事件是否能合理移动。 o 若不在场证明时间晚于所有犯罪时间，只需检查与最晚的犯罪事件是否能合理移动。 o 若在中间，则检查与前后两个犯罪事件是否能合理移动。 7. 合理性判断： o 两点之间的欧几里得距离是否小于等于时间差（因速度≤1，距离≤时间差）。 o 为避免浮点数运算，比较距离的平方与时间差的平方。 8. 结果统计： o 若嫌疑人与任一相关犯罪事件之间无法合理移动，则计数加 1。 o 最终输出可洗清嫌疑的总人数。