完全背包 完全背包：与01背包唯一的区别是——每种物品有无限件，可以拿任意多个。 二维数组的写法： 01背包： 完全背包： 滚动数组优化： 01背包： 完全背包： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 状态定义： > dp[i][j] 加选第 i 件物品放入一个容量为 j 的背包可以获得的最大价值。假设现在背包的容量为5。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 完结 9.29第一稿 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 对于最小生成树，我将会从一下几个角度进行讲解 目录 * 1.并查集 * 2.最小生成树的概念 * 3.最小生成树的性质 * 4.算法---KRUSKAL * 5.算法---PRIM * 6.附：算法对比 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、并查集 把并查集拆开看： “并”，顾名思义就是合并； “查”，顾名思义就是查找； “集”，还是顾名思义就是集合。 可以把集合理解成几个本互不相干的部落，那么刚开始每个部落的首领就为本身。 而合并，可以理解为两个部落打架，输的一方被赢的一方吞并。 查找，即查找某个部落的首领。针对上一张表，可得出以下结果 其实细心的人会发现，这张图表十分像树，那么我们可以通过数组 fff 来存储并查集， fif_ifi 表示第 iii 个节点（部落）的父节点（首领）。 接下来上干货： 查找实际上就是从节点开始，一步步往上找，直到找到最终的父节点，可以用以下函数实现。 由于函数通过数组直接返回节点父节点值，无需复杂计算，所以该函数时间复杂度为 O(n)O(n)O(n) ，近似于感人的 O(1)O(1)O(1) 。 合并就简单了，只要将两个节点的父节点都改成相同的即可。 此代码执行过后，find(f[13])=find(f[21])。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、最小生成树的概念 要理解最小生成树，我们先要明白什么是“生成树”。 图：由一组顶点和连接顶点的边组成。 连通图：图中任意两个顶点之间都存在路径。 树：一个没有环的连通图。 生成树：一个连通无向图的生成树是它的一个连通子图，它包含原图的所有顶点，但边数最少（恰好有 n−1n-1n−1 条边，其中 nnn 是顶点数），并且没有环。 简单来说，生成树就是用最少的边把图中所有的顶点都连通起来，并且保证没有回路。 举个例子： 想象一个城市网络，每个顶点代表一个城市，边代表城市之间的道路。这个城市网络本身可能有很多条路，甚至有多条路连接相同的两个城市（形成环）。那么，这个网络的一个“生成树”就是一套能让你从任何一个城市开车到任何其他城市，且道路数量最少的路线规划。这套规划里不会有“环路”或“冗余的道路”。 现在，我们给图的每条边加上一个权重的概念。权重可以代表距离、成本、时间等。 最小生成树就是：在一个带权连通无向图中，总权重和最小的那棵生成树。 继续上面的例子： 现在每条道路（边）都有修建成本（权重）。我们想找出一套道路规划，既能连接所有城市（生成树），又使得总的修建成本最低。这套规划就是这个城市网络的最小生成树。 核心目标：在保证所有点连通的前提下，选择总权重最低的边。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、最小生成树的性质 * 唯一性：最小生成树不一定唯一。当图中存在多条权重相同的边，并且可以互换时，就可能产生多个不同的最小生成树，但它们的总权重是相同的。 * 边数：任何最小生成树都必然包含恰好 n−1n-1n−1 条边（ nnn 是顶点数）。 * 环性质：在最小生成树中，任意加上一条原本不在树中的边，都会形成一个环。并且这个环上新加入的那条边，一定是环上权重最大的边（否则就可以用它替换掉环上更大的边，得到更小的总权重，与“最小”矛盾）。 * 切割性质：把图的顶点分成任意两个集合（一个切割），连接这两个集合的权重最小的边，必然属于图的最小生成树。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、算法---KRUSKAL 核心思想：将所有边按权重从小到大排序，然后依次考虑每条边。如果加入当前边不会与已选择的边形成环，就将其加入生成树；否则就跳过。 * 排序：把所有边按权重从低到高排好。 * 检查：从权重最低的边开始检查，如果加上这条边不会使原来的树形成自环，就加入这条边 * 重复：直到修好了 n−1n-1n−1 条路。 关键技术：如何高效判断加入一条边是否会形成环？使用并查集数据结构。 第一部分没有好好看的只能重看了哈哈哈{\color{yellow} 第一部分没有好好看的只能重看了哈哈哈}第一部分没有好好看的只能重看了哈哈哈 初始时，每个顶点自成一个集合。 当考虑一条边的起点 uuu 和终点 vvv 时，检查 uuu 和 vvv 是否在同一个集合中。 如果在，说明加入这条边会形成环，舍弃。 如果不在，则加入这条边，并将 uuu 和 vvv 所在的集合合并。 时间复杂度：排序边需要 O(m log m)O(m\ log\ m)O(m log m) ，而并查集操作近乎常数时间，所以主要复杂度为 O(m log m)O(m\ log\ m)O(m log m) ，非常适合稀疏图，其中 mmm 为边数。 这是一道模板题 题解： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、算法---PRIM 核心思想：从某一个顶点开始，每次选择一条连接已构建的树 与未加入树的顶点的权重最小的边，并将该边和对应的顶点加入到树中。 * 起点：随便选一个顶点。 * 生长：每次从这棵树向外延伸出最小权重的边，把一个新的点连进来。 * 重复：直到所有的点都被连入这棵树。 适用数据结构：通常使用优先队列（最小堆） 来高效地获取当前可用的最小边。 时间复杂度： 使用邻接矩阵和简单遍历：O(n2)O(n²)O(n2) ，适合稠密图。 使用邻接表和二叉堆：O(m log n)O(m\ log\ n)O(m log n) ，适合稀疏图。(一般直接用Kruskal，很少用） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 六、附：算法对比 特性 Kruskal Prim 核心思想 加边法，按权重从小到大选择边 加点法，从一点出发逐步扩张树 数据结构 并查集 + 边排序 优先队列（最小堆） 时间复杂度 O(m log m)O(m\ log\ m)O(m log m) O(m log n)O(m\ log\ n)O(m log n) 或 O(n2)O(n²)O(n2) 适用场景 稀疏图（边较少时效率很高） 稠密图（边很多时，用邻接矩阵可能更快） 图是否连通 需额外检查是否有 n−1n-1n−1 条边来判断图是否连通 算法过程自然保证连通性 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 制作不易，给个赞吧

背包问题 dp经典应用-背包问题 一般来说，就是给定一组有固定价值和固定重量的物品， 以及一个承重量固定的背包， 求在不超过背包最大承重量的前提下， 能放进背包里面的物品的最大总价值。 01搜索 01背包，完全背包 有n件物品和一个容量为v的背包。 第i个体积为 wi 价值wi，每件物品只有一件，只能选或者不选， 求不超过容量的前提下能获得的最大总价值。 状态定义： f[i][j]=前i个物品，容量为j时的最大值； 选第i件物品，容量够，则f[i][j]=f[i-1][j-w[i]]+v[i] 不选第i件物品，f[i][j]=f[i-1][j]; f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i-1][j])

背包DP 动态规划的经典应用-背包问题。 一般来说，就是给定一组有固定价值和固定重量的物品，以及一个承重量固定的背包，求在不超过背包最大承重的前提下，能放进背包里的物品的最大总价值。 动态规划（DP）类问题主要求解的步骤 1、划分阶段 2、确定状态 3、确定决策并写出转移方程式 贪心为什么错？ 根本原因：贪心需要算性价比（单位重量的价值），但题中的物品不可分割，所以计算性价比来排序的策略是错的。 所以，可以考虑01搜索，对每个物品遍历“选 or 不选”两种情况，但是可能会超时。 背包问题分类：01背包，完全背包，多重背包，分组背包…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 01背包 问题定义：有 n 件物品和一个容量为 v 的背包，第i件物品体积 wi ，价值 vi ，每件物品只有一件，只能选或不选，求不超过容量的前提下能获得的最大总价值 状态定义： > dp[i][j] 表示前 i 个物品，容量为 j 时的最大价值 状态转移： > 选第 i 件物品且容量够，则 dp[i][j] = dp[i - 1][j - w[i]] + v[i] > 不选第 i 件物品，则 dp[i][j] = dp[i - 1][j] > dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]) 答案： > 一般来说，dp[n][m]; 实现代码： 滚动数组优化： 每次都是覆盖上一行，尝试是否可以使用一维数组进行实现。 确定状态：dp[j] 表示背包容量为 j 时的最大价值。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 当数据量过大时，用 cin 和 cout 读写较慢，可以用 scanf 和 printf 进行格式化输入输出 换行一定要用 \n 代替 endl 啊 二分用 (l+r)/2 找中间数是个不好的习惯，可能会导致 l+r 数溢出导致变为负数，随后除以二会 mid 也是一个错误的负数索引，从而导致数组越界访问或程序崩溃，可以用 int mid=l+((r-l)>>1)，不过位运算的优先级没加减乘除的优先级高，所以一定要加括号 牢发竟然没教我们 #define int long long 有时候也是个好东西，不过你 main 就要改 signed 类型了 上面的拉完了，不如 using ll=long long; for 循环遍历似乎 ++i 性能比 i++ 好？ 再难的题你哪怕不会，良心（吗？）的出题人也会给你 30% 左右的分让你暴力的 观察完全二叉树，其最后一个结点编号为 nnn ，其父亲结点的编号为 n/2n/2n/2 ，所以从 n/2n/2n/2 开始的结点都是叶子结点，因此结点数为 nnn 的完全二叉树其叶子结点个数为 n−n/2n-n/2n−n/2 个 二维前缀和数组 s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]; 二维前缀和求从 (x1,y1)(x1,y1)(x1,y1) 到 (x2,y2)(x2,y2)(x2,y2) 的元素和 ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] 虽然但是，似乎没啥用 QAQ

答案解析： 2（你不会没做对吧）

字符串 【算法漫笔001】KMP、EXKMP 【算法漫笔002】字符串HASH 【算法漫笔003】KMP自动机+DP 【算法漫笔005】MANACHER 图论 【算法漫笔004】同余最短路 数论 【算法漫笔006】盒子与球 DP的新系列在做了！

#include<bits/stdc++.h> using namespace std; const int maxn = 114514; int a[maxn], b[maxn], n, len, m; int check(int mid){ int cnt = 0; int i = 0, now = 0; while(i < n+1){ i++; if(a[i] - a[now] < mid){ cnt++; }else{ now = i; } } if(cnt <= m) return 1; return 0; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> len >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; a[0] = 0, a[n+1] = len; if(n == 0){ cout << len; return 0; } } long long l = 1, r = len; while(l < r){ int mid = (l+r+1)>>1; if(check(mid)) l = mid; else r = mid - 1; } cout << l; return 0; }

循环+数组

#include <bits/stdc++.h> using namespace std; int a,b,c; int main(){ cin>>a>>b>>c; if(a>0){ cout<<a<<endl; } if(b>0){ cout<<b<<endl; } if(c>0){ cout<<c<<endl; } return 0; }

T1 前缀和 题目大意 给定一个长度为 n 的数组，有 m 次询问。 每次询问： 求区间： 如果每次都遍历区间，最坏复杂度是 O(nm)。 可以提前预处理前缀和。 核心思路 定义： 表示： > 前 i 个数的总和。 所以： 相减： 代码 复杂度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2 异或前缀和 题目大意 给一个数组，多次询问区间： 所有元素的异或值。 核心思路 普通前缀和使用减法： 异或有一个重要性质： 定义： 那么： 前面的数字出现两次，会全部抵消。 所以： 代码 复杂度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3 奖学金 题目大意 每个学生有： 排序规则： 1. 总分高的在前； 2. 总分相同，语文高的在前； 3. 语文也相同，编号小的在前。 最后输出前 5 名。 核心思路 这是典型的： > 结构体 + 自定义排序。 把每个学生的信息放进结构体。 比较函数直接按照题目要求写。 代码 复杂度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4 第一个大于 X 的数 题目大意 给定一个升序数组。 找到： > 第一个严格大于 x 的元素位置。 也就是找最小的 i： 核心思路 二分答案。 如果： 说明 mid 有可能是答案，但是左边可能还有更早的位置： 否则： 代码 复杂度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5 第一个大于等于 X 的数 与上一题只有一个区别。 这一题找： 代码 两道二分一定要区分 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6 撤硕管理员 这题是典型的： > DFS 选或不选。 题目要求从 n 个同学中选择任意一些，使选择的费用总和是质数，求方案数量。([ACGO][1]) 核心思路 枚举到第 id 个同学，有两种选择： 所以： 到最后判断： 代码 复杂度： 核心模板： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T7 全排列问题 题目大意 输出： 的所有全排列。 要求每个数字占 5 个字符宽度。([ACGO][2]) 核心思路 定义： 表示排列第 x 个位置放什么。 vis[i]： 每一层 DFS 枚举： 代码 核心口诀： 复杂度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T10 [CSP-J 2025] 多边形 题目条件是： 若选择的最大木棍为 mx，总长度为 sum，则必须满足： 题目保证 n<=5000，a[i]<=5000。([ACGO][4]) 核心思路 先排序： 假设： 是当前方案中的最大边。 那么条件： 移项： 所以问题变成： > 从前 i-1 根木棍中选择若干根，统计子集和大于 a[i] 的方案数。 定义： 表示： > 当前已经处理过的木棍中，选出的木棍长度和为 j 的方案数。 因为最大 a[i] 只有 5000，所以所有： 的和统一存到： 即可。 代码 复杂度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T11 [CSP-J 2022] 上升点列 这题核心是： > LIS + 二维 DP。 将所有点按照： 排序。 对于两个点： 如果： 就可以连接。 两个点的曼哈顿距离： 中间需要添加： 个点。([ACGO][5]) 状态 表示： > 以第 i 个原有点作为结尾，已经使用了 j 个新增点时，最长点列长度。 代码 复杂度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T12 [CSP-J 2019] 纪念品 这题是非常经典的： > 每两天之间做一次完全背包。 每天可以买同一种纪念品无限次，因此属于完全背包。([ACGO][6]) 核心思路 考虑第 i 天买，第 i+1 天卖。 第 j 个纪念品： 收益： 当前拥有 m 枚金币： 于是做一次完全背包，求最大利润。 然后： 继续处理下一天。 代码 复杂度： 最关键： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T13 [CSP-J 2020] 方格取数 这题的移动规则决定了： > 只能不断向右进入下一列，但是在同一列中可以向上或向下移动。 所以不能只写普通： 因为同一列可能： 也可能： 因此每一列需要做两遍 DP。该题是 CSP-J 2020 T4。([ACGO][7]) 状态 表示： > 到达 (i,j) 时能获得的最大价值。 对于每一列分别： 代码 复杂度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

0-1背包问题 概念部分 定义： 为什么不适用贪心： 状态设计： 转移方程： 二维背包模板代码 题目描述 辰辰要进山采药。山洞里有 M 株草药，采摘第 i 株需要花费 w [i]单位时间，采到后能得到 v [i]的价值。 他总共只有 T 单位时间。每株草药要么完整采下来（花掉对应的时间），要么干脆不采，不能只采一部分。 请问在时间用完之前，他最多能采到多少价值的草药？ 输入格式 第一行两个整数 T 和 M，用一个空格分隔，分别表示总时间和草药数目。 接下来 M 行，每行两个整数 w [i]和 v [i]表示第 i 株草药的采摘时间和价值。 输出格式 一行一个整数，表示在规定时间内能采到的最大总价值。 滚动数组优化(一维DP的优化） 观察转移方程： 滚动数组优化代码模板 ： 题目描述 Bessie 要给自己的手链挑饰品。手链能承受的总重量上限是 M。 现在有 N 个候选饰品，第 i 个重 W [i]，能带来 D [i]的魅力值。每个饰品最多只能用一次。 请问在不超过重量上限的前提下，手链的魅力值总和最大是多少？ 输入格式 第一行两个整数 N 和 M，分别表示饰品个数和手链的重量上限。 接下来 N 行，每行两个整数 W [i]和 D [i] ，表示第 i 个饰品的重量和魅力值。 输出格式 一行一个整数，表示能获得的最大魅力值总和。

不是出题人fm4光光了吧! 这题纯浪费时间啊！

01背包：有 n 件物品和一个容量为 V 的背包。第 i 件物品体积为 wi，价值为 vi，每件物品只有一件，只能选或者不选。求不超过容量的前提下能获得的最大总价值。 1.状态设计：dp[i][j] 表示，前 i 件物品中，容量为 j 时的最大价值。 2.转移方程： · 如果选第 i 件物品，dp[i][j] = dp[i - 1][j - w[i]] + v[i]； · 如果不选第 i 件物品，dp[i][j] = dp[i - 1][j]； 3.滚动数组优化：状态数组的空间开销，与物品个数、背包容量有关，很容易空间超限。于是考虑优化空间开销，用一维数组来实现状态数组。 观察转移方程：发现第 i 行的数值只依赖于第 i-1行，既然前面的都用不上，就把二维压缩成一维，反复覆盖使用。 方法技巧：通过反向遍历避免重复取值 例题： A85.采药 错误思路：贪心（性价比） 错误原因：物品不可分割 反例： 假设背包容量为10， 若按贪心思路，应选择①，总价值为7； 而正确答案应选择②③，总价值为10。 物品 体积w 价值v 性价比 ① 6 7 1.17 ② 5 5 1.00 ③ 5 5 1.00 正解： A573.装箱问题 观察到：数据范围不足以支持二维数组，会MLE，因此采用滚动数组优化 代码：

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个最小值 1.2 题目背景、允许、禁止与限制 背景： 有一棵 nnn 个节点的树，初始时 111 号节点被染黑，其它节点均为白色 允许： 初始时 BBB 在 111 号节点 →\rightarrow→ 间接地说明了 111 号节点是根节点 每一轮，AAA 可以先染黑 kkk 个节点，然后 BBB 可以走到相邻的任意节点，如果 BBB 在白色节点则 BBB 胜，当 AAA 将所有节点染为黑点时则 AAA 胜。 求让 AAA 胜利的最小 kkk 1.3 题目数据范围与猜测 n≤3×105⟶O(n log n)n \le 3 \times 10^5 \longrightarrow O(n~log~n)n≤3×105⟶O(n log n) 1.4 一句话概括题意 有一棵树，求一个最小值使得在游戏规则下 AAA 必胜 2 题目破题推导 2.1 第一步：大拆小，小组大 我们考虑一个节点 uuu 的“威胁”，也就是在 uuu 的子树中，还需要额外染黑的节点数量 * 第一部分：本身欠的（有可能欠负数，也就是不仅可以染孩子，还可以染孩子的子树中需要染黑的） 设 s(i)s(i)s(i) 代表 iii 的子节点数量，则这部分带来的“威胁”值为 s(u)−ks(u) - ks(u)−k * 第二部分：孩子节点需要补的 设 f(i)f(i)f(i) 表示 iii 的子树中，还需要额外染黑的节点数量，son(i)son(i)son(i) 代表 iii 的所有孩子 则这部分为：∑v∈son(u)max(f(v),0)\sum_{v\in son(u)}max(f(v),0)∑v∈son(u) max(f(v),0) 为什么是 max(f(v),0)max(f(v),0)max(f(v),0)，而不是 f(v)f(v)f(v)？ 因为子节点的“威胁”如果是负数，不能用于补充父节点“欠”的，只能补充 vvv 自己的孩子所欠的 3 模型匹配 这题特别重要的一个转换点： 很多时候，我们看到求一个最小值，就理所当然认为这是dp 但是这道题并没有使用dp求这个最小的k 而是使用了二分答案，树形dp只是一个辅助工具 那么我们的dp定义其实和上面的 f(i)f(i)f(i) 一样 然后当我们测试完这个 kkk 后，若 dproot(1)≤0dp_{root(1)}\le 0dproot(1) ≤0，则代表合法 4 最终代码（禁止抄袭，仅用于参考）

为何不对

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个最小值和最小值对应的可行方案 1.2 题目背景、允许、禁止与限制 背景： 国家中有 NNN 个人 国家中的人成如下关系：111 个国王（没有上级），N−1N-1N−1 个人，如果 AAA 是 BBB 的上级，BBB 是 CCC 的上级，则称 AAA 也是 CCC 的上级 允许： 现在有条消息，你作为国王要传播这条消息 使用 111 单位时间将这条消息传播给 111 个人（之前被传播过消息的人也可以同时传播给其直接上级或直接下级）→\rightarrow→ 发现这两种情况貌似都是“沿着边传播”！所以其实本质上不用考虑“传播给直接上级”，因为可以被“传播给直接下级”平替 求最短需要多少单位时间可以把这条消息传播给所有人，以及从哪些点（也就是以哪些点为根节点）开始传播可以达到这个最短时间 1.3 题目数据范围与猜测 n≤1000⟶O(n2)n \le 1000 \longrightarrow O(n^2)n≤1000⟶O(n2) 1.4 一句话概括题意 有一棵树，求这棵树上沿边传播消息的最短时间 2 题目破题推导 2.1 第一步：画图模拟+贪心思路 画一颗这样的树 发现只有这样的传播顺序，才能使整体耗费时间最短 那么我们有个基本贪心思路：传播顺序是按照子树内部传播时间从大到小 2.2 第二步：证明贪心思路 传播时间越长的子树越应该先被通知，因为早点开始可以让它的"长耗时"和"等待时间"重叠，从而减少总体时间。 类比现实生活：如果有多个任务要分配，最耗时的任务应该最先开始，这样总完成时间最短——这就是流水线调度中的经典贪心策略（Johnson法则的简化版） 这里不写数学证明了，自己思考 3 模型匹配 树形结构、最短时间、多次求答案--> 树形dp 设 dp[i]dp[i]dp[i] 为以 iii 为根的整棵子树都被传播到的最小时间 刚刚我们已经知道了传播的顺序 那对于这个点，整体传播完时间究竟是多久呢？答案是： minv是u的孩子(dp[v]+i(v是第几个被u传播的)−1)\underset{v是u的孩子}{min}\left(dp[v] + i(v是第几个被u传播的) - 1 \right) v是u的孩子min (dp[v]+i(v是第几个被u传播的)−1) 4 最终代码（禁止抄袭，仅用于参考）

代码： #include<bits/stdc++.h> using namespace std; int main(){ int m,n; cin>>m>>n; for(int c=1;c<=10000;c++){ if(c%m0&&c%n0){ cout<<c; break; } } return 0; }

代码： #include<bits/stdc++.h> using namespace std; int main(){ int n,i; cin>>n; for(int c=0;c<n;c++){ cin>>i; if(i%10<=4){ cout<<i-i%10<<endl; } else{ cout<<i-i%10+10<<endl; } } return 0; }