题目链接 小红修道路 题目描述 给定一个带权无向连通图和  条从顶点 1 出发的计划修建的道路。问最多可以删除多少条计划道路，使得从顶点 1 到所有其他顶点的最短路径长度，与全部  条道路都修建时的情况相比，保持不变。 解题思路 这个问题的核心是找出哪些计划道路是“不可或缺”的，然后从总数中减去这些必要的道路。 我们可以将问题分解为两个主要步骤：   确定最终的最短路径：首先，我们需要知道在最理想的情况下（即所有  条计划道路都修建后），从顶点 1 到其他所有顶点的最短路径长度是多少。这是一个典型的单源最短路径问题，由于所有边权非负，我们可以使用 Dijkstra 算法来解决。我们在包含原始边...

题目链接 【模板】最小生成树 题目描述 给定一个包含  个顶点和  条边的无向连通图，边权均为整数。你需要求出该图的最小生成树（MST）。 输出要求：  最小生成树的所有边的权值之和。 构成最小生成树的边的原始编号（从 1 开始）。若有多种方案，输出任意一种。  解题思路 本题是求解无向连通图的最小生成树，是经典的图论问题。常用的算法有 Kruskal 和 Prim。考虑到本题需要输出构成 MST 的边的编号，使用 Kruskal 算法会更直观方便。 Kruskal 算法 Kruskal 算法是一种基于贪心思想的算法，其核心步骤如下：  边的排序：将图中所有的  条边按照权重从小到大进行排序。...

题目链接 【模板】单源最短路Ⅲ ‖ 非负权图 题目描述 给定一个包含  个顶点和  条边的有向赋权图，边权均为非负整数。指定一个起点 ，你需要计算从起点  到图中所有顶点的最短路径长度。  如果一个顶点无法从起点到达，则其最短路径长度为 。 起点到其自身的最短路径长度为 。  解题思路 本题是典型的单源最短路径问题，且所有边权均为非负，因此最适合使用 Dijkstra 算法 求解。由于图的规模可能较大，需要使用**堆（优先队列）**来进行优化，以达到题目要求的时间复杂度。 Dijkstra 算法（堆优化） Dijkstra 算法是一种贪心算法，用于寻找图中从单一源点到所有其他顶点的最短路径。其...

题目链接 【模板】单源最短路Ⅰ ‖ 无权图 题目描述 在一个有向无权图中，给定一个起始点，求它到图中所有顶点的最短路径长度。 解题思路 对于边权全部相等（或无权，可视为边权为1）的图，求解单源最短路径问题最适合使用广度优先搜索 (BFS)。 广度优先搜索 (BFS) BFS 算法的特点是逐层遍历。它从源点开始，首先探索所有距离为 1 的邻居，然后是所有距离为 2 的邻居，以此类推。这种按距离逐层扩展的搜索方式，天然地保证了当算法第一次到达某个顶点时，所经过的路径就是从源点到该顶点的最短路径。 算法流程   数据结构：  一个队列，用于存储待访问的顶点。 一个邻接表 adj，用于存储图的结构。 ...

题目链接 奶牛排排站 题目描述 在  个元素的全排列中，建立排列与它按字典序的排名之间的一一对应关系。需要支持两种操作：  Q 操作：给定一个排列，求出它的排名（从 1 开始）。 P 操作：给定一个排名，求出对应的排列。  这个问题是康托展开 (Cantor Expansion) 及其逆运算的典型应用。 解题思路 康托展开：排列求排名 (Q 操作) 康托展开的公式为：  其中， 表示在当前位右边（未出现的数字中）比第  位数字小的数字的个数。最终排名为 。 举例说明：求排列 {1, 2, 5, 3, 4} 在  的全排列中的排名。  第一位是 1：比 1 小的数有 0 个。贡献为 。 第二位是...

题目链接 绿豆蛙的归宿 题目描述 给定一个  个点、 条边的有向无环连通图（DAG）。起点为 ，终点为 。每条边  都有一个非负长度 。 当绿豆蛙位于顶点  时，如果该点有  条出边，它会以等概率（）选择其中一条边离开。 请计算绿豆蛙从起点  出发，到达终点  的路径总长度的期望值。 输入:  第一行输入两个整数 ，分别表示点数与边数。 接下来  行，每行输入三个整数 ，表示存在一条从  指向 、长度为  的有向边。 保证图是 DAG，且从  可以到达 。  输出:  输出一个实数，表示期望路径长度，四舍五入保留两位小数。  解题思路 这是一个在有向无环图（DAG）上求期望的经典问题，可以使用...

题目链接 旺仔哥哥走魔法迷宫 题目描述 在一个  的矩阵中，每个格子都有一个魔力值。从一个起始点开始，每次都等概率地移动到一个魔力值严格小于当前格子的目标格子。每次移动的得分是两点间欧几里得距离的平方。当不存在魔力值更小的格子时，移动停止。求总得分的数学期望。 解题思路 这是一个典型的期望动态规划 (Expectation DP) 问题。由于移动总是从魔力值大的格子走向小的格子，所以移动路径构成一个有向无环图 (DAG)，这保证了 DP 的可行性。 DP 状态与顺序  状态定义：设  表示从格子  出发，未来能够获得的总得分的期望值。 计算顺序：要计算格子  的期望值，我们需要知道所有它可能跳...

题目链接 超多面骰子 题目描述 给定一个有  个面的均匀骰子，求期望需要投掷多少次，才能使每一面都至少出现一次。 输入:  第一行一个整数 ，表示测试用例数量。 接下来  行，每行一个整数 ，表示骰子的面数。  输出:  对于每个测试用例，输出一行一个实数，表示期望投掷次数。  解题思路 这是一个经典的概率期望问题，通常被称为赠券收集问题 (Coupon Collector's Problem)。 1. 定义状态和随机变量   设  为集齐所有  个面所需的总投掷次数。我们要求的是 。   我们可以将整个过程分解为  个阶段：  第 0 阶段：已经集齐 0 个面，目标是集齐第 1 个面。 第 ...

题目链接 单选错位 题目描述 一份试卷有  道单项选择题，第  题有  个选项。每道题的正确答案都是从其选项中等概率随机选出的。 旺仔哥哥本来做对了所有题目，但在誊写答案时，发生了错位：  原第  题的答案被写到了第  题的位置 (对于 )。 原第  题的答案被写到了第  题的位置。  求在这种情况下，旺仔哥哥期望能答对多少题。 输入:  第一行一个整数 ，表示题目数量。 第二行  个整数 ，表示每道题的选项数。  输出:  输出一个实数，表示期望答对的题目数。  解题思路 本题的核心是利用期望的线性性质。 1. 期望的线性性质  设  为总共答对的题目数，这是一个随机变量。我们要求的是 。 ...

题目链接 随机路径长度期望 题目描述 给定一个  个点、 条边的有向无环图（DAG）。等概率随机地从图中所有简单路径的集合中选择一条路径。请求出所选路径的长度（经过的边数）的数学期望，结果对  取模。 一条简单路径可以长度为 ，即起点和终点是同一个点。 解题思路 根据数学期望的定义，路径长度的期望等于所有路径的长度总和除以所有路径的总数。  因此，问题被分解为两个核心任务：  计算图中所有简单路径的总数 。 计算图中所有简单路径的长度总和 。  这是一个可以在DAG上通过动态规划解决的问题。我们可以对每个节点 ，计算从它出发的所有路径的相关信息。由于是DAG，我们可以使用记忆化搜索（即DFS+...

题目链接 抢红包 题目描述 一个红包总金额为  元，有  个人来抢。规则如下：如果红包里还剩  元，下一个人抢到的金额是从区间  中等概率均匀随机出的一个实数。 求第  个人期望抢到多少钱，结果对  取模。 输入:  输入一行，包含三个整数 。  输出:  输出一行，表示第  个人期望抢到的钱数对  取模后的结果。  解题思路 这是一个经典的期望问题，可以通过线性递推来解决。 1. 定义状态  设  为第  个人抢到的金额（一个随机变量）。 设  为第  个人抢红包之前，红包里剩余的金额（也是一个随机变量）。 我们要求的是第  个人的期望金额，即 。  2. 分析单次期望  根据题目规则，如果...

题目链接 [SDOI2008]仪仗队 题目描述 在一个  的学生方阵中，观察者站在左后方（坐标原点 ）。方阵的学生坐标为 ，其中 。 一个位于点  的学生能被看到，当且仅当连接原点  和点  的线段上没有其他学生。你需要计算总共能看到多少名学生。 输入:  输入一行，包含一个整数 。  输出:  输出一行，表示能看到的学生总数。  注意：根据题目样例（，输出 ），我们可以推断出实际的方阵是从  到  的区域，观察者位于 ，并且不计自身。因此，我们需要统计坐标  在  范围内（ 不同时为 ）的可见点。 解题思路 这道题本质上是一个经典的数论问题，与欧拉函数紧密相关。 1. 可见性条件 一个位于点...

题目链接 动态序列 题目描述 给定一个长度为  的数组，你需要构建一个数据结构来支持以下两种操作：  查询第  小：找出当前整个序列中，从小到大排序后的第  个值。 单点修改：将第  个位置的元素修改为 。 注意：本题的值域范围为 。  解题思路 本题要求我们在支持单点修改的同时，快速查询整个序列的第  小值。 由于本题的值域被限制在了 ，我们可以采用一种非常直接高效的方法，而无需进行离散化。 核心思想：值域上的树状数组   数据结构：  我们可以建立一个大小为值域上限（例如 ）的树状数组。 在这个树状数组中，下标代表的是具体的数值。tr[v] 存储的是当前序列中值为 v 的数有多少个。   ...

题目链接 【模板】非质模数下的乘法逆元 题目描述 给定正整数对 ，求  模  的乘法逆元。 需要注意的是，数据不保证  为质数。 解题思路 本题要求解线性同余方程 ，其中  就是  模  的乘法逆元。题目特别指出， 不一定是质数，这意味着我们不能使用费马小定理。 求解该方程的通用方法是使用 扩展欧几里得算法（Extended Euclidean Algorithm）。   问题转化  线性同余方程  可以等价地写成二元一次不定方程（丢番图方程）的形式：，其中  是一个整数。 根据 裴蜀定理，这个方程有解的充要条件是  能够整除 。因为  和  都是正整数，所以这个条件就是 。即  和  必须互...