摘要： 形式化题意 给定一个带权无向图，求从 \(s\) 点到 \(e\) 点的路径上途径边权种类的最小值. 思路 题图 我们把边权种类相同的点连成的子图抽象成一个 "平台" ，从题目给我们的图中可以看出来，\(1\) 到 \(6\) 的过程其实也是不断上平台与下平台的过程. 从 \(1\) 点上绿平台，走 阅读全文

摘要： 夫史之称美者，以叙事为先，至若书功过，记善恶，文而不丽，质而非野，使人味其滋旨，怀其德音，三复忘返，百遍无致 语 林史·语其一 林史·语其二 林史·语其三 林史·语其四 林史·语其五 林史·语其六 林史·语其七 林史·语其八 林史·语其九 林史·语其十 纪事本末 林史·HEOI2024 林史·CLO 阅读全文

摘要： 初步分析 此题描述让我们想到Tarjan求割点，因此我们从割点的角度来探讨一下这道题. 假如我们去掉的不是一个割点，那么它实际上不会对连通性造成影响，但是根据样例可以看出来，删去这个点导致了其余点与当前点无法联通，即答案为 \(2\ (n-1)\). 假如我们去掉的点是一个割点，那么它必然会将整张图 阅读全文

摘要： 题目链接 T415418 这道题严格的时间限制比较令人头疼，似乎需要一些高级的算法，但实际上是，想要用点基础知识通过这道题需要两种算法：费马小定理 (见下函数Miller_rabin) 用于subtask1,另一种算法 (见下函数prim) 用于subtask2.两个subtask的范围限制给了我们 阅读全文

摘要： 题解引用 引理1: 区间 \([l,r]\) 是最优解的必要不充分条件是: \(l,r\) 分别是区间的最小值与最大值. 这很显然，若假设不成立，当区间向内缩小时，一定有分子不变，分母变小，进而算出更优解，与假设矛盾. 引理2: 最优解不小于 \(x\) 的充要条件为存在区间 \([i,j]\)，使 阅读全文

摘要： 题目描述 给出 \(N\) 个正整数 \(a[1..N]\) ，再给出一个正整数 \(k\) ，现在可以进行如下操作：每次选择一个大于 \(k\) 的正整数 \(a[i]\) ，将 \(a[i]\) 减去 \(1\) ，选择 \(a[i-1]\) 或 \(a[i+1]\) 中的一个加上 \(1\) 阅读全文

摘要： 题目描述 有一个整数组成的矩阵，现请你从中找出一个指定边长的正方形区域，使得该区域所有数中的最大值和最小值的差最小。 题目分析 其实这道题和滑动窗口很像，而滑动窗口使用优先队列解决. 我们都知道优先队列可以维护区间最值. 但是优先队列维护的区间不是二维的，而是一维的. 因此，这道题我们的思考方向，一 阅读全文

摘要： 实际上这题很难和树状数组联系起来，我感觉效率也不是很高，感觉不是正解 怎么使用树状数组 这道题我们很容易想到一点：同种物品在一个区间内只能出现一次，先不考虑别的问题，我们想出下面这种使用树状数组的思路： 定义树状数组只有 \(0\) 和 \(1\) 两种状态，分别表示统计这个物品或不统计这个物品. 阅读全文

摘要： 什么是Markdown，Katex Markdown 是一种使用标记辅助文章排版的语言，而 Katex 是一种数学公式的格式. 它们可以让你的博客看起来更舒服. Markdown 可以直接使用，但在你使用 Katex 之前，请先到 你的博客设置 中勾选 “启用数学公式支持”.另外，强烈建议将下方“默 阅读全文

摘要： 温馨提示：Contest 大字的右侧有目录可以快速跳转 Contest 背包DP 线性DP 区间DP 坐标DP 树形DP 状压DP 概率与期望DP 计数DP 单调优化DP 背包DP 背包DP可以理解为“从若干物品中选择特定物品”的问题的统称. 对背包问题开dp数组，通常需要考虑以下几个维度 已选物品 阅读全文