TH911 Blog

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

题解：失配树

洛谷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

例题链接 $\text{Upd on 2025/11/25}$：全文重写。以前写的什么鬼东西。 本文中，字符串下标统一从 $1$ 开始。 设字符串 $s$，$s[i]$ 表示 $s$ 的第 $i$ 个字符，以 $s[l,r]$ 表示 $s[l]s[l+1]\cdots s[r]$ 构成的子串。 前缀函数 设长度为 $n$ 的字符串 $s$，设其前缀函数 $\pi(i)$...

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

题解：[USACO12DEC] First! G

洛谷P3065

题目传送门 如果你还不会 Trie树：看这里 题意分析 策略 看到字典序，很容易想到考虑使用 Trie 树解决。 假设 $s$ 为更改字典序后可能的最小值，那么相当于钦定了 $s_i$ 小于其兄弟节点。（如图） 假设 $s=\texttt{acd}$，那么就钦定了 $c<a,c<b$，否则最小值不可能为 $\texttt{acd}$。 至此，思路就比...

Posted by TH911 on November 14, 2024

Trie 树详解

洛谷P8306 | Trie树

题目传送门 字典树（Trie树） 字典树其实就是一种空间换时间的策略。 比如我们使用 $\texttt{aa,ab,ac,abc,acd,aac}$ 来构造一棵字典树，则如下图： 简单而言，就是将每一位字符都视作连接节点的两条边，那么便形成了如上的树。 这么做有什么好处呢？ 节约时间。 这样查询前缀，仅仅需要在字典树上找到 $t$ 的最后一个字符，然后统计字数权值和...

Posted by TH911 on November 14, 2024

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

要做一个优秀的 OIER

FRIENDS