牛客937992666号

分类

题解(76)

/ 注册

全部文章（共77篇）

题解 | 小红的基环树 #

基环树：将个点和条边的连通无向图，即在个节点的树上添加一条边恰好包含一个环的图，称为基环树图的直径：在一个图中，任意两个节点的距离的最大值个节点构成的所有基环树中，最小的直径是多少？当时，就是一个最简单的环，此时直径为当时，可以构造这样的结构...

2026-01-25

0 39

题解 | 洛谷P11457 [USACO24DEC] Job Completion G #

这道题目和上一道题目类似，但是第个工作是需要在或之前做，需要的时间来做同样的，需要的是按照截至时间从小到大排序，那么是按照从小到大排序不多详解总代码： #include<bits/stdc++.h> using namespace std;...

2026-01-24

0 39

题解 | [JSOI2007]建筑抢修 #

这是我第一次做到反悔贪心的题目第座建筑有两个参数：需要秒维修以及需要在秒之前完成维修，否则报废无论是按照从小到大排序或者从小到大排序都会有个问题，就是可以一开始就选择了很不好的选择，例如我按照从小到大排序，我的想法是物品维修时间小的先修，维修时间大的后修。反例： 10 ...

2026-01-24

0 46

题解 | 最高分不下降路径 #

从到的任意简单路径（不重复经过顶点）顶点的权值序列为，需要满足，即不单调递减，那么得分就是中不同值的个数。求到中所有简单路径中最大的得分是多少因为权值需要满足不递减的关系，所以即使能到达，但如果，那么不能走到所以我们需要将每个点的权值从小到大排序，但是不需要排序，因...

C++

2026-01-24

0 34

题解 | 小红修道路 #

给你个点和条双向边，然后又给你条从到的双向计划道路。这一共边构成的图中：设从到每一个点的最短距离为，现在最多可以删除多少条计划道路，使得删除后的图中从到每一个点的最短距离仍然为。例如一条双向计划道路为，表示到的双向计划道路的权值为，如何判断这一条计划道路能否可以删除呢？ ...

2026-01-22

0 99

题解 | 【模板】最小生成树 #

给定一个无向连通有权图，其中是顶点集，是边集，边权为生成树的概念：是的一个子图，满足：包含的所有个顶点有且仅有条边子图是连通的，且无环最小生成树的概念：在所有的生成树中，边权值和最小的生成树 ...

2026-01-22

0 52

题解 | 洛谷P2730 [IOI 1996 / USACO3.2] 魔板 Magic Squares #

这道题目不难，但是有一个点需要注意：题目需要输出所有方案中字典序最小的答案，一开始使用的双向BFS解决，但是了三个点，原因是双向BFS搜索即使正向和反向同时按照字典序最小的顺序搜索，最后双向BFS搜索出来的结果也不一定是按照字典序最小的结果，为什么？因为双向扩展的异步性破坏了普通 BFS 的...

2026-01-19

0 34

题解 | 【模板】康托展开 #

康托展开：现在给你一个长度为排列，求这个排列在长度为的所有排列中是第几个排列(即求其排名)。假设现在的排列是那么排名等于，其中表示在剩余数组里面有多少个比小的数的个数例如排列时，剩余数组为，里面有个数比小，所以时，剩余数组为 &nb...

2026-01-18

0 33

题解 | 洛谷P3811 【模板】模意义下的乘法逆元 #

两种求解逆元的方法：快速幂和扩展欧几里得算法，时间复杂度都为，是模数这道题目需要求从到所有数对的乘法逆元，时间复杂度为，最坏情况是，给卡超时了正确的解法是线性逆元，在的时间复杂度求出从到所有数对的乘法逆元，该方法是线性从前推后，所以与时间复杂度与没有关系现在如...

2026-01-18

0 40

题解 | 旺仔哥哥走魔法迷宫 #

我觉得这道题目十分考验码力例如现在的位置是，根据题意，假设下一步可以到达的点是，每一个点满足那么我们有结构体存每个位置的 struct Node{ int x, y, sum;...

2026-01-18

0 36