TH911 Blog

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

猫和老鼠

Posted by TH911 on November 19, 2024

高斯消元详解

例题：洛谷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\\ ...

Posted by TH911 on November 19, 2024

题解：失配树

洛谷P5829

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

Posted by TH911 on November 19, 2024

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

洛谷P8815

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

Posted by TH911 on November 19, 2024

题解：[POI2006] KRA-The Disks

洛谷P3434

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

Posted by TH911 on November 19, 2024

KMP 算法详解

例题：洛谷P3375

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

Posted by TH911 on November 18, 2024

题解：[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$ ...

Posted by TH911 on November 16, 2024

树链剖分详解

重链剖分 | 例题：洛谷P3384

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

Posted by TH911 on November 15, 2024

我讨厌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...

Posted by TH911 on November 15, 2024

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

洛谷P4555

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

Posted by TH911 on November 14, 2024

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

要做一个优秀的 OIER

FRIENDS