TH911 Blog

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

题解：[TJOI2015] 概率论

洛谷P3978 | “数学题” | 卡特兰数

题目传送门 题意分析 首先，对于这种输入只有一个数，从这一个数就能推出答案的题目，大概率是个毒瘤数学题。如此考虑求解。 求期望，期望即总叶节点数除以不同构的二叉树个数。 令 $n$ 个节点的不同构二叉树个数为 $f_n$，其叶节点总数为 $g_n$，则答案即 $\dfrac{g_n}{f_n}$。 考虑如何求解 $f_n,g_n$。 先考虑求解 $f_n$。其实 $f_n...

Posted by TH911 on July 14, 2025

题解：[RMI 2020] 秘鲁 / Peru

洛谷P11405 | 双栈模拟双端队列

题目传送门 双栈模拟队列 本篇题解主要介绍本题线性做法所利用的数据结构。 时间限制 $\text{300ms}$，又是交互题（无需 IO），显然是为了卡时间。 那么这道题大概率是一个 $\mathcal O(n)$ 的线性做法。 其实这道题目需要用到一个黑科技：双栈模拟队列。（具体见下文） 这道题目 DP 之后便是要维护一个数据结构，实现： 双端插入、删除。 ...

Posted by TH911 on July 14, 2025

题解：[HNOI2004] 树的计数

洛谷P2290 | Prüfer 序列

题目传送门 题意分析 对于这种关于树上度数的计数问题，一般会考虑使用 Prüfer 序列求解（Prüfer 序列参见此处）。 Prüfer 序列（Prufer 序列）的主要作用就是将无根树与序列相互转换，每一个确定的无根树都对应一个确定的 Prüfer 序列。 那么对于这道题目，假如树确定了，那么对应的 Prüfer 序列。因此满足条件的树的棵数即 Prüfer 序列的数量。...

Posted by TH911 on July 14, 2025

题解：齿轮

洛谷P6298 | 最大公因数转换

题目传送门 题意分析 将从 $n$ 个 $a_i$ 中选出 $k$ 个数，使得这 $k$ 个数的最大公因数为 $t$ 记为 $f_t$。题目即求解 $f_1,f_2,\cdots,f_m$。 但是可以发现这并不好求，因为无法确定最大公因数为 $t$ 对应哪 $k$ 个数。 可以思考一个常用的技巧：将最大公因数转化为普通因数。 那么我们求 $k$ 个数的因数均包含 $t$ 的...

Posted by TH911 on July 14, 2025

题解：可持久化线段树 2

静态区间第 $k$ 小问题

例题链接 静态区间第 $k$ 小 可以使用可持久化权值线段树解决。 求 $a[l,r]$ 第 $k$ 小不好求，因此可以考虑先简化一下，求 $a[1,r]$ 的 $k$ 小值。 这就可以使用可持久化权值线段树，对于每一个 $i$，给 $a_1\sim a_i$ 建一棵权值线段树统计数量。 查询时，使用前缀和与差分获取真实的 $[l,r]$ 中的数的个数即可。 AC 代码 ...

Posted by TH911 on July 13, 2025

题解：可持久化线段树 1（可持久化数组）

主席树 | 动态开点可持久化线段树

例题链接 可持久化线段树/主席树 可持久化线段树与主席树 “主席树”其实只是一个称呼，“主席树”的提出者也没有进行一个严谨的定义，一般主席树就是指可持久化权值线段树。 算法简介 可持久化线段树，可以维护多个历史版本下的线段树，支持单点修改，因此可以用来实现可持久化数组。 但是如果给每一个版本都开一个线段树，若有 $n$ 个节点，$m$ 个版本，空间复杂度就是 $\math...

Posted by TH911 on July 13, 2025

题解：[国家集训队] Crash的数字表格 / JZPTAB

洛谷P1829

题目传送门 莫比乌斯反演 对于这种题目，显然是一个数学题，因此可以转换。 不妨钦定 $n\leq m$，否则交换 $n,m$。 记答案为 $\textit{ans}$： \[\begin{aligned} \textit{ans}&=\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)\\ &=\sum_{i=1}^...

Posted by TH911 on July 11, 2025

题解：[NOI2018] 屠龙勇士

洛谷P4774

题目传送门 exexCRT 一条龙对应的剑可以通过平衡树等数据结构快速确定第 $i$ 条龙单次收到攻击为 $f_i$。 $x$ 次攻击后，龙的血量为 $a_i-f_ix$。 若干次回血后，血量为 $0$，即： \[\begin{aligned} a_i-f_ix&\equiv0&\pmod{p_i}\\ f_ix&\equiv a_i&\pm...

Posted by TH911 on July 10, 2025

题解：[NOI2002] 荒岛野人

洛谷P2421

题目传送门 题意分析 观察数据范围，$1\leq n\leq15,1\leq m\leq10^6$，数据范围不大，因此可以考虑枚举 $m$。 两个野人 $i,j$ 在第 $x$ 年相遇即： \[c_i+x\cdot p_i\equiv c_j+x\cdot p_j\pmod m\] 同时，$x$ 需要满足 $x\leq\min(l_i,l_j)$。 若没有野人相遇，则 $...

Posted by TH911 on July 10, 2025

题解：Short Task

CF1512G

题目传送门 题意分析 一个显然的性质，$d(n)\geq n$。因为 $n$ 自己一定是自己的因数。因此，若 $d(n)=c$ 存在，则 $n\leq c$。 又发现 $c\leq10^7$，且多次询问基本相同，因此可以考虑预处理出答案后离线处理。 自己写一下就可以发现，从 $n$ 找其因数求和并不好做，我太菜了，因此可以考虑从 $n$ 找其倍数 $kn$，更新 $kn$ 的...

Posted by TH911 on July 10, 2025

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

要做一个优秀的 OIER

FRIENDS