TH911 Blog

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

猫和老鼠


高斯消元详解

例题:洛谷P3389,P2455

题目传送门:【模板】高斯消元法,[SDOI2006]线性方程组。 引入 给定一个 $n$ 元一次方程组: \[\large \begin{cases} a_{1,1}x_1+a_{1,2}x_2+a_{1,3}x_3+\cdots+a_{1,n}x_n=b_1\\ a_{2,1}x_1+a_{2,2}x_2+a_{2,3}x_3+\cdots+a_{2,n}x_n=b_2\\ ...

题解:失配树

洛谷P5829

题目传送门 题意分析 首先,看到 border,我们自然而然地想到了 KMP。 所谓 border,其实就是其前缀和后缀相等。 现在,给定了字符串 $s$,求 $s[1,p]$ 和 $s[1,q]$ 的最长公共 border。($s[l,r]$ 表示 $s$ 中第 $l$ 位到第 $r$ 组成的字符串) 我们先考虑如何求出 border。 参照 KMP 算法即可。(如...

题解:[CSP-J 2022] 逻辑表达式

洛谷P8815

题目传送门 题意分析 给定一个 bool 运算表达式,求其值和两种布尔短路在运算途中发生的次数。 首先,对于这种让你“计算表达式”的题目,一般来讲就是栈、递归。 然而我们看到这之中,“运算优先级”就十分的烦人。 我们可以考虑手动给给定的表达式添加括号,也可以考虑转后缀或前缀表达式进行运算。 我们同样可以使用栈来模拟, & 直接算,而 | 在有括号时才计算。 在本...

题解:[POI2006] KRA-The Disks

洛谷P3434

题目传送门 实话实说,真不觉得能够评蓝…… $2025/7/20$ 更新:好了,降黄了…… $\mathcal O\left(n\right)$ 做法 如图,如果一个盘子能够通过第 $2$ 个管道,那么其宽度一定小于第 $2$ 个管道的深度,也就小于了第 $3$ 个管道的宽度。那么我们就可以把原序列变为一个单调不升序列(如图): 在此之后,我们就可以用一个指...

KMP 算法详解

例题:洛谷P3375

例题链接 什么是 KMP 算法 命名 首先,你要了解“KMP”的命名由来。 其实这仅仅是因为 KMP 算法由三个叫 Donald E. Knuth、James H. Morris, Jr. 和 Vaughan R. Pratt 的人共同提出而已。 作用 参考例题(洛谷P3375)。 在一个字符串 $s1$(通常称之为“文本串”)中查找另一个字符串 $s2$(通常称之为“...

题解:[ABC140E] Second Sum

AtCoder ABC140E

题目传送门 洛谷同步链接 题意分析 当 $a_i$ 对答案产生贡献时,当且仅当存在区间 $[l,r]$ 满足 $i\in[l,r]$ 且 $a_i$ 是 $[l,r]$ 的次大值。 由此我们开始做题。 计算合法区间数 显然,当且仅当区间中有且仅有一个数大于 $a_i$ 时,答案会增加 $a_i$。 那么我们考虑算出,对于每一个 $a_i$,会造成多少个 $a_i$ ...

树链剖分详解

重链剖分 | 例题:洛谷P3384

例题链接 本文所指的“树链剖分”,均指“重链剖分”,即将子树最大的子节点作为重子节点的树链剖分。 由于树链剖分代码较为冗长,本文所有代码均使用命名空间,g 代表邻接表,hld 代表树链剖分,seg 代表线段树。 关于树链剖分 是什么 顾名思义,将一个树剖分为多条链。 为什么 这样可以将原本树上的一对多信息关系化为一对一的线性关系,便于维护。(详见下文) 特点 ...

我讨厌zjj2024/zjj2023/FastFastTle/junjie_zhao/zjj_AK

?

我讨厌zjj2024/zjj2023/FastFastTle/junjie_zhao/zjj_AK 我讨厌zjj2024/zjj2023/FastFastTle/junjie_zhao/zjj_AK 我讨厌zjj2024/zjj2023/FastFastTle/junjie_zhao/zjj_AK 我讨厌zjj2024/zjj2023/FastFastTle/junjie_zhao/z...

题解:[国家集训队] 最长双回文串

洛谷P4555

题目传送门 如果你还不会Manacher:看这里 题意分析 首先,我们发现题目要求最长回文串,自然而然地想到 Manacher。 但是当我们求出最长回文半径 $p_i$ 后,却发现不知道如何进一步做题了。 如果枚举两个回文串分别的回文中心,那么就是一个 $\mathcal O\left(n^2\right)$ 的算法,考虑到 $2\leq \vert S \vert \...