tingshuo2917 - 博客园

2026年2月24日

摘要：树状数组 D001 单修区查单查区修区查区修【模板】树状数组 D002 二维偏序逆序对 P1908 逆序对 D003 偏序问题顺序对 ABC441E A > B substring 二叉堆 D004 二叉堆序列合并 P1631 洛谷阅读全文

posted @ 2026-02-24 12:29 tingshuo2917 阅读(2) 评论(0) 推荐(0)

D003 偏序问题顺序对 ABC441E A > B substring

摘要： ABC441E A > B substring - AtCoder 给一个只含字符 ABC 的字符串，问有多少个子串中 A 的数量大于 B 的数量。令 \(A=1,B=-1,C=0\) 求前缀和数组 \(a\) 可知子串应该满足的条件为 \(i<j\) \(a_j-a_i>0\) 即 \(a_i<a 阅读全文

posted @ 2026-02-24 12:23 tingshuo2917 阅读(1) 评论(0) 推荐(0)

D002 二维偏序逆序对 P1908 逆序对

摘要：

P1908 逆序对 - 洛谷逆序对其实就是二维偏序的一种，对数组 \(a\) ，如果 \(i<j\) 且 \(a_i>a_j\) ，则 \((a_i,a_j)\) 构成一个逆序对。树状数组求逆序对维护的是值域的频数，这就是为什么在 \(1e9\) 下需要进行离散化了，因为开不了这么大的数组。先阅读全文

posted @ 2026-02-24 11:12 tingshuo2917 阅读(4) 评论(0) 推荐(0)

2026年2月23日

D001 单修区查单查区修区查区修【模板】树状数组

摘要：树状数组（Binary Indexed Tree, BIT，也称 Fenwick Tree）是算法竞赛中极其常用的数据结构。它的核心优势在于：代码短小精悍、常数极小、内存占用少。虽然它的功能是线段树的子集，但在处理“动态前缀和”相关问题时，BIT 通常是首选。来自董晓算法，对两个关键函数原理的图阅读全文

posted @ 2026-02-23 23:13 tingshuo2917 阅读(2) 评论(0) 推荐(0)

图论题解一览

摘要：强连通分量前置知识：DAG基础。比如出度为 \(0\) 和入度为 \(0\) 的点的性质及影响，拓扑排序及其性质需要掌握：缩点 G001 强连通分量 Tarjan算法 P2812 USACO Network of Schools 校园网络 G002 强连通分量 Tarjan算法 CF999E R 阅读全文

posted @ 2026-02-23 21:35 tingshuo2917 阅读(2) 评论(0) 推荐(0)

G003 Tarjan算法缩点拓扑排序最长路 P3387 【模版】缩点

摘要： P3387 【模版】缩点 - 洛谷给定一个有向图，每个点都有一个权值，允许多次经过一条边或者一个点但权值只计算一次。求一条权值之和最大的路径。很明显的拓扑排序最长路问题，考虑缩点后进行 DP 。一般的方法为缩点后得到 DAG ，在新的 DAG 里进行拓扑排序。在拓扑排序的过程中更新状态转移方阅读全文

posted @ 2026-02-23 21:29 tingshuo2917 阅读(1) 评论(0) 推荐(0)

G002 强连通分量 Tarjan算法 CF999E Reachability from the Capital

摘要： CF999E Reachability from the Capital - CodeForces 给定一个有向图和一个节点 \(s\) ，问最少加多少条边可以使 \(s\) 可以到达图中所有的点（ \(s\) 可以到达自身）考虑缩点，缩点后源点一定被无法到达，所以我们需要统计源点的个数。特判，阅读全文

posted @ 2026-02-23 17:31 tingshuo2917 阅读(4) 评论(0) 推荐(0)

G001 强连通分量 Tarjan算法 P2812 [USACO]Network of Schools 校园网络

摘要： P2812 校园网络 [USACO]Network of Schools - 洛谷给定一个有向图， \(A \rarr B\) 表示 \(A\) 可以给 \(B\) 发送软件。问：最少需要给多少学校发送软件可以让所有学校收到问：最少加几条边，可以给任意一所学校发送软件使全图可以收到在有向图中阅读全文

posted @ 2026-02-23 16:32 tingshuo2917 阅读(1) 评论(0) 推荐(0)

公告