TH911 Blog

「光阴不可测，岁月亦无歌。」

题解：间谍网络

洛谷P1262

题目传送门 一道水的 提高+/省选−，但是可能会降 普及+/提高。 因为这个请求升 提高+/省选− 的理由是另一道差不多的题目是 提高+/省选−，但是该题已经降 普及+/提高。 $\text{Updated at 2025/7/21}$ 真的降 普及+/提高 了…… 前置知识 Tarjan 缩点和拓扑排序。 题意...

Posted by TH911 on January 24, 2025

无向图 Tarjan 点双连通分量详解

例题：洛谷P8435

例题链接 有向图没有点双连通分量 有向图请见强连通分量。 点双连通分量 点双连通 若一个无向连通图删去任意一个点之后仍然连通，则该图点双连通。 点双连通分量 在满足边双连通的前提下尽可能大的子图。 Tarjan 求点双连通分量 前置知识：Tarjan 求割点 如果你不会，你可以看看。 Tarjan 求点双连通分量 ...

Posted by TH911 on January 23, 2025

无向图 Tarjan 求割点详解

例题：洛谷P3388

例题链接 割点 所谓割点，就是连通图中的某一个点满足删除该点后，原图不再连通。 如图中的 $2,4$ 就是一个割点。 但需要注意的是，割点不一定在环上，比如： 图中的 $2$ 就是割点。 不过存在特殊情况： 该图没有割点，无论去掉 $1$ 还是 $2$，最后都会剩下一个节点。 关于“割点”不同的定义 如同平衡树中的“左旋...

Posted by TH911 on January 23, 2025

题解：最短路计数

洛谷P1144

题目传送门 题意分析 因为是无向无权图，因此可以通过 BFS 求最短路。 BFS 找到即最优，因此找的时候递推即可。 AC 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ...

Posted by TH911 on January 23, 2025

无向图 Tarjan 边双连通分量详解

例题：洛谷P8436

例题链接 只有无向图有边双连通分量 有向图没有“边双连通分量”这个概念，只有“连通分量”、“强连通分量”和“弱连通分量”。 有向图见强连通分量。 边双连通分量 众所周知，在有向图中，存在强连通分量，强连通分量中的任意两点是连通的。 而在无向图中，同样存在边双连通分量。 边双连通 若一个无向...

Posted by TH911 on January 23, 2025

题解：[HAOI2006] 受欢迎的牛 G

题解：[USACO03FALL] 受欢迎的牛 G | 洛谷P2341

题目传送门 题意分析 给定 $n$ 个点，$m$ 条有向边，求有多少个点能够到达其他全部的点。 题目给出的类似于“奶牛 $A$ 喜欢奶牛 $B$”，我们可以从点 $B$ 向点 $A$ 连边，表示“$B$ 被 $A$ 喜欢”。 随后我们只需要看是否能够找到一个点，使其能够抵达所有的点即可。 但是会有环，因此我们可以用 Tarjan 缩点 来处理掉环，使得原图成为一个有...

Posted by TH911 on January 23, 2025

有向图 Tarjan 求强连通分量详解

有向图 Tarjan 缩点 | 例题：洛谷P3387

例题链接 只有有向图有强连通分量 无向图没有“强连通分量”这个概念，只有“连通块”。 无向图请看边双连通分量和点双连通分量。 引入 例题： 给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条...

Posted by TH911 on January 23, 2025

题解：[USACO10MAR] Great Cow Gathering G

洛谷P2986

题目传送门 树形 DP 换根树形 DP。 令 $dis_x$ 表示节点 $x$ 的子树内不方便程度的和。 显然，$dis_x$ 会因为根节点的不同而不同，我们考虑如何转换。 令 $dp_x$ 表示以 $x$ 为根节点时，不方便程度之和。 原来的 $dis_x$ 则是在以 $1$ 为根节点的条件下求得的。 则： \[dp_1=dis_1\] 对于节点 $x$ 的子节点...

Posted by TH911 on January 22, 2025

题解：[POI2008] STA-Station

洛谷P3478 | 换根 DP

题目传送门 树形 DP 依然是树形 DP。 首先，在根节点确定的情况下，深度之和显然可以 $\mathcal O(n)$ 求。 但是现在根节点不确定，因此我们需要 $\mathcal O(n)$ 来枚举根节点。 然而这样时间复杂度就来到了 $\mathcal O\left(n^2\right)$，考虑到 $1\leq n\leq 10^6$，无法通过此题。 如图： ...

Posted by TH911 on January 22, 2025

题解：[USACO06NOV] Round Numbers S

洛谷P6218

题目传送门 题意分析 求 $[l,r]$ 中有多少个整数满足其二进制中，$0$ 的个数大于等于 $1$ 的个数。 注意一个数的二进制不包括其前导 $0$。例如对于 $9$，其二进制仅仅是 $1001$。 分块打表 考虑到 $1\leq l\leq r\leq 2\times 10^9$，并不是很大，考虑分块打表。 计算机一秒内能够处理的数据规模约为 $4\times 10...

Posted by TH911 on January 22, 2025

FEATURED TAGS
树状数组 题解 提高+/省选− 省选/NOI− DP 普及+/提高 基础算法 数学 组合数学 普及/提高− 贪心 字符串 线段树 未完 图论 平衡树 数论 树形 DP 搜索 Tarjan Trie 二分 位运算 二分答案 状态压缩 FHQ Treap 前端 无聊时候的一点思考 最短路 树链剖分 NOI/NOI+/CTSC
ABOUT ME

要做一个优秀的 OIER

FRIENDS