查看原题请戳这里 虽然题目叫最短路计数，但是TA可以只用到最短路的概念而不用最短路的算法……由于这是一个无权图，所以一条路径上边的数量就是这条路径的长度，那么我们就可以用BFS来搞定这个问题了。 具体思路我们每遍历到一个节点就和ta的前一个结点的距离比较，这里会有三种情况：(由1到2) 2号点没 ...

定义欧拉路径（欧拉通路）：通过图中所有边的简单路。（换句话说，每条边都通过且仅通过一次）也叫”一笔画”问题。欧拉回路：闭合的欧拉路径。（即一个环，保证每条边都通过且仅通过一次）欧拉图：包含欧拉回路的图。 起源在一个图中求解一条欧拉回路的问题，起源于欧拉提出的、著名的“七桥问题”。详见百度百科。 判 ...

查看原题请戳这里 前言 没有什么是吸一口氧气解决不了的，如果有，就再吸一口…… 算法朴素暴力 首先，看到这道题的第一时间就想到了一个暴力的方法——枚举每一个x点和x与z的间距（只需要枚举偶数间接即可，否则无法满足y−x=z−y）。然而，这个算法是$O(n^2)$的，我们无法承受这个时间复杂度。 优 ...

查看原题请戳这里 解题思路首先，因为题目要求求“即满足经过景点数最大的前提下使得滑行总距离最小”，所以这道题目我们可以用最小生成树来解决。 具体做法核心算法 这里推荐用kruskal去求最小生成树(prim虽然加上堆优化也应该不会超时，但是ta真的是代码难敲效率还低qwq)。 因为这道题目对于每 ...

查看原题戳这里 一道有趣的建图题qxy当时做了好久才发现自己图建错了qwq看到“如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠”后，大家有没有感到一丝丝熟悉呢？ 没错，这个条件和拓扑排序的条件很相似所以，我们只需要把所有的车站放到一个图中，在用一个类似于 ...

查看原题请戳这里 算法思路题目中一共给了合并和查询和两种操作，很显然我们可以用并查集来实现。但是，查询操作需要给出两个点之间的距离，那么我们怎么去统计这个量呢？如图，我们可以发现，如果我们想要知道4号点到2号点的距离，如果不压缩路径，我们可以选择一步步去统计这两个点到祖先的距离，然后进行计算。但是 ...

查看原题请戳这里 和关押罪犯差不多，也是一个种类并查集的题目。不过关押罪犯有两个种类，而这个题复杂一些，有三个种类，但大体思路都是一样的，我们只需要开三倍空间就可以了。对于每一句话，我们只需要判断它和前面的记录是否冲突，若冲突，则让ans + 1，否则按照这句话的要求去修改。 Tips： 因为要开 ...

其实……说实话我还真的不是非常会用qwq先存一下板子把，以后慢慢来qwq 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606 ...

树的直径定义 给定一棵树，树中每条边都有一个权值，树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链。后者通常也可称为直径，即直径是一个数值概念，也可代指一条路径 性质 直径两端点一定是两个叶子节点 距离任意点最远的点一定是 ...

查看原题请戳这里 暴力做法枚举呗……时间复杂度$O(n^2)$。显然，这种复杂度不是我们可以接受的 线段树做法ps： 感觉这东西还是暴力……由于这道题目问的是区间的最大值和最小值，所以我们可以用线段树去解决。（只有查询，可好敲了）但是呢，由于线段树的复杂度是$O(nlogn)$的，而且ta常数比较 ...